Which is Faster - LinkedList or ArrayList?

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

Which is Faster - LinkedList or ArrayList?

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

 

Tutorials

  1. Assertion in java
  2. Anonymous Inner Classes - Anonymous Inner Classes tutorial
  3. Appending Strings - Java Tutorials
  4. Assertion in Java
  5. Autoboxing unboxing in Java - Java Tutorials
  6. Thread Deadlocks - Java Tutorials
  7. BASIC Java - Java Tutorials
  8. Interthread Communication in Java
  9. boolean comparisons - tutorial
  10. Catching Exceptions in GUI Code - Java Tutorials
  11. Exception in Java - Java Tutorials
  12. Causing Deadlocks in Swing Code
  13. Class names don't identify a class - Java Tutorials
  14. Commenting out your code - Java Tutorials
  15. Java Deadlocks - Java Deadlocks Tutorials, Deadlocks in Java
  16. Disassembling Java Classes - Java Tutorials
  17. Double-checked locking,java tutorials,java tutorial
  18. Exceptional Constructors - Java Tutorials
  19. Final Methods - Java Tutorials
  20. garbage collection in java
  21. Java - JDK Tutorials
  22. J2EE Singleton Pattern - Design Pattern Tutorials
  23. Java Comments - Java Tutorials
  24. Java Field Initialisation - Java Tutorials
  25. Java HashSet  - Java Tutorials
  26. Java Multi Dimensions Array - Java Tutorials
  27. java awt package tutorial
  28. Java GC
  29. Java HashMap - Java Tutorials
  30. JDK 1.4 the NullPointerException - Java Tutorials
  31. HashMap and HashCode
  32. LinkedHashMap - Java Tutorials
  33. Which is Faster - LinkedList or ArrayList?
  34. Making Enumerations Iterable - JDK 5 Example
  35. Making Exceptions Unchecked - java tutorial,java tutorials
  36. Creation Time Comparison of Multi Dimensional Array- Java Tutorials
  37. Multicasting in Java - java tutorials,tutorial
  38. Non-virtual Methods in Java - java tutorials
  39. Orientating Components Right to Left,java newsletter,java,tutorial
  40. The link to the outer class,java tutorial,java tutorials