Friday, December 27, 2013

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

Difference between ArrayList vs LinkedList in Java
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 interfaceLinkedList 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

5 comments:

oakleyses said...

louis vuitton handbags, oakley sunglasses, louboutin, longchamp outlet, nike shoes, louis vuitton outlet stores, chanel handbags, burberry outlet, prada outlet, jordan shoes, tiffany and co, michael kors outlet, tory burch outlet, louis vuitton outlet, longchamp handbags, nike free, true religion jeans, michael kors outlet, kate spade outlet, polo ralph lauren outlet, tiffany and co, prada handbags, polo ralph lauren outlet, michael kors outlet, michael kors outlet, longchamp handbags, oakley sunglasses, ray ban sunglasses, kate spade handbags, burberry outlet, louis vuitton outlet, louboutin outlet, louboutin, coach factory outlet, air max, air max, coach outlet, gucci outlet, christian louboutin shoes, michael kors outlet, coach purses, ray ban sunglasses, michael kors outlet, louis vuitton, coach outlet store online, true religion jeans, oakley sunglasses cheap

oakleyses said...

ralph lauren, lululemon, air max, hollister, north face, nike air max, polo lacoste, vanessa bruno, timberland, vans pas cher, louboutin, louis vuitton, oakley pas cher, air max pas cher, nike roshe run, air max, true religion outlet, barbour, sac longchamp, air force, hollister, sac louis vuitton, nike free, polo ralph lauren, nike trainers, louis vuitton uk, nike roshe, sac hermes, longchamp, michael kors, sac burberry, sac guess, mulberry, new balance pas cher, converse pas cher, sac louis vuitton, hogan outlet, nike tn, north face, true religion outlet, ray ban pas cher, michael kors, air jordan, nike blazer, nike free pas cher, michael kors pas cher, abercrombie and fitch, ray ban sunglasses

oakleyses said...

mac cosmetics, mont blanc, marc jacobs, canada goose outlet, nike huarache, vans shoes, soccer jerseys, hollister, giuseppe zanotti, beats by dre, abercrombie and fitch, longchamp, insanity workout, celine handbags, bottega veneta, ghd, nfl jerseys, north face outlet, chi flat iron, ugg boots, birkin bag, ugg australia, canada goose, herve leger, ugg pas cher, rolex watches, valentino shoes, canada goose uk, canada goose, ferragamo shoes, canada goose, ugg boots, uggs outlet, north face jackets, soccer shoes, asics running shoes, new balance shoes, p90x, lululemon outlet, canada goose jackets, mcm handbags, instyler, babyliss pro, ugg, wedding dresses, jimmy choo outlet, reebok outlet, nike roshe run

oakleyses said...

parajumpers, karen millen, air max, converse, pandora charms, moncler, louboutin, moncler, links of london, lancel, juicy couture outlet, oakley, hollister, pandora charms, supra shoes, thomas sabo, canada goose, gucci, wedding dresses, timberland boots, swarovski crystal, air max, coach outlet store online, moncler, ray ban, canada goose, moncler, ugg, louis vuitton, swarovski, hollister, montre homme, moncler, hollister clothing store, ralph lauren, rolex watches, moncler outlet, moncler, iphone 6 cases, baseball bats, juicy couture outlet, toms shoes, vans, pandora jewelry, ugg, converse shoes

Anna said...

Great and Useful Article.

Online Java Course

Java Online Training

Java Course Online

Best Recommended books for Spring framework

Java Interview Questions












Java Training Institutes in Chennai

Java Training in Chennai

J2EE Training in Chennai

java j2ee training institutes in chennai

Java Course in Chennai