Which is Faster - LinkedList or ArrayList?

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

Ads

Tutorials   
Java final method Assert in Java Final method in java Autoboxing in Java assert In Java JDBC batch insert using Java bean class Java Singleton Pattern Java Collection API - Java Tutorials Stack Overflow - Java Tutorials End of Year Puzzle The link to the outer class,java tutorial,java tutorials Orientating Components Right to Left,java newsletter,java,tutorial Non-virtual Methods in Java - java tutorials Multicasting in Java - java tutorials,tutorial Creation Time Comparison of Multi Dimensional Array- Java Tutorials Making Exceptions Unchecked - java tutorial,java tutorials Making Enumerations Iterable - JDK 5 Example Which is Faster - LinkedList or ArrayList? LinkedHashMap - Java Tutorials HashMap and HashCode JDK 1.4 the NullPointerException - Java Tutorials Java HashMap - Java Tutorials Java GC java awt package tutorial Java Multi Dimensions Array - Java Tutorials Java HashSet  - Java Tutorials Java Field Initialisation - Java Tutorials Java Comments - Java Tutorials J2EE Singleton Pattern - Design Pattern Tutorials Java - JDK Tutorials garbage collection in java Final Methods - Java Tutorials Exceptional Constructors - Java Tutorials Double-checked locking,java tutorials,java tutorial Disassembling Java Classes - Java Tutorials Java Deadlocks - Java Deadlocks Tutorials, Deadlocks in Java Commenting out your code - Java Tutorials Class names don't identify a class - Java Tutorials Causing Deadlocks in Swing Code Exception in Java - Java Tutorials Catching Exceptions in GUI Code - Java Tutorials boolean comparisons - tutorial Interthread Communication in Java BASIC Java - Java Tutorials Thread Deadlocks - Java Tutorials Autoboxing unboxing in Java - Java Tutorials Assertion in Java Appending Strings - Java Tutorials Anonymous Inner Classes - Anonymous Inner Classes tutorial Assertion in java
Ads

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

Share on Google+Share on Google+

Which is Faster - LinkedList or ArrayList?

Posted on: April 18, 2011 If you enjoyed this post then why not add us on Google+? Add us to your Circles

Advertisements

 

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.

Ads

 

Ads