A Guide to the Java LinkedList

1. Introduction

LinkedList is a doubly-linked list implementation of the List and Deque interfaces. It implements all optional list operations and permits all elements (including null).

2. Features

Below you can find the most important properties of the LinkedList:

• Operations that index into the list will traverse the list from the beginning or the end, whichever is closer to the specified index
• It is not synchronized
• Its Iterator and ListIterator iterators are fail-fast (which means that after the iterator’s creation, if the list is modified, a ConcurrentModificationException will be thrown)
• Every element is a node, which keeps a reference to the next and previous ones
• It maintains insertion order

Although LinkedList is not synchronized, we can retrieve a synchronized version of it by calling the Collections.synchronizedList method, like:

List list = Collections.synchronizedList(new LinkedList(...));

3. Comparison to ArrayList

Although both of them implement the List interface, they have different semantics – which will definitely affect the decision of which one to use.

3.1. Structure

An ArrayList is an index-based data structure backed by an Array. It provides random access to its elements with a performance equal to O(1).

On the other hand, a LinkedList stores its data as a list of elements, and every element is linked to its previous and next element. In this case, the search operation for an item has execution time equal to O(n).

3.2. Operations

The insertion, addition and removal operations of an item are faster in a LinkedList because there is no need to resize an array or update the index when an element is added to some arbitrary position inside the collection, only references in surrounding elements will change.

3.3. Memory Usage

A LinkedList consumes more memory than an ArrayList because of every node in a LinkedList stores two references, one for its previous element and one for its next element, whereas ArrayList holds only data and its index.

4. Different Methods to Initialize a LinkedList

We can initialize a LinkedList using one of two constructors. Further, we use constructors to initialize new instances of a class.

4.1. Initializing an Empty LinkedList

We use the empty LinkedList() constructor to initialize an empty LinkedList.

Let’s demonstrate an example of a LinkedList parameterized over String using generics.

Let’s use a JUnit 5 test to verify the empty LinkedList:

@Test
public void whenInitializingLinkedList_ShouldReturnEmptyList() throws Exception {
    LinkedList<String> linkedList=new LinkedList<String>();     
    Assertions.assertTrue(linkedList.isEmpty());
}

Accordingly, we can add String elements to this list:

linkedList.addFirst("one");
linkedList.add("two");
linkedList.add("three");

Likewise, we can initialize a LinkedList of any class type.

4.2. Initializing a LinkedList From a Collection

We can also use the LinkedList(Collection<? extends E> c) constructor when we want to initialize a LinkedList whose elements are the elements of a given Collection. It adds the elements in the order in which the Collection‘s iterator returns them.

Let’s demonstrate an example of a LinkedList parameterized over  Integer using generics. However, first, we create a Collection to use as the argument when we invoke the constructor. Let’s create a Collection of type ArrayList parameterized over Integer using generics:

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

 arrayList.add(Integer.valueOf(1));
 arrayList.add(Integer.valueOf(2));
 arrayList.add(Integer.valueOf(3));

Afterward, let’s call the constructor to initialize a LinkedList:

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

Again, let’s use a JUnit 5 test to verify the LinkedList derives its elements from the ArrayList it is constructed from:

@Test
public void whenInitializingListFromCollection_ShouldReturnCollectionsElements() throws Exception {
    ArrayList<Integer> arrayList=new ArrayList<Integer>(3);
        
    arrayList.add(Integer.valueOf(1));
    arrayList.add(Integer.valueOf(2));
    arrayList.add(Integer.valueOf(3));
 
    LinkedList<Integer> linkedList=new LinkedList<Integer>(arrayList);

    Object[] linkedListElements = linkedList.toArray();
    Object[] collectionElements = arrayList.toArray();

    Assertions.assertArrayEquals(linkedListElements,collectionElements);
}

Similarly, we can initialize LinkedList using any Java Collection. Accordingly, the elements of the LinkedList initialized from a Collection are the type of the Collection‘s elements.

5. Usage

Here are some code samples that show how you can use LinkedList:

5.1. Creation

LinkedList<Object> linkedList = new LinkedList<>();

5.2. Adding Element

LinkedList implements List and Deque interface, besides standard add() and addAll() methods you can find addFirst() and addLast(), which adds an element in the beginning or the end, respectively.

5.3. Removing Element

Similar to element addition, this list implementation offers removeFirst() and removeLast().

Also, there are convenient methods, such as removeFirstOccurence() and removeLastOccurence(), which return a boolean (true if the collection contained the specified element).

5.4. Queue Operations

Deque interface provides queue-like behaviors (actually, Deque extends Queue interface):

linkedList.poll();
linkedList.pop();

Those methods retrieve the first element and remove it from the list.

The difference between poll() and pop() is that pop will throw NoSuchElementException() on empty list, whereas poll returns null. The APIs pollFirst() and pollLast() are also available.

Here’s, for example, how the push API works:

linkedList.push(Object o);

Which inserts the element as the head of the collection.

LinkedList has many other methods, most of which should be familiar to a user who already used Lists. Others that are provided by Deque might be a convenient alternative to “standard” methods.

The full documentation can be found here.

6. Insert an Element at a Specific Position in a LinkedList

When we want to add an element at a specific position in a LinkedList, we have several method options:

Let’s demonstrate using each of these methods. Further, let’s initialize an empty list:

LinkedList<String> linkedList=new LinkedList<String>();

Afterward, let’s add the first element using the method addFirst(E e):

linkedList.addFirst("one");

Although we can build the list by repeatedly calling the add(E e) method, we want to demonstrate the different options for adding an element at a specific position. Therefore, let’s add the last element in the list using the method addLast(E e):

linkedList.addLast("three");

Let’s call the add(E e) method to add an element to the end of the list built so far:

linkedList.add("four");

A LinkedList uses a 0-based index, which means that the first element is at index 0, the second element at index 1, the third element at index 2, and so on. To create a sequence, let’s add the element “two” at index position 1 using add(int index, E element):

linkedList.add(1,"two");

Let’s use a JUnit 5 test to verify we added the elements in the LinkedList at specific, respective positions:

@Test
public void whenAddingElementsInLinkedListAtSpecificPosition_ShouldReturnElementsInProperSequence() throws Exception {
    LinkedList<String> linkedList=new LinkedList<String>();
        
    linkedList.addFirst("one");
    linkedList.addLast("three");
    linkedList.add("four");
    linkedList.add(1,"two");

    Object[] linkedListElements = linkedList.toArray();
    Object[] expectedListElements = {"one","two","three","four"};

    Assertions.assertArrayEquals(linkedListElements,expectedListElements);
}

The JUnit test should pass, verifying that we added elements at specific positions in a LinkedList.

7. Converting an Array into a LinkedList

In some cases, we may have data in the form of an array, and we need to work with it as a LinkedList for efficient insertions or to take advantage of the Deque operations that LinkedList provides. Converting an array to a LinkedList is straightforward in Java.

First, let’s start with a sample array of elements:

String[] array = { "apple", "banana", "cherry", "date" };

We can convert this array into a LinkedList by passing it to the Arrays.asList() method and then creating a new LinkedList from the resulting List:

List<String> list = Arrays.asList(array);  // Convert array to List
LinkedList<String> linkedList = new LinkedList<>(list);

Now linkedList contains all the elements from the original array, and we can use any of the LinkedList operations on it.

Another approach to convert an array into a LinkedList is by using the Collections.addAll() method. This method provides a simple way to add all elements from an array directly into a LinkedList.

First, we create an empty LinkedList. Then we use the Collections.addAll() method to add each element from the array into the LinkedList:

LinkedList<String> linkedList = new LinkedList<>();
Collections.addAll(linkedList, array);

After this operation, linkedList contains all the elements from the array and it preserves the order.

8. Conclusion

ArrayList is usually the default List implementation.

However, there are certain use cases where using LinkedList will be a better fit, such as preferences for constant insertion/deletion time (e.g., frequent insertions/deletions/updates), over constant access time and effective memory usage.