Java LinkedBlockingDeque: Blocking Deque With a Single Lock

In this part of the tutorial series, you will learn everything about the java.util.concurrent.LinkedBlockingDeque class, which has been part of the JDK since Java 6 – the only implementation of the BlockingDeque interface in the JDK:

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

We are here in the class hierarchy:

Since Java 21, Deque also extends the SequencedCollection interface. This gives LinkedBlockingDeque the reversed() method, which returns a reverse-ordered view of the deque. That view is a Deque, not a BlockingDeque – the blocking methods such as takeFirst() are not available on it. What reversed() means for a deque is explained in the article Queue vs. Deque.

LinkedBlockingDeque Characteristics

The LinkedBlockingDeque class is based on a doubly linked list – just like ConcurrentLinkedDeque – but is blocking, optionally bounded, and thread-safe through a lock (see below).

LinkedBlockingDeque is the deque counterpart of LinkedBlockingQueue and shares its characteristics with one exception: Thread safety is provided by a single ReentrantLock that guards inserting and taking at both ends. (LinkedBlockingQueue uses two locks – one for inserting at the end, one for taking from the head.)

Whether the deque is bounded is decided when you create it: new LinkedBlockingDeque<>() creates a deque with the capacity Integer.MAX_VALUE – practically unbounded. new LinkedBlockingDeque<>(capacity) sets a limit; once it is reached, putFirst() and putLast() block, and offerFirst() and offerLast() return false.

LinkedBlockingDeque does not offer a fairness policy, i.e., blocking methods are served in undefined order. (With a fairness policy, they would be served in the order they were called.)

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

The deque characteristics in detail:

Underlying data structure	Thread-safe?	Blocking/ non-blocking	Fairness policy	Bounded/ unbounded	Iterator type
Doubly linked list	Yes (pessimistic locking with a single lock)	Blocking	Not available	Optionally bounded (default: 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().

Recommended Use Case

I recommend LinkedBlockingDeque if you need a blocking, thread-safe deque – that is, a deque at which a thread waits until an element is available or until there is room again. The JDK has no alternative for that: LinkedBlockingDeque is the only implementation of the BlockingDeque interface.

For all other use cases, check out the section “Deque Implementations in Java: Which One to Use?” in the Deque interface article.

LinkedBlockingDeque vs. ConcurrentLinkedDeque

If nothing should block, use ConcurrentLinkedDeque: It works without a lock and is faster under low to moderate contention. However, it is always unbounded, and its size() method traverses the entire list.

You need LinkedBlockingDeque as soon as a thread should wait for an element or for a free slot, or as soon as you need a capacity limit – for example, for a work queue between producer and consumer threads in which urgent jobs are put at the front with putFirst().

LinkedBlockingDeque Example

The following example shows how you can use LinkedBlockingDeque. It extends the LinkedBlockingQueue example in that it inserts/removes elements on a random side of the deque.

Here’s what happens in the example:

• First, we create a LinkedBlockingDeque with a capacity for three elements.
• Then we schedule ten dequeue operations that take elements from the deque at random sides every three seconds.
• We also schedule ten enqueue operations that start only after 3.5 seconds but then insert elements at a random side of the deque at intervals of only one second each.
• By starting enqueue operations later, we can see blocking dequeue operations at the beginning.
• Since we then insert much faster than we take, we quickly reach the deque’s capacity, therefore blocking enqueue threads.

You can find the code in the LinkedBlockingDequeExample class on GitHub.

public class LinkedBlockingDequeExample {
  private static final long startTime = System.currentTimeMillis();

  static void main() throws InterruptedException {
    BlockingDeque<Integer> deque = new LinkedBlockingDeque<>(3);
    ScheduledExecutorService pool = Executors.newScheduledThreadPool(10);

    // Start reading from the deque immediately, every 3 seconds
    for (int i = 0; i < 10; i++) {
      int delaySeconds = i * 3;
      pool.schedule(() -> dequeue(deque), delaySeconds, TimeUnit.SECONDS);
    }

    // Start writing to the deque after 3.5 seconds (so there are already 2
    // threads waiting), every second (so that the deque fills faster than
    // it's emptied, so that we see a full deque soon)
    for (int i = 0; i < 10; i++) {
      int element = i;
      int delayMillis = 3500 + i * 1000;
      pool.schedule(
          () -> enqueue(deque, element), delayMillis, TimeUnit.MILLISECONDS);
    }

    pool.shutdown();
    pool.awaitTermination(1, TimeUnit.MINUTES);
  }

  private static void enqueue(BlockingDeque<Integer> deque, int i) {
    if (ThreadLocalRandom.current().nextBoolean()) {
      enqueueAtFront(deque, i);
    } else {
      enqueueAtBack(deque, i);
    }
  }

  private static void enqueueAtFront(BlockingDeque<Integer> deque, int element) {
    log("Calling deque.putFirst(%d) (deque = %s)...", element, deque);
    try {
      deque.putFirst(element);
      log("deque.putFirst(%d) returned (deque = %s)", element, deque);
    } catch (InterruptedException e) {
      Thread.currentThread().interrupt();
    }
  }

  private static void enqueueAtBack(BlockingDeque<Integer> deque, int element) {
    log("Calling deque.putLast(%d) (deque = %s)...", element, deque);
    try {
      deque.putLast(element);
      log("deque.putLast(%d) returned (deque = %s)", element, deque);
    } catch (InterruptedException e) {
      Thread.currentThread().interrupt();
    }
  }

  private static void dequeue(BlockingDeque<Integer> deque) {
    if (ThreadLocalRandom.current().nextBoolean()) {
      dequeueAtFront(deque);
    } else {
      dequeueAtBack(deque);
    }
  }

  private static void dequeueAtFront(BlockingDeque<Integer> deque) {
    log("    Calling deque.takeFirst() (deque = %s)...", deque);
    try {
      Integer element = deque.takeFirst();
      log("    deque.takeFirst() returned %d (deque = %s)", element, deque);
    } catch (InterruptedException e) {
      Thread.currentThread().interrupt();
    }
  }

  private static void dequeueAtBack(BlockingDeque<Integer> deque) {
    log("    Calling deque.takeLast() (deque = %s)...", deque);
    try {
      Integer element = deque.takeLast();
      log("    deque.takeLast() returned %d (deque = %s)", element, deque);
    } catch (InterruptedException e) {
      Thread.currentThread().interrupt();
    }
  }

  private static void log(String format, Object... args) {
    System.out.printf(
        Locale.US,
        "[%4.1fs] [%-16s] %s%n",
        (System.currentTimeMillis() - startTime) / 1000.0,
        Thread.currentThread().getName(),
        String.format(format, args));
  }
}

Here you can see a sample output of the program:

[ 0.0s] [pool-1-thread-1 ]     Calling deque.takeLast() (deque = [])...
[ 3.0s] [pool-1-thread-4 ]     Calling deque.takeFirst() (deque = [])...
[ 3.5s] [pool-1-thread-2 ] Calling deque.putFirst(0) (deque = [])...
[ 3.5s] [pool-1-thread-2 ] deque.putFirst(0) returned (deque = [])
[ 3.5s] [pool-1-thread-1 ]     deque.takeLast() returned 0 (deque = [])
[ 4.5s] [pool-1-thread-5 ] Calling deque.putLast(1) (deque = [])...
[ 4.5s] [pool-1-thread-4 ]     deque.takeFirst() returned 1 (deque = [])
[ 4.5s] [pool-1-thread-5 ] deque.putLast(1) returned (deque = [])
[ 5.5s] [pool-1-thread-9 ] Calling deque.putLast(2) (deque = [])...
[ 5.5s] [pool-1-thread-9 ] deque.putLast(2) returned (deque = [2])
[ 6.0s] [pool-1-thread-3 ]     Calling deque.takeFirst() (deque = [2])...
[ 6.0s] [pool-1-thread-3 ]     deque.takeFirst() returned 2 (deque = [])
[ 6.5s] [pool-1-thread-7 ] Calling deque.putLast(3) (deque = [])...
[ 6.5s] [pool-1-thread-7 ] deque.putLast(3) returned (deque = [3])
[ 7.5s] [pool-1-thread-8 ] Calling deque.putFirst(4) (deque = [3])...
[ 7.5s] [pool-1-thread-8 ] deque.putFirst(4) returned (deque = [4, 3])
[ 8.5s] [pool-1-thread-8 ] Calling deque.putFirst(5) (deque = [4, 3])...
[ 8.5s] [pool-1-thread-8 ] deque.putFirst(5) returned (deque = [5, 4, 3])
[ 9.0s] [pool-1-thread-10]     Calling deque.takeFirst() (deque = [5, 4, 3])...
[ 9.0s] [pool-1-thread-10]     deque.takeFirst() returned 5 (deque = [4, 3])
[ 9.5s] [pool-1-thread-2 ] Calling deque.putLast(6) (deque = [4, 3])...
[ 9.5s] [pool-1-thread-2 ] deque.putLast(6) returned (deque = [4, 3, 6])
[10.5s] [pool-1-thread-1 ] Calling deque.putLast(7) (deque = [4, 3, 6])...
[11.5s] [pool-1-thread-4 ] Calling deque.putFirst(8) (deque = [4, 3, 6])...
[12.0s] [pool-1-thread-5 ]     Calling deque.takeFirst() (deque = [4, 3, 6])...
[12.0s] [pool-1-thread-1 ] deque.putLast(7) returned (deque = [3, 6, 7])
[12.0s] [pool-1-thread-5 ]     deque.takeFirst() returned 4 (deque = [3, 6, 7])
[12.5s] [pool-1-thread-9 ] Calling deque.putFirst(9) (deque = [3, 6, 7])...
[15.0s] [pool-1-thread-3 ]     Calling deque.takeFirst() (deque = [3, 6, 7])...
[15.0s] [pool-1-thread-4 ] deque.putFirst(8) returned (deque = [8, 6, 7])
[15.0s] [pool-1-thread-3 ]     deque.takeFirst() returned 3 (deque = [8, 6, 7])
[18.0s] [pool-1-thread-7 ]     Calling deque.takeLast() (deque = [8, 6, 7])...
[18.0s] [pool-1-thread-7 ]     deque.takeLast() returned 7 (deque = [9, 8, 6])
[18.0s] [pool-1-thread-9 ] deque.putFirst(9) returned (deque = [9, 8, 6])
[21.0s] [pool-1-thread-6 ]     Calling deque.takeLast() (deque = [9, 8, 6])...
[21.0s] [pool-1-thread-6 ]     deque.takeLast() returned 6 (deque = [9, 8])
[24.0s] [pool-1-thread-8 ]     Calling deque.takeLast() (deque = [9, 8])...
[24.0s] [pool-1-thread-8 ]     deque.takeLast() returned 8 (deque = [9])
[27.0s] [pool-1-thread-10]     Calling deque.takeLast() (deque = [9])...
[27.0s] [pool-1-thread-10]     deque.takeLast() returned 9 (deque = [])

In the beginning, you can see how the takeLast() and takeFirst() invocations block after 0 s and 3 s at the empty deque.

After 3.5 s and 4.5 s, we write elements to the deque, which are immediately removed by the previously blocked methods in threads 1 and 4.

The program writes faster than it reads. After 10.5 s, thread 1 therefore blocks at the full deque when calling putLast(), and after 11.5 s, thread 4 does as well when calling putFirst().

After 12 s, thread 5 removes an element so that thread 1 can continue and fill the deque again.

After 12.5 s, thread 9 blocks with putFirst() because the deque is still (or again) full.

After 15 s and 18 s, threads 3 and 7 each remove an element, allowing blocked threads 4 and 9 to insert an element in turn.

Then (at 21 s, 24 s, and 27 s), the remaining three elements are removed, and no new ones are inserted.

Is LinkedBlockingDeque Thread-Safe?

Yes, LinkedBlockingDeque is thread-safe.

Thread safety is provided by a single ReentrantLock, simply called lock in the source code. It guards both ends of the list – inserting as well as taking, at the head as well as at the end –, and two conditions hang off it: putFirst() and putLast() wait on notFull, takeFirst() and takeLast() on notEmpty.

The number of elements is kept in the field count, a volatile int. It is only written under the lock, which is why it does not have to be an AtomicInteger as in LinkedBlockingQueue; volatile ensures that size() reads the current value even without the lock.

LinkedBlockingQueue gets by with two locks because elements are only taken at its head and only inserted at its end: A consumer thread changes only the head of the list, a producer thread only its last node. A placeholder node without an element at the head ensures that these are two different nodes even when the queue is empty.

That does not work for a deque, because elements are inserted and taken at each end. If each end had its own lock, takeFirst() and takeLast() could unlink the same node at the same time in a deque with exactly one element – both threads would get the same element, and count would be decremented twice. That is why a single lock guards both ends.

This comes at a price: Producer and consumer threads can block each other even when they work at different ends.

The following diagram shows the one lock that guards both ends of the list – in the example, a deque holding the elements 4 and 3, as after 7.5 s in the example output, into which a producer thread (on the left of the picture) inserts 5 at the front with putFirst(5) while a consumer thread (on the right) takes the last element with takeLast():

With low to moderate contention, optimistic locking, as ConcurrentLinkedDeque implements it via compare-and-set, is usually faster. Despite its name, optimistic locking works without any lock at all; a deque that works this way is therefore also called lock-free.

Under high contention, on the other hand, explicit locks have the edge. And only they can make a thread wait until an element or a free slot is available – a lock-free deque cannot block.

LinkedBlockingDeque Time Complexity

As with all deques based on linked lists, the time required for inserting and taking at both ends is independent of the length of the deque. The time complexity is, therefore, O(1).

That also applies to the size() method. Unlike ConcurrentLinkedDeque, which is also based on a linked list and runs through the entire list to count the elements each time size() is called, LinkedBlockingDeque uses the counter count, which is updated on insertion and removal, and thus keeps the size available in constant time.

contains(), remove(Object), removeFirstOccurrence(), and removeLastOccurrence(), on the other hand, are O(n) because in the worst case, they traverse the entire list. They hold the lock while doing so, so no other thread can insert or take in the meantime.

Summary and Outlook

In this part of the tutorial series, you learned about the doubly linked list-based LinkedBlockingDeque – thread-safe, blocking, and optionally bounded, the only implementation of the BlockingDeque interface in the JDK. It is thread-safe thanks to a single lock for both ends, so producer and consumer threads can block each other even at different ends; size() returns the size in O(1) thanks to the counter count.

This article was about the last of the four deque implementations. In the next part of the series, I’ll show you how to implement a deque using an array. When to use which deque implementation is explained in the Deque interface article.