Saturday, February 18, 2012

Difference between LinkedList vs ArrayList in Java

LinkedList and ArrayList both implement List Interface but how they work internally is where the differences lies. Main difference between ArrayList and LinkedList is that ArrayList is implemented using re sizable array while LinkedList is implemented using doubly LinkedList. ArrayList is more popular among Java programmer than LinkedList as there are few scenarios on which LinkedList is a suitable collection than ArrayList. In this article we will see some differences between LinkedList and ArrayList and try to find out when and where to use LinkedList over ArrayList.

LinkedList vs ArrayList in Java

Difference between LinkedList and ArrayList in JavaAll the differences between LinkedList and ArrayList has there root on difference between Array and LinkedList data-structure. If you are familiar with Array and LinkedList data structure you will most likely derive following differences between them:

1) Since Array is an index based data-structure searching or getting element from Array with index is pretty fast. Array provides O(1) performance for get(index) method but remove is costly in ArrayList as you need to rearrange all elements. On the Other hand LinkedList doesn't provide Random or index based access and you need to iterate over linked list to retrieve any element which is of order O(n).

2) Insertions  are easy and fast in LinkedList as compared to ArrayList because there is no risk of resizing array
and copying content to new array if array gets full which makes adding into ArrayList of O(n) in worst case, while adding is O(1) operation in LinkedList in Java. ArrayList also needs to update its index if you insert something anywhere except at the end of array.

3) Removal is like insertions better in LinkedList than ArrayList.

4) LinkedList has more memory overhead than ArrayList because in ArrayList each index only holds actual object (data) but in case of LinkedList each node holds both data and address of next  and previous node.

When to use LinkedList and ArrayList in Java

As I said LinkedList is not as popular as ArrayList but still there are situation where a LinkedList is better choice than ArrayList in Java. Use LinkedList in Java if:

1) Your application can live without Random access. Because if you need nth element in LinkedList you need to first traverse up to nth element O(n) and than you get data from that node.

2) Your application is more insertion and deletion driver and you insert or remove more than retrieval. Since insertion or
removal doesn't involve resizing its much faster than ArrayList.

That’s all on difference between ArrayList and LinkedList in Java. Use ArrayList in Java for all there situation where you need a non-synchronized index based access. ArrayList is fast and easy to use, just try to minimize array resizing by constructing arraylist with proper initial size.

Other Java Tutorials you may like

18 comments :

Anonymous said...

Another difference between LinkedList and ArrayList is that ArrayList is index based while LinkedList is not. I prefer to use ArrayList or Vector but never used LinkedList.

Anonymous said...

LinkedList vs ArrayList, ArrayList vs LinkedList, ArrayList and LinkedList in Java, LinkedList and ArrayList in Java, Differnece between ArrayList and LinkedList, Difference between LinkedList and ArrayList, What is difference between LinkedList and ArrayList, When to use LinkedList and When to use ArrayList, LinkedList and Array in Java

Thomas Mauch said...

You may want to have a look at http://java.dzone.com/articles/gaplist-%E2%80%93-lightning-fast-list which introduces GapList which strives for combining the strengths of both ArrayList and LinkedList.

Jan Kowalski said...

Would someone explain why I'm getting better results with inserting to ArrayList list than to LinkedList? Is that some compiler optimization? Using Java 1.6.0 u27.

Here's the code I used:

public class ListsTest {

public static void main(String args[]) {
int count = 10000000;
List arrayList = new ArrayList();
long time = addElements(arrayList, count);
System.out.println("ArrayList with " + count + " elements: " + time
+ " ms.");
List linkedList = new LinkedList();
time = addElements(linkedList, count);
System.out.println("LinkedList with " + count + " elements: " + time
+ " ms.");
}

private static long addElements(List list, int number) {
long start = System.currentTimeMillis();
for (int i = 0; i < number; i++) {
list.add(i);
}
long end = System.currentTimeMillis();
return end - start;
}
}

Anonymous said...

Hi all - currently thinking of whether to choose ArrayList or LinkedList.
So as i understood from all the comments i found, LinkedList is faster, when inserting at random places, but slower when reading from random index.
But please take a look at the following test:

public class Test {

private static final int NUMBER = 100000;


/**
* @param args
*/
public static void main(String[] args) throws Exception {
testAddEnd(new ArrayList());
testAddEnd(new LinkedList());
testAddEnd(new Vector());
testAddMiddle(new ArrayList());
testAddMiddle2( new LinkedList());
testAddMiddle(new Vector());
testAddStart(new ArrayList());
testAddStart(new LinkedList());
testAddStart(new Vector());
}


private static final void testAddEnd(List list) throws Exception {
long time = System.currentTimeMillis();
for (int i = 0; i < NUMBER; i++) {
list.add(Integer.valueOf(i));
}
System.out.println("Add End (" + list.getClass().getName() + "): " + (System.currentTimeMillis() - time));
Thread.sleep(2000);
}


private static final void testAddMiddle(List list) throws Exception {
long time = System.currentTimeMillis();
for (int i = 0; i < NUMBER; i++) {
if (list.size() > 0) {
list.add(i / 2, Integer.valueOf(i));
} else {
list.add(Integer.valueOf(i));
}
}
System.out.println("Add Middle (" + list.getClass().getName() + "): " + (System.currentTimeMillis() - time));
Thread.sleep(2000);
}


private static final void testAddMiddle2(LinkedList list) throws Exception {
long time = System.currentTimeMillis();
for (int i = 0; i < NUMBER; i++) {
if (list.size() > 0) {
list.add(i / 2, Integer.valueOf(i));
} else {
list.add(Integer.valueOf(i));
}
}
System.out.println("Add Middle (" + list.getClass().getName() + "): " + (System.currentTimeMillis() - time));
Thread.sleep(2000);
}

private static final void testAddStart(List list) throws Exception {
long time = System.currentTimeMillis();
for (int i = 0; i < NUMBER; i++) {
if (list.size() > 0) {
list.add(0, Integer.valueOf(i));
} else {
list.add(Integer.valueOf(i));
}
}
System.out.println("Add Start (" + list.getClass().getName() + "): " + (System.currentTimeMillis() - time));
Thread.sleep(2000);
}
}


with the results:

Add End (java.util.ArrayList): 21
Add End (java.util.LinkedList): 15
Add End (java.util.Vector): 11
Add Middle (java.util.ArrayList): 485
Add Middle (java.util.LinkedList): 9192
Add Middle (java.util.Vector): 482
Add Start (java.util.ArrayList): 1108
Add Start (java.util.LinkedList): 15
Add Start (java.util.Vector): 1150


Could you explain this???

Thanks, Dirk.

Terry said...

@Dirk, You can see that LinkedList give better performance than ArrayList while inserting object into either beginning or end , because LinkedList is implemented at DoublyLinked list using Deque interface. Also for random index requires traversal of list either from beginning or end, whichever is closer to the position. That's why insertion on middle is such an expensive operation in LinkedList.

Anonymous said...

I understand that the right way to traverse a LinkedList is through ListIterator and it scans it sequentially. But Java API does provide an API for random access using get(int index). And in facts its performance is same as of LinkedList (as show from code below). Does it mean Java provides an efficient wrapper API for LinkedList that works like ArrayList?

public static void main(String[] args) {
// TODO Auto-generated method stub
LinkedList list = new LinkedList();
for (int i =0;i<=1000000; i++) {
list.add(i);
}
long start = System.currentTimeMillis();
list.get(1);
long end = System.currentTimeMillis();
System.out.println(" time to traverse 1st element " + (end - start) );


start = System.currentTimeMillis();
list.get(999999);
end = System.currentTimeMillis();
System.out.println(" time take to traverse 999999th element " + (end - start) );
}

time to traverse 1st element 0
time to traverse 999999th element 0

-- Viv

Anonymous said...

Does ArraList vs LinkedList is similar to Array vs LinkedList in terms of data structure ?

Anonymous said...

Guys, before you try to do test like those up here, please keep in mind things like warming up testing environment. You have to pass code optimization by making few(lots) of creating, retriving etc operation as some optimization will be done during compilation some during application running.

Caleb said...

Linked list also keeps the order after a remove(index)

Anonymous said...

Good and clear explanation. Fortunately for me, most of my problems have been of the "array-type" while I was not really aware of linked lists.

SARAL SAXENA said...

Hi Javin..gr8 article few things that I want to add is ...
LinkedList and ArrayList are two different implementations of the List interface. LinkedList implements it with a doubly-linked list. ArrayList implements it with a dynamically resizing array.

As with standard linked list and array operations, the various methods will have different algorithmic runtimes.

For LinkedList

get is O(n)
add is O(1)
remove is O(n)
Iterator.remove is O(1)
For ArrayList

get is O(1)
add is O(1) amortized, but O(n) worst-case since the array must be resized and copied
remove is O(n)
LinkedList allows for constant-time insertions or removals, but only sequential access of elements. In other words, you can walk the list forwards or backwards, but grabbing an element in the middle takes time proportional to the size of the list.

ArrayLists, on the other hand, allow random access, so you can grab any element in constant time. But adding or removing from anywhere but the end requires shifting all the latter elements over, either to make an opening or fill the gap. Also, if you add more elements than the capacity of the underlying array, a new array (twice the size) is allocated, and the old array is copied to the new one, so adding to an ArrayList is O(n) in the worst case but constant on average

Jay said...

Another key difference between ArrayList vs LinkedList in Java is that LinkedList implements Queue interface, which means it can be used as FIFO data structures. LinkedList implements method defined in Queue interface e.g. poll(), peek() and offer() which can be used to retrieve and remove head element from list. ArrayList doesn't implement Queue interface. Since LinkedList provides O(1) performance for adding object at beginning and removing object from end, its best suited for such use cases.

Marioosh said...

I'm using LinkedList only when I need Queue interface features, in all other situations I prefer ArrayList. Nice comparision, good job.

Volodymyr Levytskyi said...

LinkedList can be used as queue,deque and stack and even index-access collection.
LinkedList is truly function-rich.
LinkedList is best suited when you need sequential access to it like adding,removing elements one after another. However indexed access might be not very efficient.
Read my tutorial to know more about internal life of LinkedList here

Anonymous said...

In arraylist too we can remove the elements using the index value: http://docs.oracle.com/javase/6/docs/api/java/util/ArrayList.html#remove(int)

But your following statement is contradictory in the first point:

"but remove is costly in ArrayList as you need to rearrange all elements"

Javin @ ArrayList vs LinkedList said...

@Anonymous, Yes, we can remove elements by index in ArrayList, but that also shifts subsequent elements to the left by subtracting one from there index, This is costly operation, because it involves calls to System.arraycopy() for copying elements. If you look code for remove(int index) from java.lang.ArrayList, this is clear:

int numMoved = size - index - 1;
if (numMoved > 0)
System.arraycopy(elementData, index+1, elementData, index,
numMoved);
elementData[--size] = null; // Let gc do its work

arvinrong said...

QUOTE:"time to traverse 1st element 0
time to traverse 999999th element 0"

The reason of the test result shown above is that the retrieval operation of get(i) method either begin from the beginning or the end of the list. And it depends on which index is closed to index i.So get(1) starts retrieving from the beginning of the list, get(999999) starts from the end instead.

Post a Comment