Sunday, 27 August 2017

Internal implementation of ArrayList in Java

   There are two List interface implementation classes in Collection , i.e ArrayList and LinkedList. The ArrayList is most commonly used Collection class in java. We can discuss about how ArrayList internally works and what are the methods .

  ArrayList internally uses array object to add the elements. In other words, ArrayList is backed by Array data-structure. The array of ArrayList is resizable i.e dynamic in nature.

     Below code is internal implementation or source code of add(), remove(), contains() and size() methods of ArrayList.


package com.pr;

import java.util.Arrays;

public class CustomArrayList {

       private static int DEFAULT_CAPACITY = 10;
       private int size = 0;
       private transient Object[] element = {};
       public CustomArrayList () {
             element = new Object[DEFAULT_CAPACITY];
       } 
       public void add(Object obj) {
            if (size == element.length) {
                 increaseCapacity();
             }
             element[size++] = obj;
       }
 
       public Object get(int index) {
             if (index >= size || index<0) {
                     throw new ArrayIndexOutOfBoundsException();
             }
             return element[index];
       }
 
       public Object remove(int index) {
            if (index < size) {
                   Object obj = element[index];
                   element[index] = null;
                   int temp = index;
                   while (temp < size) {
                         element[temp] = element[temp + 1];
                         element[temp+1] = null;
                         temp++;
                    }
                    size--;
                    return obj;
             } else {
                  throw new ArrayIndexOutOfBoundsException();
             }
       }
 
       public boolean contains(Object obj) {
              boolean flag = false;
              if (obj == null) {
                   for (int i = 0; i<size; i++) {
                        if (element[i] == null) {
                             flag = true;
                        }
                    }
                } else {
                      for (int i = 0; i<size; i++) {
                           if (obj.equals(element[i])) {
                                flag = true;
                           }
                      }
                }
                return flag;
        } 
 
        private void increaseCapacity() {
              int increasedSize = element.length * 2;
              Arrays.copyOf(element, increasedSize);
        }
        public int size() {
             return size;
        }
}
 

The main program :--

package com.pr;

public class MainClass {
      public static void main(String[] args) {
            CustomArrayList list = new CustomArrayList();
            list.add("AB");
            list.add("BC");
            System.out.println(list.size());
            System.out.println(list.contains("AB")); 
      }
}
  

  Output : - 2
                   true


Related Post :
Collection Related Interview Questions and Answers in Java(List,Map & Set)  
 

1 comment:

  1. Actually I did'nt knew about Java, but I think this article about "Internal implementation of ArrayList in Java" it's cool

    ReplyDelete