Java ConcurrentLinkedDeque: Non-blocking Thread-safe Deque

ConcurrentLinkedDeque is an unbounded, thread-safe double-ended queue in java.util.concurrent that lets many threads add and remove elements at both ends without locks. It was added in Java 7, and it uses compare-and-swap (CAS) instructions instead of locks, so a thread never waits for another thread to finish its operation.

We use ConcurrentLinkedDeque when several threads share a collection that they use as a stack, a queue or both, for example a pool of pending jobs that workers take from either end. Its methods never block. When the deque is empty, a call either returns null or throws an exception, depending on the method.

The following example shows the main operations on both ends, with the result of each call.

ConcurrentLinkedDeque<String> jobs = new ConcurrentLinkedDeque<>();
jobs.offerLast("job-1");
jobs.offerLast("job-2");
jobs.offerFirst("urgent");
String head = jobs.peekFirst();                  // "urgent"
String tail = jobs.pollLast();                   // "job-2"
String next = jobs.pollFirst();                  // "urgent"
int remaining = jobs.size();                     // 1
String nothing = new ConcurrentLinkedDeque<String>().pollFirst();   // null

Notice that peekFirst() only reads the head, whereas the poll methods remove what they return. The sections that follow cover the method families, the multithreaded example with 100 adding and 100 removing threads, the limits of size() and iteration, a work-stealing scenario and a comparison with the other deques.

1. What Is ConcurrentLinkedDeque?

A ConcurrentLinkedDeque is a doubly linked list of nodes. Each thread that adds or removes an element changes the links at one end with a CAS instruction, which succeeds only if no other thread changed them first. On failure, the thread reads the new links and tries again, so some thread always makes progress and no thread waits on a lock.

The class implements Deque, not List, so it has no index-based get(i). We can think of it as a concurrent stack and queue in one. Four more rules of the class matter in concurrent code.

• It is unbounded, so offerFirst() and offerLast() always return true.
• It does not permit null elements, because null is the return value that means “empty”.
• Its iterators are weakly consistent and never throw ConcurrentModificationException.
• The size() method is not a constant-time operation, and bulk operations such as addAll() are not atomic.

2. Methods for Both Ends

Every operation comes in a version for the head (First) and one for the tail (Last). Like other Deque classes, the methods also come in pairs that differ in how they report an empty deque, so we choose the family by whether an empty deque is normal or an error.

Operation	Throws on empty	Returns null on empty	Stack alias
Add	addFirst(e), addLast(e)	offerFirst(e), offerLast(e) (always true)	push(e)
Remove	removeFirst(), removeLast()	pollFirst(), pollLast()	pop()
Read without removing	getFirst(), getLast()	peekFirst(), peekLast()	peek()

The methods in the first column throw NoSuchElementException on an empty deque. In concurrent code another thread can empty the deque between our check and our call, so the poll and peek methods with a null check are the safer default.

ConcurrentLinkedDeque<String> empty = new ConcurrentLinkedDeque<>();
String polled = empty.pollFirst();               // null
String peeked = empty.peekLast();                // null
String first = empty.getFirst();                 // NoSuchElementException
String popped = empty.pop();                     // NoSuchElementException

Since Java 21, every Deque is a sequenced collection, so reversed() returns a reverse-ordered view of the same deque.

ConcurrentLinkedDeque<String> steps = new ConcurrentLinkedDeque<>(List.of("open", "edit", "save"));
Deque<String> undoOrder = steps.reversed();
String lastStep = undoOrder.peekFirst();         // "save"
String undoList = undoOrder.toString();          // "[save, edit, open]"

3. ConcurrentLinkedDeque Example

In this example, we implement two different tasks. One task adds a large amount of data to the deque, and the other removes a large amount of data from the same deque. If the deque is thread safe, the final size equals the number of elements added minus the number removed, with no lost or duplicated elements.

class AddTask implements Runnable {
    private final ConcurrentLinkedDeque<String> deque;

    AddTask(ConcurrentLinkedDeque<String> deque) {
        this.deque = deque;
    }

    @Override
    public void run() {
        String name = Thread.currentThread().getName();
        for (int i = 0; i < 10_000; i++) {
            deque.add(name + ": Element " + i);
        }
    }
}

class RemoveTask implements Runnable {
    private final ConcurrentLinkedDeque<String> deque;

    RemoveTask(ConcurrentLinkedDeque<String> deque) {
        this.deque = deque;
    }

    @Override
    public void run() {
        for (int i = 0; i < 5_000; i++) {
            deque.pollFirst();
            deque.pollLast();
        }
    }
}

Next, we run 100 add tasks and wait for them, and after that 100 remove tasks. Each executor waits for its tasks in close(), which the try-with-resources block calls, since ExecutorService is AutoCloseable as of Java 19.

ConcurrentLinkedDeque<String> deque = new ConcurrentLinkedDeque<>();
try (ExecutorService adders = Executors.newFixedThreadPool(100)) {
    for (int i = 0; i < 100; i++) {
        adders.submit(new AddTask(deque));
    }
}
int sizeAfterAdding = deque.size();              // 1000000
try (ExecutorService removers = Executors.newFixedThreadPool(100)) {
    for (int i = 0; i < 100; i++) {
        removers.submit(new RemoveTask(deque));
    }
}
int sizeAfterRemoving = deque.size();            // 0

Let us see how it all worked.

1. First, the 100 AddTask tasks add elements to the deque. Each one inserts 10,000 elements with add(), which adds at the tail, so the deque has 1,000,000 elements when they finish.
2. After that, the 100 RemoveTask tasks remove elements. Each one removes 10,000 elements with pollFirst() and pollLast(), which remove and return the head and the tail. When the deque is empty, both methods return null.
3. We call size() only after each group of tasks has finished. While threads still add or remove elements, size() can return a number that was never the real size, as section 4 explains.

With a plain ArrayDeque in place of ConcurrentLinkedDeque, the same code can lose elements or throw exceptions inside the tasks, because ArrayDeque is not thread safe.

4. size(), Iteration and Bulk Operations

The deque keeps no element counter, so size() walks the whole linked list and counts the nodes. It costs O(n) time, and the deque can change during the walk. To check whether work is left, we call isEmpty() or test the result of pollFirst() for null instead.

Iteration is weakly consistent. An iterator shows the elements as they were at some point at or after its creation, it may or may not show later changes, and it never throws ConcurrentModificationException. So one thread can loop over the deque while others add and remove elements.

ConcurrentLinkedDeque<Integer> orders = new ConcurrentLinkedDeque<>(List.of(1, 2, 3));
for (Integer order : orders) {
    if (order == 1) {
        orders.addLast(4);                       // no ConcurrentModificationException
    }
}
int orderCount = orders.size();                  // 4

Bulk operations such as addAll(), removeIf(), equals() and toArray() are not atomic. Another thread can see half of an addAll(), so when a group of elements must appear together, we wrap them in one object and add that object.

5. Work Stealing With a Shared Deque

Work stealing is the main pattern that needs both ends of a deque. The owner thread pushes and pops its own tasks at the head in last-in-first-out order, which keeps recently used data in the CPU cache. An idle thread steals the oldest tasks from the tail, so the two threads rarely compete for the same node. The ForkJoinPool uses the same idea with its own internal deques.

Say an image service splits a batch of 10,000 thumbnails into tasks. The following example lets an owner thread and a thief thread drain one deque from opposite ends and counts the processed tasks.

ConcurrentLinkedDeque<Integer> thumbnails = IntStream.range(0, 10_000).boxed()
        .collect(Collectors.toCollection(ConcurrentLinkedDeque::new));
LongAdder processed = new LongAdder();
Thread owner = Thread.ofPlatform().start(() -> {
    while (thumbnails.pollFirst() != null) {
        processed.increment();
    }
});
Thread thief = Thread.ofPlatform().start(() -> {
    while (thumbnails.pollLast() != null) {
        processed.increment();
    }
});
owner.join();
thief.join();
long done = processed.sum();                     // 10000

We can see that every task is processed once and only once, although neither thread knows how many tasks the other one took. The split between the two threads varies per run.

6. ConcurrentLinkedDeque vs Other Deques

The right deque depends on two questions, namely whether several threads use it and whether a consumer must wait when it is empty. A non-blocking deque returns null at once, whereas a blocking deque makes the consumer wait for an element, which a producer-consumer design needs.

Class	Thread safe	Blocking	Bounded	Best for
ConcurrentLinkedDeque	Yes, lock-free	No	No	Shared stack or queue, work stealing
LinkedBlockingDeque	Yes, one lock	Yes, takeFirst(), putLast()	Optional capacity	Producer-consumer with both ends
ConcurrentLinkedQueue	Yes, lock-free	No	No	Shared FIFO queue, one end each
ArrayDeque	No	No	No	Single-threaded stack or queue
ArrayBlockingQueue	Yes, one lock	Yes	Yes, fixed	Back-pressure with a fixed size

When consumers would otherwise loop on pollFirst() and burn CPU while the deque is empty, a LinkedBlockingDeque is the better choice. For a plain queue with one end for producers and one for consumers, ConcurrentLinkedQueue is simpler. The Java concurrency guide lists the other concurrent collections.

7. ConcurrentLinkedDeque FAQs

Thread safety, blocking, null handling and stack use are the points to clear up before the class replaces a synchronized LinkedList.

7.1. Is ConcurrentLinkedDeque thread safe?

Yes. Every single operation is thread safe and lock-free. A sequence of operations, such as peekFirst() followed by pollFirst(), is not atomic, so we act on the result of pollFirst() instead of checking first.

7.2. Is ConcurrentLinkedDeque blocking?

No. No method waits for an element or for a lock. For a deque that makes consumers wait, we use LinkedBlockingDeque and its takeFirst() or pollFirst(timeout, unit) methods.

7.3. Why does ConcurrentLinkedDeque not allow null elements?

Because null is the signal for an empty deque. The call add(null) throws NullPointerException, so a null from pollFirst() always means that the deque was empty.

7.4. Can we use ConcurrentLinkedDeque as a stack?

Yes. The methods push(), pop() and peek() work on the head, which makes it a thread-safe replacement for the legacy Stack class. Since pop() throws on an empty deque, pollFirst() is safer in concurrent code.

8. Conclusion

ConcurrentLinkedDeque is a lock-free, unbounded deque that many threads can use at both ends at the same time. It rejects null, its iterators never throw ConcurrentModificationException, and its size() is slow and only an estimate while other threads change it.

The class fits shared stacks, queues and work-stealing designs where threads should never wait. When consumers must wait for elements or the deque needs a capacity limit, LinkedBlockingDeque is the better tool.

9. References

• ConcurrentLinkedDeque (Java SE 25 API)
• Deque (Java SE 25 API)
• LinkedBlockingDeque (Java SE 25 API)
• JEP 431, Sequenced Collections

Happy Learning !!

Source Code on Github