Java ConcurrentLinkedDeque: Thread-Safe Deque Without Locks

In this article, you will learn everything about the java.util.concurrent.ConcurrentLinkedDeque class, which has been part of the JDK since Java 7:

• What are the characteristics of ConcurrentLinkedDeque?
• When should you use it – and when ConcurrentLinkedQueue?
• How to use it (Java example)?
• How does it achieve thread safety without a lock?

We are here in the class hierarchy:

Since Java 21, Deque also extends the SequencedCollection interface. This gives ConcurrentLinkedDeque the reversed() method, which returns a reverse-ordered view of the deque. What this means for a deque is explained in the article Queue vs. Deque.

ConcurrentLinkedDeque Characteristics

ConcurrentLinkedDeque is the deque counterpart of ConcurrentLinkedQueue and shares its characteristics with one exception: It is based on a doubly linked list. Besides the reference to its successor (next), each node also holds one to its predecessor (prev). This allows elements to be both inserted and removed at either end.

ConcurrentLinkedDeque is unbounded: A capacity limit would require a counter that is updated together with the list on every insertion and removal. LinkedBlockingDeque keeps exactly such a counter; the lock-free algorithm of ConcurrentLinkedDeque does without it. ConcurrentLinkedDeque does not offer blocking operations either.

null elements are not allowed (offerFirst(null) throws a NullPointerException) – which is why pollFirst() and pollLast() can unambiguously signal “deque empty” with the return value null.

The characteristics in detail:

Underlying data structure	Thread-safe?	Blocking/ non-blocking	Bounded/ unbounded	Iterator type
Doubly linked list	Yes (optimistic locking via compare-and-set)	Non-blocking	Unbounded	Weakly consistent¹

¹ Weakly consistent: The iterator returns exactly once every element that has been in the deque continuously since the iterator was created. It may reflect changes made after its creation – insertions as well as removals – but does not have to; it never throws a ConcurrentModificationException.

The iterator supports remove().

The individual operations at the two ends – offerFirst(), offerLast(), pollFirst(), and pollLast() – are atomic: Each of them takes effect for other threads at exactly one moment, the successful compare-and-set. Bulk operations such as addAll(), removeIf(), and forEach() are not: A forEach() running in parallel with addAll() may see only some of the new elements.

Recommended Use Case

ConcurrentLinkedDeque is a good choice when you need a thread-safe, non-blocking, unbounded deque.

No array-based alternative exists for this purpose. The only array-based deque, ArrayDeque, is not thread-safe.

ConcurrentLinkedDeque vs. ConcurrentLinkedQueue

If you only need a FIFO queue – insert at one end, remove at the other –, I recommend ConcurrentLinkedQueue. It works on the same lock-free principle but needs one reference less per node, because its list is only singly linked.

You need ConcurrentLinkedDeque as soon as you have to insert or remove at both ends – for example, for a thread-safe stack with push() and pop(), or for a work queue in which urgent jobs are put at the front with offerFirst().

ConcurrentLinkedDeque Example

The following example (ConcurrentLinkedDequeExample class on GitHub) demonstrates the thread safety of ConcurrentLinkedDeque. Four writing and three reading threads concurrently insert and remove elements at random ends of the deque.

public class ConcurrentLinkedDequeExample {

  private static final int NUMBER_OF_PRODUCERS = 4;
  private static final int NUMBER_OF_CONSUMERS = 3;
  private static final int NUMBER_OF_ELEMENTS_TO_PUT_INTO_DEQUE_PER_THREAD = 5;
  private static final int MIN_SLEEP_TIME_MILLIS = 500;
  private static final int MAX_SLEEP_TIME_MILLIS = 2000;

  private Deque<Integer> deque;
  private final CountDownLatch producerFinishLatch =
      new CountDownLatch(NUMBER_OF_PRODUCERS);
  private volatile boolean consumerShouldBeStoppedWhenDequeIsEmpty;

  static void main() throws InterruptedException {
    new ConcurrentLinkedDequeExample().runDemo();

    // We'll let the program end when all consumers are finished
  }

  private void runDemo() throws InterruptedException {
    createDeque();
    startProducers();
    startConsumers();
    waitUntilAllProducersAreFinished();

    consumerShouldBeStoppedWhenDequeIsEmpty = true;
  }

  private void createDeque() {
    deque = new ConcurrentLinkedDeque<>();
  }

  private void startProducers() {
    for (int i = 0; i < NUMBER_OF_PRODUCERS; i++) {
      createProducerThread().start();
    }
  }

  private Thread createProducerThread() {
    return new Thread(
        () -> {
          for (int i = 0; i < NUMBER_OF_ELEMENTS_TO_PUT_INTO_DEQUE_PER_THREAD; i++) {
            sleepRandomTime();
            insertRandomElementAtRandomSide();
          }

          producerFinishLatch.countDown();
        });
  }

  private void sleepRandomTime() {
    ThreadLocalRandom random = ThreadLocalRandom.current();
    try {
      Thread.sleep(random.nextInt(MIN_SLEEP_TIME_MILLIS, MAX_SLEEP_TIME_MILLIS));
    } catch (InterruptedException e) {
      Thread.currentThread().interrupt();
    }
  }

  private void insertRandomElementAtRandomSide() {
    ThreadLocalRandom random = ThreadLocalRandom.current();
    Integer element = random.nextInt(1000);
    if (random.nextBoolean()) {
      deque.offerFirst(element);
      System.out.printf(
          "[%s] deque.offerFirst(%3d)        --> deque = %s%n",
          Thread.currentThread().getName(), element, deque);
    } else {
      deque.offerLast(element);
      System.out.printf(
          "[%s] deque.offerLast(%3d)         --> deque = %s%n",
          Thread.currentThread().getName(), element, deque);
    }
  }

  private void startConsumers() {
    for (int i = 0; i < NUMBER_OF_CONSUMERS; i++) {
      createConsumerThread().start();
    }
  }

  private Thread createConsumerThread() {
    return new Thread(
        () -> {
          while (shouldConsumerContinue()) {
            sleepRandomTime();
            removeElementFromRandomSide();
          }
        });
  }

  private boolean shouldConsumerContinue() {
    return !(consumerShouldBeStoppedWhenDequeIsEmpty && deque.isEmpty());
  }

  private void removeElementFromRandomSide() {
    if (ThreadLocalRandom.current().nextBoolean()) {
      Integer element = deque.pollFirst();
      System.out.printf(
          "[%s]     deque.pollFirst() = %4d --> deque = %s%n",
          Thread.currentThread().getName(), element, deque);
    } else {
      Integer element = deque.pollLast();
      System.out.printf(
          "[%s]     deque.pollLast()  = %4d --> deque = %s%n",
          Thread.currentThread().getName(), element, deque);
    }
  }

  private void waitUntilAllProducersAreFinished() throws InterruptedException {
    producerFinishLatch.await();
  }
}

In the following, I have printed the first 15 lines of an exemplary program run:

[Thread-1] deque.offerFirst(295)        --> deque = [295]
[Thread-4]     deque.pollLast()  =  295 --> deque = []
[Thread-5]     deque.pollLast()  = null --> deque = []
[Thread-2] deque.offerLast(982)         --> deque = [982]
[Thread-3] deque.offerFirst(190)        --> deque = [190, 982]
[Thread-0] deque.offerFirst(522)        --> deque = [522, 190, 982]
[Thread-6]     deque.pollLast()  =  982 --> deque = [522, 190]
[Thread-1] deque.offerLast(543)         --> deque = [522, 190, 543]
[Thread-0] deque.offerFirst(506)        --> deque = [506, 522, 190, 543]
[Thread-5]     deque.pollLast()  =  543 --> deque = [506, 522, 190]
[Thread-4]     deque.pollFirst() =  506 --> deque = [522, 190]
[Thread-3] deque.offerLast(760)         --> deque = [522, 190, 760]
[Thread-2] deque.offerFirst( 46)        --> deque = [46, 522, 190, 760]
[Thread-6]     deque.pollLast()  =  760 --> deque = [46, 522, 190]
[Thread-1] deque.offerLast(312)         --> deque = [46, 522, 190, 312]

You can see how the seven threads insert and remove elements at both ends of the deque. In the third line, you can see how thread 5 got a null return value when it invoked pollLast(). That’s because the deque was empty at that point.

ConcurrentLinkedDeque Performance

This section covers the thread safety and time complexity of ConcurrentLinkedDeque.

Is ConcurrentLinkedDeque Thread-Safe?

Yes. Like ConcurrentLinkedQueue, ConcurrentLinkedDeque achieves thread safety through optimistic locking – and here, too, the word “locking” is misleading: The class does without any lock. It works with non-blocking compare-and-set (CAS) operations:

• offerFirst() attaches the new node to the prev reference of the first node via compare-and-set, offerLast() to the next reference of the last node.
• pollFirst() and pollLast() use compare-and-set to set the item of the first or last node to null. At that moment, the element is removed; the node is unlinked from the list only afterward.

The head and tail pointers may lag behind. Without a lock, this cannot be avoided: A compare-and-set changes only one reference, but inserting changes two – the one at the end node and the head or tail pointer. Between the two steps, the pointer still points to the previous end node for other threads.

The class turns this into an advantage: A thread updates head or tail only if it had to step over at least one node on its way to the first or last node. Without contention, this happens only on every second insertion or removal – half of the compare-and-sets on the two pointers are saved, and these are exactly the fields that all threads working at the same end compete for.

A thread therefore does not rely on the two pointers but checks the node itself – prev == null means first node, next == null means last node – and otherwise keeps following the prev or next references.

The following diagram shows what happens when two threads insert at opposite ends at the same time, using values from lines 7 to 9 of the example output: Thread-0 issues its compare-and-set on prev of the first node 522, Thread-1 on next of the last node 190. The two compare-and-sets target different references, so both succeed, and no thread has to repeat its attempt. head and tail stay where they were, because neither thread had to step over a node.

Only threads inserting at the same end compete for the same reference. Then – as with ConcurrentLinkedQueue – only one compare-and-set succeeds, and the other thread repeats its attempt at the new end of the deque.

When accessing deques, low to moderate contention (access conflicts between multiple threads) is usually to be expected, since a thread usually does not access the deque continuously but first has to create the element to be inserted or process the removed element. With low to moderate contention, optimistic locking achieves a significant performance gain over pessimistic locking with implicit or explicit locks.

LinkedBlockingDeque, on the other hand, achieves thread safety with a single ReentrantLock that guards both ends together.

ConcurrentLinkedDeque Time Complexity

As with all deques based on linked lists, the cost of inserting and removing at both ends does not depend on the length of the deque. The time complexity is, therefore: O(1).

However, this does not apply to the size() method. To determine the length of the deque, size() has to iterate over all elements of the linked list. The longer the deque, the longer it takes to calculate its length. The time complexity of size() is, therefore: O(n).

And because other threads may insert and remove elements in the meantime, the result may already be outdated by the time it is returned – which is why the Javadoc considers size() of little use in concurrent applications. To find out whether the deque is empty, use isEmpty(): It only looks for the first element and does not count any further.

(Here, you can find an introduction to the topic of time complexity.)

Summary and Outlook

In this part of the tutorial series, you learned about the thread-safe ConcurrentLinkedDeque based on a doubly linked list: lock-free via compare-and-set, unbounded, with size() in O(n). If you only need a FIFO queue, use ConcurrentLinkedQueue.

Next, I’ll introduce you to the only blocking deque, LinkedBlockingDeque.