ArrayList or LinkedList?

This article provides guidance to Java developers in choosing the appropriate sequential data structure.

ArrayList and LinkedList are two classes of the Java Collection Framework used for storing lists of object references. ArrayList and  LinkedList both implement the List interface. Let's first try to understand their most important parent interface List (which).

List Interface

A list is simply an ordered collection of elements (also known as a sequence). It adds position-oriented operations useful for quickly accessing, adding, and removing elements at a specific index position on the list. List interface has Collection and Iterable as super-interfaces. It can allow storing duplicates and null values. It provides indexed access to its element.

Usage

Below is the code snippet of declaring ArrayList and LinkedList using the List interface.

import java.util.*;

public class MyClass {

  // Unsynchronized or Not thread safe

  List<Object> arrayList = new ArrayList<>(); // declares an array list

  List<Object> linkedList = new LinkedList(); // declares a linked list   

    // ensures thread safety 

  List<Object> tsArrayList = Collections.synchronizedList(new LinkedList<>());

  List<Object> tsLinkedList = Collections.synchronizedList(new LinkedList<>());   

}

Vector is similar to ArrayList except they are provided with automatic synchronization, which makes them thread-safe but causes some performance overhead.

Internal Implementation 

Linked List

The LinkedList data structure contains an ordered set of data elements (know as nodes) such that each element contains a link or reference to its successor (next element). The last element (or tail) of the sequence points to a null element. The linked list itself contains a reference to the first element of the list, which is called the head element. LinkedList in Java is a doubly-linked list implementation of the List interface. In a doubly-linked list, every node points to its previous and next node. Other interfaces it implements are Serializable, Cloneable, and Deque (with super-interface as Queue). 

ArrayList

ArrayList is a resizable-array implementation of the List interface. It is internally implemented as an object array, which can increase the size as necessary to support more number of elements in the collection. It is possible to specify the initial capacity of an ArrayList through the constructor ArrayList(int initialCapacity)  and later increases the capacity using  void ensureCapacity(int minCapacity), if necessary, to ensure that it can hold at least the number of elements specified by the minimum capacity argument.

It also includes a method void trimToSize()to reduce the size based on existing elements.

// calling constructure ArrayList<type>(initialCapacity)
List arr = new ArrayList<Integer>(10);

By default, an creates a list of initial capacity 10, while LinkedList only constructs an empty list without any initial capacity.  LinkedList does not implement the RandomAccess interface, whereas implements the interface (instead of Deque interface).

Space and Time Complexity of Various Operations

Tips

Consider the following code examples for traversing aLinkedList The code below would be very slow as LinkedList does not support random access and there is a huge overhead while traversing for each iteration.

LinkedList ll = new LinkedList();
…
…
Object o = null;
for (int i = 0; i < list.size(); i++)
{
o = list.get(i);
…
}

A better approach for improved performance would be to use the following code instead.

LinkedList ll = new LinkedList();
…
…
Object o = null;
ListIterator li = list.listIterator(0);
while (li.hasNext()){
o = ll.next();
…
}

Conclusion

An ArrayList is faster and better as it supports random access to its elements. Traversing a linked list or inserting an item in the middle is very expensive as you have to iterate over each item and is very likely to have cache misses. If you need to perform processing on multiple items of the list in a single iteration then the overhead of iterations can be lesser inLinkedList than that of anArrayList which involves copying array element multiple times.

To share your experience and more insights on this topic, please leave your thoughts in the comments section below.