In java, ArrayList and LinkedList both are linear data structures in the Collection framework. Both data structures introduced due to the limitation of the array because the Array has a predefined and fixed size. In this post, we will see the difference between ArrayList and LinkedList. There are many similarities in both, but we will discuss how ArrayList vs LinkedList in deep.
Implementation
Implementation of both classes are the first difference between ArrayList and LinkedList in java.
The ArrayList class implements the List, Cloneable, RandomAccess, and Serializable interface and extends the AbstractList class.
The LinkedList class implements the List, Cloneable and Serializable, Deque interface and extends the AbstractList class.
You can see LinkedList class doesn’t implement RandomAccess interface but implements Deque interface.
Default capacity
The default capacity of the ArrayList class is 10. Whenever we create an ArrayList it has default size that is 10.
But A LinkedList doesn’t have default capacity. Because it creates a node when we add an element.
Data structure
An ArrayList uses internally a dynamic Array. It is a growable Array and it can increase and decrease itself when we manipulate it. Here each element stores in the unique index value.
But LinkedList uses the doubly linked list structure to store the elements and each element bind with the next and previous element. Here each element stores as a node and the node has the address part, that contains the address of the previous and next node.
Access
As we know ArrayList class implements a Random interface, so it supports the random access of elements based on the index value. We can get any element randomly by an index value.
But LinkedList class doesn’t implement the Random interface, so we can’t access the element directly. When we access elements by index value, that element goes for search from head to tail.
Performance
An ArrayList performs better than LinkedList when store and access the elements. Because it supports random access.
But LinkedList performs better than ArrayList when we want to perform manipulation. Because we can add or remove easily in LinkedList.
When to use
If you want to perform manipulation in data more than the access to data, then you should use LinkedList. Because when we add or remove any element from ArrayList it shifts all the elements after the operation.
Suppose we have an ArrayList of 1000 element and we are removing element at index 50. The JVM shifts all the elements towards left after index 50.
But on LinkedList, if we remove any element, JVM removes the node and changes the address of the node. You can see it here.
But ArrayList supports random access and LinkedList doesn’t support it so we can use it accordingly.
Searching
The search operation is fast in ArrayList as compare to LinkedList. Because ArrayList support random access and we can get element by index value directly. But LinkedList doesn’t support it, if we get the element by index value it starts searching sequentially. ArrayList gives the performance of O(1) while LinkedList performance is O(n).
Memory management
As we know ArrayList increase itself automatically, but internally it creates new ArrayList and copy all the values from old ArrayList. That consume more memory in java. But LinkedList doesn’t increase it size in advance.