ArrayList and LinkedList are the Collection classes, and both of them implements the List interface. The ArrayList class creates the list which is internally stored in a dynamic array that grows or shrinks in size as the elements are added or deleted from it. LinkedList also creates the list which is internally stored in a Doubly Linked List.
Both the classes are used to store the elements in the list, but the major difference between both the classes ArrayList and LinkedList is that ArrayList allows random access to the elements in the list as it operates on an index-based data structure. On the other hand, the LinkedList does not allow random access as it does not have indexes to access elements directly, it has to traverse the list to retrieve or access an element from the list.
Let us discuss some more differences between ArrayList and LinkedList with the help of the comparison chart shown below.
Content: ArrayList Vs LinkedList
|Basis for Comparison||ArrayList||LinkedList|
|Basic||ArrayList allows random access to the elements in the list.||LinkedList does not allow random access to the elements in the list.|
|Data structure||The internal structure used for storing elements is the dynamic array.||The internal structure used to store elements is doubly link list.|
|Extends||ArrayList extends AbstarctList class.||LinkedList extends AbstractSequentialList.|
|Implements||AbstractList implements List interface.||LinkedList implements List, Deque, Queue.|
|Access||Access to elements in the list is faster in ArrayList.||Access to elements in the list is slower in LinkedList.|
|Manipulation||Manipulation to elements in the list is slower in ArrayList.||Manipulation to elements in the list is faster in LinkedList.|
|Behaviour||ArraylList behaves as List as it implements list.||LinkedList behaves as List a well as the Queue as it implements List and Queue both.|
Definition of ArrayList
The AbstractList class is defined by the Collection Framework. It extends AbstarctList and implements List interface. ArrayList uses dynamic array i.e. the array of variable length as a internal data structure to store the elements in the list. The need of ArrayList arises as the array in java is of fixed length. So it can not grow or shrink in size as the elements are added or deleted from the array.
So you have to know the size of required array in advance. But the array list implemented using ArrayList class can grow and shrink in size as the elements are added or deleted from the array.
The array list implemented using ArrayList can be accessed randomly as ArrayList operates on the index-basis. So knowing index you can directly access the eleemnt of the list. There are three constructors of ArrayList:
ArrayList( ) ArrayList(Collection<? extends E> c) ArrayList(int capacity)
The first constructor implements an empty array list. The second constructor implements an array list initialized using the Collection c elements. The third constructor implements array list with the capacity provided in the argument. Working with the ArrayList, sometimes you will require converting the Collection ArrayList into an array. It can be done by calling toArray().
Definition of LinkedList
Like ArrayList, LinkedList is also a Collection class uses doubly linked list as an internal data structure to store the elements in the list. The LinkedList class extends AbstractSequentialList and implements the List, Deque and Queue interfaces. The linked list implemented using LinkedList can not be accessed randomly. If you want to retrieve any element from the list, you have to iterate the list in order to search that element.
There are two constructors in LinkedList class.
LinkedList( ) LinkedList(Collection<? extends E> c)
The first constructor creates an empty linked list. The second constructor creates a linked list, initialized with the elements of Collection c.
In LinkedList, the manipulation of the list is easy and fast. This is because if you add or delete any element in the list, then there is no need of shifting the elements as in ArrayList. But the accessing is slower as it does not have index to directly access the elements.
Key Differences Between ArrayList and LinkedList in Java
- The list implement by the ArrayList can be accessed randomly because ArrayList adopts the index-based data structure of the array. On the other hands, the list implemented by the LinkedList can’t be accessed randomly because for retrieving or accessing a particular element in the list you have to traverse the list.
- The internal data structure used by ArrayList to store the elements of the list is a dynamic array that can grow or shrink as the elements are added or deleted from the list. However, the internal data structure used by the LinkedList to store the elements in the list is doubly linked list.
- The ArrayList extends the AbstractList class which is also a Collection class whereas, the LinkedList class extends AbstractSequentialList class that is again a Collection class.
- ArrayList class implements List interface whereas, the LinkedList class implements List, Queue, and Deque interfaces.
- Accessing elements from the list implemented using ArrayList is faster as it has an index-based data structure. On the other hands, there is no index based structure in the list implement byLinkledList. Hence, an iterator is applied over the list to reach the element to be accessed which makes accessing slower in LinkedList.
- Manipulation is Manipulationin the list implemented using ArrayList because whenever an element is added or deleted from the list, the elements in the list are shifted to accommodate the change. On the other hand, manipulation is faster in the list implemented by LinkedList as it does not require shifting elements in the list on addition or deletion of the elements from the list.
- ArrayList acts like a list as it implements List interface whereas, the LinkedList act as list and queue as it implements List and Queue both.
When there is a frequent addition or deletion of the elements in the list, LinkedList must be used as it performs better during manipulation. If frequent search is applied to the list, the ArrayList is best choice, as it performs better while accessing elements from the list.
Sai Chand Pasupuleti says
Thanks for the explantion. Could you please add whether insertion order is maintained or not in arraylist and linkedlist.