Sunday 5 May 2013

Interview Question #10 How ArrayList works internally in java?

Another favorite interview question. Honestly whole of Collections is an interesting topic and a lot of interview questions can be framed on it. Advantage of this being, Java knowledge of Candidate is tested along with his/her data structure knowledge.

So lets understand how ArrayList works. This is the most basic question you could frame. Many other questions to come are based on this.

Basic Data Structure used in an ArrayList is -

private transient Object[] elementData; 

So it's an array of Object(Just the declaration.)
When we actually create an arrayList following piece of code is executed -


this.elementData = new Object[initialCapacity];


You create an ArrayList as follows -
  • List<String> myList = new ArrayList<String>();  OR 
  • List<String> myList = new ArrayList<String>(6); 
 1st one invokes a default constructor while the second will invoke a constructor with an integer argument. When we create an ArrayList in the 2nd way it will internally create an array of Object with size specified in the constructor argument(6 in our case). Default value is 10 i.e if no size is supplied array with size 10 is created.

Code for it is as follows -

    public ArrayList(int initialCapacity) {
    super();
        if (initialCapacity < 0)
            throw new IllegalArgumentException("Illegal Capacity: "+
                                               initialCapacity);
    this.elementData = new Object[initialCapacity];
    }



    public ArrayList() {
    this(10);
    } 



Once you tell this interviewer can be sure you know what data structure is internally used.Now we know ArrayList is better than normal arrays as it is size dynamically increases. But how does this take place internally? How much does the size increase?

Inside .add() method there is this check. Before adding element into the array it will check what is the current size of filled elements and what is the maximum size of the array. If size of filled elements is greater than maximum size of the array(or will be after adding current element) then size of the array must be increased. But if you know array basic you cannot dynamically increase the array size. So what happens internally is a new Array is created with size 1.5*currentSize and the data from old Array is copied into this new Array.

Code for it is as follows -

    public boolean add(E e) {
    ensureCapacity(size + 1);  // Increments modCount!!
    elementData[size++] = e;
    return true;
    }



    public void ensureCapacity(int minCapacity) {
    modCount++;
    int oldCapacity = elementData.length;
    if (minCapacity > oldCapacity) {
        Object oldData[] = elementData;
        int newCapacity = (oldCapacity * 3)/2 + 1;
            if (newCapacity < minCapacity)
        newCapacity = minCapacity;
            // minCapacity is usually close to size, so this is a win:
            elementData = Arrays.copyOf(elementData, newCapacity);
    }
    }



If you wish to know more you can view the ArrayList Sourecode. In Eclipse press Ctrl+T(Open Type) and type in ArrayList. Open it to view the source code.To visualize the ArrayList class refer to following image -



Related Links


9 comments:

  1. Thanks buddy...learned a new point

    ReplyDelete
  2. Hello,
    I have question, in list objects are stored by index, so how they are mapped with index, like if you try to fetch value at index, it will return object at given index. Like in map we will put key/value pair and fetch value at key but what about List. So how the mapping is done in ArrayList ?

    ReplyDelete
  3. Hi,
    ArrayList essentially contains an array which by the very definition of it is stored in contiguous memory locations. Your question takes me back to my college days where one of the most popular question is -

    Q. Difference between an array and linked list.
    Answer - Array is stored in contiguous memory location (sequentially) where as linkedlist is not. Next pointer is used to keep track of next node in the array list. So if you to the lowest level of understanding. Lets say you have an array of size 10 which can hold 10 integers. Assuming int is 32 bits or 4 bytes your array will take 40 bytes of memory. And if you see the memory locations it will be sequential. Eg 12000-12040 ( Hust numbers to give you the idea.)

    So coming to your question. If your memory location of int array of size 10 starts at 1200 ( to 12040) and you want the integer stored at index 2 you will do 1200 + (4 * 2) = 1208. To generalize it ,

    memoryLocation = startingMemLocation + ((size of variable type in bytes) * index)

    Map is again kind of pointers. You will have key stored in a place pointing to memory location of the value. You need the key to get the value which is the intended purpose of a Map. Hope that clarifies your question. Let me know if you still did not understand any part.

    ReplyDelete
    Replies
    1. Thanks Aniket...!

      You are right, I too remembered now, just the think I forgot, but like to clear answer that memory location of int array of size 10 starts at 12000(initially defined), later below line says 1200, instead it should use 12000 or vice versa.

      Thanks again.

      Delete
  4. could you please how arraylist works according to java 1.7 because oracle made lot changes internally but i am unable to understand how it works

    ReplyDelete

t> UA-39527780-1 back to top