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.
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 List interface.
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 ConcurrentModificationException if 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 Deque interface,
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 while ArrayList 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
Nice post!
ReplyDeleteIts also good to mention that ArrayList can be created with an initial array size so if you know how many items you're going to store in it you can speed up .add operations because re sizing the backed array won't be needed (unless adding more items than the initial capacity).
Just to make sure I understand clearly, let's say I am building a list that is going to be an attribute of a domain object. It is going to created (add) and then most likely read through as needed. But not changed and not really direct index accessed. In that case despite the slightly larger memory size, the LinkedList would actually make more sense. Just making sure I read correctly.
ReplyDeleteDon't forget that when using an iterator you can .remove() while iterating causing an extremely efficient and fast removal.
ReplyDeleteI know ArrayList is faster than LinkedList in most of cases e.g. getting an element form beginning, middle and end, does any one knows, when LinkdList is faster than ArrayList? I can think of only adding at the beginning, because there linked list doesn't resize, it just a pointer change, while array may resize, which is copy operation. Anything other case??
ReplyDelete