--- title: Java LinkedList url: https://blog.octoperf.com/java-linkedlist/ date: '2018-03-19' authors: - jloisel categories: - Development tags: - Java - Tutorial description: Java's LinkedList is a doubly-linked List implementation. Lists are ordered sequences of objects. Learn how and when a LinkedList should be used. --- # Java LinkedList The question which often arises is: are [LinkedList](https://docs.oracle.com/javase/7/docs/api/java/util/LinkedList.html) 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](https://en.wikipedia.org/wiki/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. ## How Linked List works ![Doubly Linked List](https://blog.octoperf.com/img/blog/java-linkedlist/doubly-linked-list.png) A [Doubly Linked List](https://en.wikipedia.org/wiki/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 ![Class Hierarchy inside JDK](https://blog.octoperf.com/img/blog/java-linkedlist/type-hierarchy.png) 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](https://docs.oracle.com/javase/tutorial/java/nutsandbolts/arrays.html) 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. ```java 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`. ```java public class LinkedList extends AbstractSequentialList implements List, Deque, 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 first; /** * Pointer to last node. * Invariant: (first == null && last == null) || * (last.next == null && last.item != null) */ transient Node 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](https://en.wikipedia.org/wiki/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 ```java 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 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](https://docs.oracle.com/javase/7/docs/api/java/util/Collection.html). It creates a copy of the passed collection: ```java @Test public void shouldCopy() { final List another = new LinkedList<>(); another.add("Hello World!"); final List 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. ```java @Test public void shouldAddElements() { final List 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] ```java @Test public void shouldAddStream() { final List 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](https://docs.oracle.com/javase/8/docs/api/java/util/stream/package-summary.html) and [Lambdas expressions](https://docs.oracle.com/javase/tutorial/java/javaOO/lambdaexpressions.html). ## Removing Elements Removing elements is pretty straight forward: ```java @Test public void shouldRemoveElements() { final List 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 ```java @Test public void shouldIterate() { final List 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 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](https://docs.oracle.com/javase/8/docs/api/?java/lang/Iterable.html) 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](https://docs.oracle.com/javase/7/docs/api/java/util/Set.html). The complexity of this operation is `0(n)`. ```java @Test public void shouldSearch() { final List 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](https://en.wikipedia.org/wiki/Binary_search_algorithm) must be avoided on `LinkedList` because it seeks elements by index which is inefficient on this kind of lists. ```java @Test public void shouldSearch() { final List 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)`): ```java public static int binarySearch(List> list, T key) { if (list instanceof RandomAccess || list.size()