Difference between ArrayList vs LinkedList in Java | When to use one over other
ArrayList and LinkedList are two popular concrete implementation of List Collection class in Java. Being List implementation both ArrayList and LinkedList are ordered, index based and allows duplicate but despite being from same type hierarchy there are lot of difference between ArrayList and LinkedList in Java. Main difference between ArrayList vs LinkedList is that former is backed by Array while LinkedList is based upon LinkedList data structure which makes performance of add(), remove() and iterator()different for both ArrayList and LinkedList. Difference between ArrayList and LinkedList is also an important Java collection interview questions, as much popular as Vector vs ArrayList or HashMap vs HashSet in Java. Some time this is also asked as When to use LinkedList and When to use ArrayList in Java. In this Java collection tutorial we will compare LinkedList vs ArrayList on various parameter which will help us to decide when to use ArrayList over LinkedList in Java.
When to use ArrayList vs LinkdedList
Before comparing differences of ArrayList and LinkedList, let's see What is common between ArrayList and LinkedList in Java :
1) Both ArrayList and LinkedList are implementation of List interface, which means you can pass either ArrayList or LinkedList if a method accepts Listinterface.
2) Both ArrayList and LinkedList are not synchronized, which means you can not shared them between multiple threads without external synchronization. See here to know How to make ArrayList synchronized in Java.
3) ArrayList and LinkedList are ordered collection e.g. they maintain insertion order of elements i.e. first element will be added on first position.
4) ArrayList and LinkedList also allows duplicates and null unlike any other List implementation e.g. Vector.
5) Iterator of both LinkedList and ArrayList are fail-fast which means they will throw ConcurrentModificationExceptionif collection is modified structurally once Iterator is created. They are different than CopyOnWriteArrayList whose Iterator is fail-safe.
Now let's see some difference between ArrayList and LinkedList and When to use ArrayList and LinkedList in Java.
1) Data Structure
First difference between ArrayList and LinkedList comes with the fact that ArrayList is backed by Array while LinkedList is backed by LinkedList. This will lead further differences in performance.
2) LinkedList implements Deque
Another difference between ArrayList and LinkedList is that apart from List interface, LinkedList also implements Dequeinterface, which provides first in first out operations for add() and poll() and several other Deque functions. Also LinkedList is implemented as doubly linked list and for index based operation navigation can happen from either end.
3) Adding element in ArrayList
Adding element in ArrayList is O(1) operation if it doesn't trigger re-size of Array, in which case it becomes O(log(n)) , On the other hand appending an element in LinkedList is O(1) operation, as it doesn't required any navigation.
4) Removing element from a position
In order to remove an element from a particular index e.g. by calling remove(index), ArrayList performs a copy operation which makes it close to O(n) while LinkedList needs to traverse to that point which also makes it O(n/2), as it can traverse from either direction based upon proximity.
5) Iterating over ArrayList or LinkedList
Iteration is O(n) operation for both LinkedList and ArrayList where n is number of element.
6) getting element from a position
get(index) operation is O(1) in ArrayList while its O(n/2) in LinkedList, as it needs to traverse till that entry.
7) Memory
LinkedList uses a wrapper object, Entry, which is a static nested class for storing data and two nodes next and previous whileArrayList just store data in Array. So memory requirement seems less in case of ArrayList than LinkedList except the case where Array performs re-size operation, when it copies content from one Array to another. If Array is large enough it may take lot of memory at that point and trigger Garbage collection, which can slow response time.
From all the above differences between ArrayList vs LinkedList, It looks ArrayList is better choice than LinkedList in almost all cases, except when you do a frequent add() operation than remove() or get(). In my opinion use ArrayList over LinkedList for most of practical purpose.
Other Java Collection articles from Java67 blog
No comments:
Post a Comment