Tuesday 30 September 2014

Internals of ArrayList (Part 2)

In the last tutorial ,we explored on the internal data structure and few other technical stuff including add method.In this tutorial we will try to understand why ArrayList is not preferred when you need to do modifications in list.
In this tutorial we will continue with add method. Instead of
which will insert the data at end , we will use
list.add(5, "data11");
which will add data in between the list.

import java.util.ArrayList;

 * @author Ganesh.Rashinker
public class Demo4 {
public static void main(String[] args) {
ArrayList<String> list = new ArrayList<String>();
for (int i = 1; i <= 10; i++) {
list.add("data" + i);
// insert 11th element at position 5th index
list.add(5, "data11");

The list is already having 10 elements and the 11th element is added at 5th index. As the initial capacity was 10 and which is full , a new array of capacity 16 will be created using ensureCapacity function. After the ensure capacity function, elementData is referring to new array of capacity 16.

After ensure capacity , System.arraycopy function copies the data from 5th index till the end of the list size and replaces the data from index 6.

so you have "data6"  at index 5 and 6. The next statement

elementData[index] = element;

actualy replaces "data6" with the new data "data11".

So this is how shifting of data happens. So Imagine you have ArrayList having size 1000 and you add a new element at index 5.

Conclusion: ArrayList is preferred when there are more reads and LinkedList is preferred where you have more modifications.This is one of the favorite interview question. ArrayList is expensive when you are modifying data  , we have already seen if you want to add data in between it need to shift the entire data from that index till the end of list. In this scenario , LinkedList is comparatively cheaper as memory would be allocated for new Node and the pointers of previous node and next node will be adjusted. There will be no other change in the entire LinkedList.