Java LinkedList

The question which often arises is: are LinkedList preferable to ArrayList? In which case should I use it?

As explained in the Java documentation, LinkedList is:

• A doubly-linked chain: elements are stored in nodes, with linking back and forth between themselves,
• Mutable: objects can be added and/or removed,
• Not Thread-safe: LinkedList is not suitable for concurrent access. See Thread Safety for more information.

Let's explore how to use a LinkedList through simple code examples! And find out when a LinkedList instead of an ArrayList should be used.

Need professional services?

Rely on our Expertise

How Linked List works

A Doubly Linked List consists of a sequence of nodes. Each node points to the previous and the next node. Sentinel nodes are used to keep a reference on both first and last node.

Type Hierarchy

The LinkedList inherits from:

• java.util.AbstractList,
• java.util.Object,
• and implements java.util.List, java.util.Collection.

List is a subtype of Collection with guaranteed order of insertion.

Properties

The Java LinkedList has the following properties:

• Can contain duplicate elements (i.e. elements which are equals),
• Maintains the order of insertion,
• is not synchronized (thus not thread-safe),
• Random access (through an integer index) are slow (0(n/2) on average),
• Element removal is fast because elements are stored in nodes which can be removed quickly (change links from preceding and next nodes),
• Element insertion is efficient because only a new node must be allocated (no array resize like with LinkedList).

Methods

The following table lists LinkedList most commonly used methods:

Method	Description
void add(int index, Object element)	Inserts an element at a given index
boolean addAll(Collection c)	Appends all the elements contained in the passed collection
void clear()	Empties the list
int lastIndexOf(Object o)	Returns last index of given object, or -1 if not found
Object[] toArray()	Creates an array with a copy of all objects within the list
boolean add(Object o)	Appends the passed object to the list
boolean addAll(int index, Collection c)	Inserts all elements at the given index
Object clone()	Creates a shallow copy of the list (elements within are not cloned)
int indexOf(Object o)	Index of the object being passed, or -1 if not found
int size()	Number of elements the list contains

Comparison with Arrays

Arrays is a primitive structure designed to hold a fixed number of objects. It's possible but quite difficult to resize an array (the code is usually pretty ugly too). For this reason, a LinkedList is much more convenient than an Array when you need to add/remove objects without knowing the exact collection size.

package com.octoperf;

import org.junit.Test;

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

import static org.junit.Assert.assertFalse;
import static org.junit.Assert.assertTrue;

public class LinkedListTest {

  @Test
  public void shouldArray() {
    final String[] arr = new String[0];
    assertTrue(arr.length == 0);
  }
}

In the code above, we show how to create an empty array in Java. The code asserts the array length is zero. Now, let's see how the code differs when using a LinkedList.

public class LinkedList<E>
    extends AbstractSequentialList<E>
    implements List<E>, Deque<E>, Cloneable, java.io.Serializable
{
    transient int size = 0;

    /**
     * Pointer to first node.
     * Invariant: (first == null && last == null) ||
     *            (first.prev == null && first.item != null)
     */
    transient Node<E> first;

    /**
     * Pointer to last node.
     * Invariant: (first == null && last == null) ||
     *            (last.next == null && last.item != null)
     */
    transient Node<E> last;

    /**
     * Constructs an empty list.
     */
    public LinkedList() {
    }

A LinkedList by default contains absolutely nothing. It has two pointers first and last pointing respectively to the first and last node of the list.

For this reason, adding elements to a LinkedList is much more efficient than adding elements into a Array.

Algorithmic Complexity

Before we dive into the code, let's see the most common operations this List performs algorithmically speaking. We're going to use the Big O-Notation to describe code complexity here.

Operation	Complexity
add(object o)	0(1)
add(object o, int index)	0(n)
remove(int index)	0(n)
remove(object o)	0(n)
size()	0(n)
contains(object o)	0(n)

Being based on an doubly linked chain, LinkedList is best suited for heavily adding / removing elements. Also, beware of evaluating a LinkedList size because it's costly operation. (while LinkedList.size() complexity is 0(1))

Constructors

package com.octoperf;

import org.junit.Test;

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

import static org.junit.Assert.assertFalse;
import static org.junit.Assert.assertTrue;

public class LinkedListTest {

  @Test
  public void shouldCreate() {
    final List<String> list = new LinkedList<>();
    assertTrue(list.isEmpty());
    assertFalse(list.iterator().hasNext());
  }
}

In the code above, we instantiate a new LinkedList, which is empty by default.

You can also create a list by passing another Collection. It creates a copy of the passed collection:

@Test
public void shouldCopy() {
  final List<String> another = new LinkedList<>();
  another.add("Hello World!");

  final List<String> list = new LinkedList<>(another);
  assertFalse(list.isEmpty());
  assertTrue(list.contains("Hello World!"));

  another.clear();
  assertTrue(list.contains("Hello World!"));
}

The created List contains now contains a copy of all the elements the passed collection contains. Even if you clear the original collection, the element remains in the LinkedList.

Adding Elements

Elements can be added at the beginning, at the end one by one or multiples elements at once.

@Test
public void shouldAddElements() {
  final List<String> list = new LinkedList<>();
  list.add("John Smith");
  list.add("John Doe");
  list.add(0, "Donald Trump");
  list.addAll(ImmutableList.of("Barack Obama"));

  System.out.println(list);
}

The output is:

[Donald Trump, John Smith, John Doe, Barack Obama]

@Test
public void shouldAddStream() {
  final List<String> list = new LinkedList<>();

  ImmutableList.of("John Smith", "John Doe").forEach(list::add);

  System.out.println(list);
}

The output is:

[John Smith, John Doe]

The code above shows adding elements to the list using Java Streams and Lambdas expressions.

Removing Elements

Removing elements is pretty straight forward:

@Test
public void shouldRemoveElements() {
  final List<String> list = new LinkedList<>();
  list.add("John Smith");
  list.add("John Doe");

  list.remove("John Smith");

  System.out.println(list);
}

The following code prints:

[John Doe]

As the add operations, multiple elements can be removed at once.

Iterating

@Test
public void shouldIterate() {
  final List<String> list = new LinkedList<>();
  list.add("John Smith");
  list.add("John Doe");

  // Foreach loop
  for (final String name : list) {
    System.out.println(name);
  }

  // Traditional for loop
  for (int i = 0; i < list.size; i++) {
   System.out.println(list.get(i)); 
  }

  // Java Stream
  list.forEach(System.out::println);

  // Through iterator
  final Iterator<String> it = list.iterator();
  while (it.hasNext()) {
    System.out.println(it.next());
  }
}

The following code shows 4 different ways to iterate over list elements:

• Foreach Loop: as List implements Iterable interface, lists can be iterated directly in for loops,
• For Loop: traditional for loops using an integer index,
• Java Streams: using Stream API introduced in Java 8,
• Iterator: using list iterator.

These methods are roughly equivalent in term of performance. It depends on the context how you would iterate over the list.

Searching

One should be aware that Lists are not very well suited for search operations, except for sorted lists.

Unsorted List

When searching an unsorted list, the algorithm is pretty inefficient: it scans the whole list to find the wanted element. If you need to perform frequent searches in a collection, prefer a Set. The complexity of this operation is 0(n).

@Test
public void shouldSearch() {
  final List<String> list = new LinkedList<>();
  list.add("John Smith");
  list.add("John Doe");

  assertEquals(1, list.indexOf("John Doe"));
  assertTrue(list.stream().anyMatch("John Doe"::equals));
}

Sorted List

binary search algorithm must be avoided on LinkedList because it seeks elements by index which is inefficient on this kind of lists.

@Test
public void shouldSearch() {
  final List<String> list = new LinkedList<>();
  list.add("John Smith");
  list.add("John Doe");

  Collections.sort(list);
  assertEquals(0, Collections.binarySearch(list, "John Doe"));
}

Gladly enough, the Java binary search is capable of understanding this list does not support random access and switch to iterative search (O(n)):

public static <T>
    int binarySearch(List<? extends Comparable<? super T>> list, T key) {
        if (list instanceof RandomAccess || list.size()<BINARYSEARCH_THRESHOLD)
            return Collections.indexedBinarySearch(list, key);
        else
            return Collections.iteratorBinarySearch(list, key);
    }

Best Use-Cases

LinkedList is best suited when:

• Adding or Removing elements: only requires to move a few pointers for nodes around. ArrayList performs worse here because it needs to resize the internal array when growing (and copy all elements into it),
• Reusing Iterators to insert / remove elements at specific index: These operations can be done in O(1) (where ArrayList needs to copy the internal array and shift all elements),

On the other side, LinkedList performs badly when:

• Seeking an element by index: this operation takes O(n/2) on average,
• Evaluating the list size: costs O(n) in all cases.

Alternatives

LinkedList is not the only implementation of the Java List interface. In fact there is also:

• ArrayList: Array-based list implementation,
• Vector: synchronized implementation based on a growable array of objects,
• Stack: specialization of a Vector with LIFO strategy (Last In, First Out).

Depending on the nature of the operations frequently executed on the list instance, you should consider using one of these alternatives.

ArrayList is best suited for storing a fixed amount of elements, or when you need to evaluate list size frequently.

Vector is best suited in code executed concurrently by multiple threads because it's synchronized. This data structure is pretty old (since JDK 1.0) and not used much these days.

Stack is great when you need to pop elements in the reverse order they have been pushed.

Want to become a super load tester?

Request a Demo