Java LinkedList as Deque
(+ Code Examples)

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

• What are the characteristics of LinkedList?
• 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 Characteristics as Deque

The java.util.LinkedList class implements a classic doubly linked list.

It has existed in the JDK since version 1.2, significantly longer than the Deque interface it implements. The Deque-specific methods were added with the introduction of Deque in Java 6.

The characteristics in detail:

¹ Fail-fast: The iterator throws a ConcurrentModificationException if elements are inserted into or removed from the deque during iteration.

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.

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 (e.g., if you mainly remove and insert elements in the middle – though that is not in the role of a deque), then I would advise you to compare the performance of LinkedList for your specific use case with alternative data structures.

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 header and trailer 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 {
  public static void main(String[] args) {
    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());
  }
}
Code language: Java (java)

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
Code language: plaintext (plaintext)

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 linked list, the length of the list is irrelevant for inserting and removing elements. 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)

Summary and Outlook

In this article, you learned everything about the Deque implementation LinkedList.

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

If you still have questions, please ask them via the comment function. Do you want to be informed about new tutorials and articles? Then click here to sign up for the HappyCoders.eu newsletter.