LinkedList versus ArrayList

Articles —> LinkedList versus ArrayList

In the Java Collections framework there are several implementation of the List interface - an interface which defines an ordered collection of objects. Both LinkedList and ArrayList of the more commonly used implementations, yet when does one choose one implementation of the other?

To answer this question, it is useful to understand what happens under the hood of these classes. An ArrayList stores its values within an array - items are accessed readily by their index. This provides fast access to values in the List given an index. A LinkedList however, stores its values as nodes - each node containing a reference to the previous and next nodes. This data structure requires traversal of the List by 'walking' from one node to the next to reach a particular index.

As a result of these different ways to implement the List interface, one can envision times where one implementation might be advantageous over the other.

  • Given the ArrayList is backed by an array, getting a value at an index using the get() method has a time complexity O(1). In contrast, a LinkedList must search forward from the root node to the given index - O(index).
  • Now consider a situation in which one continually adds to the front of the List. With a LinkedList the new value is simply placed at the front of the List, making the appropriate references - a time complexity of O(1). Alternatively, and ArrayList must shift all the indexes in the array before inserting the value - at the front of the List this equals O(n) (at other positions, O (n-index) and does not include array resizing if necessary).

These two scenarios are demonstrated below: 


int rounds = 10000000;

Random rand = new Random();



List<Integer> arrayList = new ArrayList<Integer>();

List<Integer> linkedList = new LinkedList<Integer>();



for ( int i = 0; i < 1000; i++ ){

	arrayList.add(i);

	linkedList.add(i);

}

//Ramp up

for ( int i = 0; i < rounds; i++ ){

	int val = arrayList.get(rand.nextInt(arrayList.size()));

}

for ( int i = 0; i < rounds; i++ ){

	int val = linkedList.get(rand.nextInt(arrayList.size()));

}

System.out.println("Testing the get method: ");

//Test the get method

long start = System.currentTimeMillis();

for ( int i = 0; i < rounds; i++ ){

	int val = arrayList.get(arrayList.size() - 1);

}

System.out.print("Time for ArrayList: ");

System.out.println((System.currentTimeMillis() - start));



start = System.currentTimeMillis();

for ( int i = 0; i < rounds; i++ ){

	int val = linkedList.get(linkedList.size() - 1);

}

System.out.print("Time for LinkedList: ");

System.out.println((System.currentTimeMillis() - start));

//Test insertions

System.out.println("Testing insertions: ");

//change rounds

rounds = 100000;

//Inserts

start = System.currentTimeMillis();

for ( int i = 0; i < rounds; i++ ){

	arrayList.add(0, 1);

}

System.out.print("Time for ArrayList: ");

System.out.println((System.currentTimeMillis() - start));



start = System.currentTimeMillis();

for ( int i = 0; i < rounds; i++ ){

	linkedList.add(0, 1);

}

System.out.print("Time for LinkedList: ");

System.out.println((System.currentTimeMillis() - start));

And the results on my system:


Testing the get method: 

Time for ArrayList: 0

Time for LinkedList: 91

Testing insertions: 

Time for ArrayList: 1310

Time for LinkedList: 1

Of course these are extreme examples, but being aware of how each data structure is implemented can go a long way in helping choose the correct implementation for each particular situation.

Links




Comments

  • thomas jeffson   -   July, 12, 2020

    Good jsob keep it up!x

Back to Articles


© 2008-2022 Greg Cope