1. ArrayList and LinkedList implement the
List interface. However, they differ completely in the way they store and link to the elements.
2. An ArrayList stores the elements sequentially based on their index. While LinkedList uses a doubly-linked list to store its elements.
3. A doubly-linked list consists of a collection of nodes, where each node contains three fields –
- The data at that node.
- A pointer/reference to the next node in the list.
- A pointer/reference to the previous node in the list.
4. Following is a representation of ArrayList and LinkedList data structures:
Following are some important differences between LinkedList and ArrayList:
- A LinkedList consumes more memory than an ArrayList because it also stores the next and previous references along with the data.
- You can access an element in an ArrayList in
O(1)time. But it takes
O(n)time to access an element in a LinkedList because it needs to traverse to the desired element by following the next/prev references.
- Adding or removing elements are usually slower in an ArrayList compared to LinkedList. This is because the elements in the ArrayList needs to be shifted if a new element is added in the middle of the ArrayList. The ArrayList might also need to be resized to accommodate the new element. Similarly, in case of removal, the elements in the ArrayList needs to be shifted to the new positions.