In Java, ArrayList and LinkedList, both are members of the Collection framework. They implement java.util.List interface and provide the capability to store and get objects in ordered collections. Both are non-synchronized classes. Still, they are different in many aspects, and we need to understand both classes in detail to make a wise decision about when to use which class.
1. Internal Implementation of LinkedList vs. ArrayList
The LinkedList is a doubly linked list implementation in Java. Every object in the linkedlist is wrapped in a Node instance:
transient Node<E> first;
transient Node<E> last;
private static class Node<E> {
E item;
Node<E> next;
Node<E> prev;
}The ArrayList has been implemented as a dynamically resizing array. This will lead to further differences in performance.
transient Object[] elementData;Note that both lists allow duplicate elements and maintain the insertion order of the elements. In LinkedList, elements have reference to the next and previous elements.
2. Difference in Performance
2.1. Add an Element
Adding an element in ArrayList is O(1) operation if it doesn’t require resizing of backing array. If array is resized, then it becomes O(log(n)).
Adding an element in LinkedList is O(1) operation, as it doesn’t require any resizing.
2.2. Remove an Element
When we remove an element from ArrayList (in backing array), it moves all elements that are after the removed index position. It makes it close to O(n) in the worst case when we remove first element. The performance is O(1) in the best case when we remove last element.
LinkedList remove() operation gives O(1) performance because it just needs to reset the pointers of the previous and next nodes. No copy or movement is required.
2.3. Iteration
The iteration is the O(n) operation for both LinkedList and ArrayList where the list contains ‘n’ items.
2.4. Get an Element
ArrayList provides get(int index), which directly finds the element at a given index location. It is of order O(1).
LinkedList also provides get() method, BUT it first traverses all nodes to reach the correct node. It makes the performance variable. In the best case, it is O(1), and in the worst case, it is O(n).
3. Conclusion
Until we are not dealing with a very high volume of data, both classes will give us the same level of performance. Both are ordered lists, and both are non-synchronized as well.
The LinkedList implements Deque interface as well, so it provides queue-like FIFO functionality through methods such as peek() and poll(). As seen in the performance comparison, ArrayList is better for storing and accessing data. LinkedList is better for manipulating data.
That’s all for arraylist vs linkedlist in java.
Happy Learning !!
Read More: ArrayList Java Docs and LinkedList Java Docs
Leave a Reply