Difference Between ArrayList and LinkedList in Java

This article explains the differences between ArrayList and LinkedList and in which case we should prefer the one over the other.

ArrayList and Linked list both share the same properties due to inheritance of the same interface – List. But what is the difference between ArrayList and LinkedList? Simply said – ArrayLists are good for write-once-read-many operations, but bad at add/remove from the front or middle. On the other hand LinkedList is better for inserting and removing data.

Operations Performance

Following table shows the average algorithm complexity by executing different operations on LinkedLists and ArrayLists

ArrayList vs. LinkedList operations complexity

ArrayList vs. LinkedList operations complexity




ArrayList vs LinkedList Performance Example

Following example demonstrates the performance of add, set and remove operations using the same data on ArrayList and LinkedList

package javatutorial.net;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

public class ArrayListVsLinkedListExample {

	private static final int ELCOUNT = 50000;

	public static void main(String[] args) {

		List<String> alist = new ArrayList<String>();
		List<String> llist = new LinkedList<String>();

		// Insertion ////////////////

		// ArrayList
		long start = System.currentTimeMillis();
		for (int i = 0; i < ELCOUNT; i++) {
			alist.add("element #" + i);
		}
		long totalTimeMs = System.currentTimeMillis() - start;
		System.out.println("Adding 50K elements in ArrayList took " + totalTimeMs + " ms");

		// LinkedList
		start = System.currentTimeMillis();
		for (int i = 0; i < ELCOUNT; i++) {
			llist.add("element #" + i);
		}
		totalTimeMs = System.currentTimeMillis() - start;
		System.out.println("Adding 50K elements in LinkedList took " + totalTimeMs + " ms");

		// Modification /////////////

		// ArrayList
		start = System.currentTimeMillis();
		for (int i = 0; i < ELCOUNT; i++) {
			alist.set(i, "modified element #" + i);
		}
		totalTimeMs = System.currentTimeMillis() - start;
		System.out.println("Modifying 50K elements in ArrayList took " + totalTimeMs + " ms");

		// LinkedList
		start = System.currentTimeMillis();
		for (int i = 0; i < ELCOUNT; i++) {
			llist.set(i, "modified element #" + i);
		}
		totalTimeMs = System.currentTimeMillis() - start;
		System.out.println("Modifying 50K elements in LinkedList took " + totalTimeMs + " ms");

		// Removal //////////////////

		System.out.println("ArrayList size before removal " + alist.size());
		System.out.println("LinkedList size before removal " + llist.size());

		// ArrayList
		start = System.currentTimeMillis();
		for (int i = 0; i < ELCOUNT; i++) {
			alist.remove(0);
		}
		totalTimeMs = System.currentTimeMillis() - start;
		System.out.println("Removing 50K elements in ArrayList took " + totalTimeMs + " ms");

		// LinkedList
		start = System.currentTimeMillis();
		for (int i = 0; i < ELCOUNT; i++) {
			llist.remove(0);
		}
		totalTimeMs = System.currentTimeMillis() - start;
		System.out.println("Removing 50K elements in LinkedList took " + totalTimeMs + " ms");

		System.out.println("ArrayList size after removal " + alist.size());
		System.out.println("LinkedList size after removal " + llist.size());
	}

}

Here is the output of executing the example code. Results will vary on different computer configurations

Adding 50K elements in ArrayList took 10 ms
Adding 50K elements in LinkedList took 7 ms
Modifying 50K elements in ArrayList took 7 ms
Modifying 50K elements in LinkedList took 6315 ms
ArrayList size before removal 50000
LinkedList size before removal 50000
Removing 50K elements in ArrayList took 135 ms
Removing 50K elements in LinkedList took 4 ms
ArrayList size after removal 0
LinkedList size after removal 0

As you will see in the output above:

  • LinkedList is significantly slower at accessing and modifying elements
  • LinkedList is slower at adding elements
  • LinkedList is much faster at removing elements from the beginning of the list
  • ArrayList inserts new elements slower
  • ArrayList is significantly faster at accessing and modifying elements
  • ArrayList is significantly slower at removing elements from the beginning of the list

Disclaimer

The algorithm complexity and the operations performance is not constant in all cases. There are two major factors you have to take into account – the size of the list and where the elements we work with are placed in the list (at the beginning, in the middle or at the end). The only constant rule is: use ArrayList if you want to retrieve elements faster and LinkedList if you want to manipulate data faster.

Share on FacebookTweet about this on TwitterShare on LinkedInShare on Google+Digg thisPin on PinterestShare on RedditShare on StumbleUponPrint this pageEmail this to someone

Leave a Reply

Be the First to Comment!

avatar
wpDiscuz