Java ConcurrentLinkedDeque (+ Code Examples)

In this article, you will learn everything about the java.util.concurrent.ConcurrentLinkedDeque class:

• What are the characteristics of ConcurrentLinkedDeque?
• When should you use it?
• How to use it (Java example)?

We are here in the class hierarchy:

ConcurrentLinkedDeque Characteristics

ConcurrentLinkedDeque is the deque counterpart of ConcurrentLinkedQueue and shares its characteristics:

• It is based on a doubly linked list.
• Thread safety is guaranteed by optimistic locking in the form of non-blocking compare-and-set (CAS) operations on separate VarHandles for the head and tail of the deque and the list node references.
• To determine the length of a ConcurrentLinkedDeque, we need to count the linked list’s elements. The cost of this operation grows proportionally with the list size. The time complexity is, therefore: O(n)
• Due to the high cost of size calculation, ConcurrentLinkedDeque is unbounded.

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: All elements that exist when the iterator is created are traversed by the iterator exactly once. Changes that occur after this can, but do not need to, be reflected by the iterator.

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 Example

The following example (ConcurrentLinkedDequeExample class on GitHub) demonstrates the thread safety of ConcurrentLinkedDeque. Four writing and three reading threads concurrently insert and extract elements from random pages 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;

  public static void main(String[] args) 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 from both sides 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.

Summary and Outlook

In this part of the tutorial series, you learned about the thread-safe linked list-based ConcurrentLinkedDeque and its characteristics.

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