Java LinkedBlockingDeque (+ Code Examples)

In this part of the tutorial series, you will learn everything about LinkedBlockingDeque:

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

We are here in the class hierarchy:

LinkedBlockingDeque Characteristics

The java.util.concurrent.LinkedBlockingDeque class is based on a linked list – just like ConcurrentLinkedDeque – but is bounded (has a maximum capacity) and blocking.

LinkedBlockingDeque is the deque counterpart to LinkedBlockingQueue and has similar characteristics accordingly:

• It is based on a doubly linked list.
• Thread safety is guaranteed by a single ReentrantLock shared by all enqueue and dequeue operations (LinkedBlockingQueue, on the other hand, uses two locks – one enqueue lock and one dequeue lock).
• Unlike ConcurrentLinkedDeque, the deque’s size is stored in a field instead of being calculated by counting the list nodes each time size() is called. Thus, the time complexity of the size() method is O(1).
• 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 blocked).

The deque characteristics in detail:

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

I recommend LinkedBlockingDeque if you need a blocking thread-safe deque.

For all other use cases, check out the article “Deque Implementations – Which One to Use?”.

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 plan 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 extract, 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();

  public static void main(String[] args) 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 1 seconds (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.

We now write faster than we read, so that after 10.5 s, thread 1 blocks at the full deque when putLast() is called, and after 11.5 s, thread 4 blocks at the full deque when putFirst() is called.

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.

Summary and Outlook

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

This article was about the last of the four deque implementations. In the next part of the series, I’ll help you decide when to use which deque implementation.