Java LinkedList – List and Deque: Methods, Example, ArrayDeque

In this article, you will learn all about the Java class LinkedList in its role as a deque:

• What are the characteristics of LinkedList?
• Which methods come from which interface?
• When should you use it as a deque?
• How to use it as a deque (Java example)?
• What are the time complexities of the LinkedList operations?

We are here in the class hierarchy:

LinkedList is the only class in this diagram that implements a second collection interface besides Deque: List. Since Java 21, both Deque and List also extend the SequencedCollection interface. This gives LinkedList the reversed() method, which returns a reverse-ordered view of the list. What this means for a deque is explained in the article Queue vs. Deque.

LinkedList Characteristics as Deque

The java.util.LinkedList class implements a classic doubly linked list – and with it the two interfaces List and Deque.

It has existed in the JDK since version 1.2, significantly longer than the Deque interface it implements. It already had some of the deque methods before; the others were added with the introduction of Deque in Java 6. The section LinkedList Methods and Their Interfaces shows which method comes from where.

null elements are allowed. That is why a null returned by pollFirst() or peekFirst() can mean two things: the deque is empty, or the element at its head is null. For this reason, the Javadoc of the Deque interface strongly discourages inserting null into a deque, even if the implementation permits it.

The characteristics in detail:

Underlying data structure	Thread-safe?	Blocking/ non-blocking	Bounded/ unbounded	Iterator type
Linked list	No	Non-blocking	Unbounded	Fail-fast¹

¹ Fail-fast: The iterator throws a ConcurrentModificationException if elements are inserted into or removed from the deque during iteration – except through the iterator’s own remove() and add() methods.

LinkedList Methods and Their Interfaces

LinkedList is older than Queue and Deque. Some of its methods therefore existed before any interface declared them. The following table shows since which Java version LinkedList has a method and which interface declares it today:

Methods	In LinkedList since	Declared by
addFirst(), addLast(), getFirst(), getLast(), removeFirst(), removeLast()	Java 1.2	Deque (since Java 6), List and SequencedCollection (since Java 21)
offer(), peek(), poll(), element(), remove()	Java 5	Queue
offerFirst(), offerLast(), peekFirst(), peekLast(), pollFirst(), pollLast(), push(), pop(), removeFirstOccurrence(), removeLastOccurrence(), descendingIterator()	Java 6	Deque
reversed()	Java 21	Deque, List, SequencedCollection

So addFirst() was not invented by the Deque interface: LinkedList already had the method in Java 1.2. Java 6 adopted it into Deque, and Java 21 also into List and SequencedCollection.

Recommended Use as a Deque

I generally advise against using LinkedList as a deque. You can find the reasons in the article “Difference between Array and Linked List”. In summary:

• An array requires significantly less memory than a linked list.
• Accessing the elements of an array is faster than accessing those of a linked list.
• Linked lists are “hard to digest” for the garbage collector.

The Javadoc of ArrayDeque says so as well: when used as a queue, the class is “likely to be faster than LinkedList”.

If you need a list, ArrayList is usually the better choice.

If you need a non-thread-safe deque (or a non-thread-safe queue), use an ArrayDeque.

Of course, these are only general recommendations. If you have reasons for using a LinkedList, I advise you to compare the performance of LinkedList for your specific use case with alternative data structures. For example, you might mainly insert and remove elements in the middle – but then the list is not in the role of a deque.

LinkedList Deque Example

In the following example, you can see how to use a LinkedList in Java. The sample code shows how to create a LinkedList, how to fill it with random elements, how to print the head and tail elements, and how to remove the elements from the LinkedList.

If you have read the ArrayDeque tutorial, the demo should look familiar to you. Since both ArrayDeque and LinkedList are non-blocking and not thread-safe, I can only demonstrate the basic deque functions for both implementations.

You can find the code in the LinkedListDemo class in the GitHub repo.

public class LinkedListDemo {
  static void main() {
    Deque<Integer> deque = new LinkedList<>();

    for (int i = 0; i < 8; i++) {
      int element = ThreadLocalRandom.current().nextInt(10, 100);
      if (ThreadLocalRandom.current().nextBoolean()) {
        deque.offerFirst(element);
        System.out.println("deque.offerFirst(" + element + ") --> deque = " + deque);
      } else {
        deque.offerLast(element);
        System.out.println("deque.offerLast(" + element + ")  --> deque = " + deque);
      }
    }

    System.out.println();
    System.out.println("deque.isEmpty()   = " + deque.isEmpty());
    System.out.println("deque.peekFirst() = " + deque.peekFirst());
    System.out.println("deque.peekLast()  = " + deque.peekLast());
    System.out.println();

    while (!deque.isEmpty()) {
      if (ThreadLocalRandom.current().nextBoolean()) {
        System.out.println("deque.pollFirst() = " + deque.pollFirst()
            + " --> deque = " + deque);
      } else {
        System.out.println("deque.pollLast()  = " + deque.pollLast()
            + " --> deque = " + deque);
      }
    }

    System.out.println();
    System.out.println("deque.isEmpty()   = " + deque.isEmpty());
    System.out.println("deque.peekFirst() = " + deque.peekFirst());
    System.out.println("deque.peekLast()  = " + deque.peekLast());
  }
}

Here is an example output:

deque.offerLast(80)  --> deque = [80]
deque.offerLast(61)  --> deque = [80, 61]
deque.offerLast(63)  --> deque = [80, 61, 63]
deque.offerFirst(30) --> deque = [30, 80, 61, 63]
deque.offerLast(11)  --> deque = [30, 80, 61, 63, 11]
deque.offerLast(33)  --> deque = [30, 80, 61, 63, 11, 33]
deque.offerLast(30)  --> deque = [30, 80, 61, 63, 11, 33, 30]
deque.offerFirst(90) --> deque = [90, 30, 80, 61, 63, 11, 33, 30]

deque.isEmpty()   = false
deque.peekFirst() = 90
deque.peekLast()  = 30

deque.pollFirst() = 90 --> deque = [30, 80, 61, 63, 11, 33, 30]
deque.pollFirst() = 30 --> deque = [80, 61, 63, 11, 33, 30]
deque.pollFirst() = 80 --> deque = [61, 63, 11, 33, 30]
deque.pollFirst() = 61 --> deque = [63, 11, 33, 30]
deque.pollLast()  = 30 --> deque = [63, 11, 33]
deque.pollLast()  = 33 --> deque = [63, 11]
deque.pollLast()  = 11 --> deque = [63]
deque.pollFirst() = 63 --> deque = []

deque.isEmpty()   = true
deque.peekFirst() = null
deque.peekLast()  = null

Looking at the output line by line, you will quickly understand how LinkedList works.

LinkedList Time Complexity

(You can find an introduction to time complexity in the article “Big O Notation and Time Complexity – Easily Explained”.)

In a doubly linked list, the length of the list is irrelevant for inserting and removing elements at the beginning and at the end. The cost for both operations is therefore constant.

Thus, the time complexity for the enqueue and dequeue operations is: O(1)

The situation is usually different for determining the size of a linked list. You must traverse the entire list from front to back to count its elements.

Fortunately, this is not the case with the Java LinkedList. It stores its size in an additional field and updates this field with every insert and delete operation.

So the time complexity for LinkedList.size() is also: O(1)

All operations that search for or remove an element in the middle – contains(), remove(Object), removeFirstOccurrence(), and removeLastOccurrence() – run in O(n), on the other hand. The same applies to the index access get(i) from the List interface: for it, LinkedList traverses the list from whichever end is closer.

Summary and Outlook

In this article, you got to know the Deque implementation LinkedList: a doubly linked list that implements both List and Deque and allows null. As a deque, ArrayDeque is almost always the better choice – LinkedList pays off only if you also need the same data structure as a List.

In the next part of this series, we will get to the first thread-safe Deque implementation: ConcurrentLinkedDeque.