top button
Flag Notify
    Connect to us
      Site Registration

Site Registration

When to use LinkedList over ArrayList Explain in detail?

+3 votes
When to use LinkedList over ArrayList Explain in detail?
posted May 27, 2015 by Karthick.c

Share this question
Facebook Share Button Twitter Share Button LinkedIn Share Button

1 Answer

0 votes

ArrayList is essentially an array. Its elements can be accessed directly by index. But if the array is full, a new larger array is needed to allocate and moving all elements to the new array will take O(n) time. Also adding or removing an element needs to move existing elements in an array. This might be the most disadvantage to use ArrayList.

LinkedList is a double linked list. Therefore, to access an element in the middle, it has to search from the beginning of the list. On the other hand, adding and removing an element in LinkedList is quicklier, because it only changes the list locally.

In summary, the worst case of time complexity comparison is as follows:

                  | Arraylist | LinkedList
 get(index)        |    O(1)   |   O(n)
 add(E)            |    O(n)   |   O(1)
 add(E, index)     |    O(n)   |   O(n)
 remove(index)     |    O(n)   |   O(n)
 Iterator.remove() |    O(n)   |   O(1)
 Iterator.add(E)   |    O(n)   |   O(1)

Despite the running time, memory usage should be considered too especially for large lists. In LinkedList, every node needs at least two extra pointers to link the previous and next nodes; while in ArrayList, only an array of elements is needed.

answer Jun 5, 2015 by Shyam