Latest Tutorials| Questions and Answers|Ask Questions?|Site Map



Home Javatutorials Which is Faster - LinkedList or ArrayList?

Related Tutorials


 
 

Share on Google+Share on Google+

Which is Faster - LinkedList or ArrayList?

Advertisement
This article compares LinkedList and ArrayList and describes which is faster with an example.

LinkedList Vs ArrayList

In this tutorial, we will compare who is more faster-LinkedList or ArrayList.

As we have been listening the statement- ArrayList is faster than LinkedList, except when you remove an element from the middle of the list. Now in this tutorial we will perform test to verify how much extent this statement is true. 

Example

In the given below example, We have created three function which first adds the element and then removes the element from the passed collection which is either LinkedList or ArrayList. The time is recorded before adding removing elements, so that it can give you a clear view of time taken by these two. The function getClass() returns the runtime class of an object. The method getSimpleName() returns the simple name of the underlying class as given in the source code.

Given below the code with its output :

package simpleCoreJava;

import java.util.*;

public class ListTest {
private static final int NUM_ELEMENTS = 100 * 1000;

public static void main(String[] args) {
List ar = new ArrayList();
for (int i = 0; i < NUM_ELEMENTS; i++) {
ar.add(i);
}
testListBeginning(ar);
testListBeginning(new LinkedList(ar));
testListMiddle(ar);
testListMiddle(new LinkedList(ar));
testListEnd(ar);
testListEnd(new LinkedList(ar));
}

public static void testListBeginning(List list) {
long time = System.currentTimeMillis();
for (int i = 0; i < 10000; i++) {
list.add(0, new Object());
list.remove(0);
}
time = System.currentTimeMillis() - time;
System.out.println("beginning " + list.getClass().getSimpleName()
+ " took " + time);
}

public static void testListMiddle(List list) {
long time = System.currentTimeMillis();
for (int i = 0; i < 10000; i++) {
list.add(NUM_ELEMENTS / 2, new Object());
list.remove(NUM_ELEMENTS / 2);
}
time = System.currentTimeMillis() - time;
System.out.println("middle " + list.getClass().getSimpleName()
+ " took " + time);
}

public static void testListEnd(List list) {
long time = System.currentTimeMillis();
for (int i = 0; i < 10000000; i++) {
list.add(new Object());
list.remove(NUM_ELEMENTS);
}
time = System.currentTimeMillis() - time;
System.out.println("end " + list.getClass().getSimpleName()
+ " took " + time);
}
}

Output :


 beginning ArrayList took 3500                    
 beginning LinkedList took 15
 middle ArrayList took 1735
 middle LinkedList took 20750
 end ArrayList took 797
 end LinkedList took 1578

 

Advertisements

If you enjoyed this post then why not add us on Google+? Add us to your Circles



Liked it!  Share this Tutorial


Follow us on Twitter, or add us on Facebook or Google Plus to keep you updated with the recent trends of Java and other open source platforms.

Posted on: April 18, 2011

Related Tutorials

Discuss: Which is Faster - LinkedList or ArrayList?  

Post your Comment


Your Name (*) :
Your Email :
Subject (*):
Your Comment (*):
  Reload Image
 
 
Comments:1
Yurx
December 3, 2011
The test is invalid

This scenario is only applicable to ArrayLists. Accessing LinkedList elements by index is a very bad idea.
DMCA.com