One of the common interview question is “What is difference between ArrayList and LinkedList”.Before we actually see differences,let me give you brief introduction of both.
- ArrayList is implementation of list interface.
- ArrayList is not synchonized(so not thread safe)
- ArrayList is implemented using array as internal data structure.It can be dynamically resized .
- LinkedList is implementation of list and deque interface.
- LinkedList is not synchronized
- LinkedList is implemented using doubly linked list as internal data structure.
ArrayList vs LinkedList:
|Internal data structure||It uses dynamic array to store elements internally||It uses doubly Linked List to store elements internally|
|Manipulation||If We need to insert or delete element in ArrayList, it may take O(n), as it internally uses array and we may have to shift elements in case of insertion or deletion||If We need to insert or delete element in LinkedList, it will take O(1), as it internally uses doubly LinkedList|
|Search||Search is faster in ArrayList as uses array internally which is index based. So here time complexity is O(1)||Search is slower in LinkedList as uses doubly Linked List internally So here time complexity is O(n)|
|Interfaces||ArrayList implements List interface only, So it can be used as List only||LinkedList implements List,Deque interfaces, so it can be used as List,Stack or Queue|
When to use ArrayList or LinkedList?
It actually depends on our need.
- If we have more insertion or deletion then we should use LinkedList.
- If we have less insertion or deletion and more search operations then we should use ArrayList.