# Deep Dive (java.util.concurrent) - ConcurrentLinkedQueue and ConcurrentLinkedDeque

> *"No locks at all — just atomic compare-and-swap, all the way down."*

`ConcurrentLinkedQueue` and `ConcurrentLinkedDeque` are **lock-free** concurrent collections built entirely on CAS (Compare-And-Swap) operations. This deep dive explains the Michael-Scott non-blocking queue algorithm and the helping mechanism that makes it work.

* * *

## Why Lock-Free?

Lock-based data structures have problems:

*   **Deadlock risk** — threads can deadlock on nested locks
    
*   **Priority inversion** — high-priority thread waits for low-priority lock holder
    
*   **Convoying** — if lock holder is preempted, ALL waiters stall
    

Lock-free structures use **CAS** (Compare-And-Swap) instead:

![](https://cdn.hashnode.com/uploads/covers/637f189ed7d9bcd845996b4b/1b1d0672-533f-4a05-8572-357dd8b2bb40.png align="center")

**Lock-free guarantee:** At least one thread is always making progress, regardless of what happens to other threads (preemption, suspension, etc.).

### CAS Refresher

```java
// Atomic compare-and-swap (single CPU instruction on x86: CMPXCHG)
boolean CAS(address, expectedValue, newValue) {
    if (*address == expectedValue) {
        *address = newValue;
        return true;   // Success!
    }
    return false;      // Failed — someone else changed it
}
```

* * *

## ConcurrentLinkedQueue — The Michael-Scott Queue

`ConcurrentLinkedQueue` implements the famous **Michael-Scott non-blocking queue** (1996). It's a singly-linked list with `head` and `tail` pointers:

```java
public class ConcurrentLinkedQueue<E> extends AbstractQueue<E>
        implements Queue<E> {
    
    private transient volatile Node<E> head;
    private transient volatile Node<E> tail;
    
    private static class Node<E> {
        volatile E item;
        volatile Node<E> next;
    }
}
```

![](https://cdn.hashnode.com/uploads/covers/637f189ed7d9bcd845996b4b/a50cda4c-dd76-436e-9729-a3ea88759dba.png align="center")

**Important:** The `head` always points to a **sentinel node** (a dummy node whose `item` is null). This simplifies edge cases.

* * *

## How offer() Works — Lock-Free Insert

```java
public boolean offer(E e) {
    final Node<E> newNode = new Node<E>(e);
    
    for (Node<E> t = tail, p = t;;) {    // Retry loop
        Node<E> q = p.next;
        
        if (q == null) {
            // p is the last node — try to CAS our node as the next
            if (NEXT.compareAndSet(p, null, newNode)) {
                // CAS succeeded! Node is linked.
                if (p != t) // Tail fell behind — update it
                    TAIL.compareAndSet(this, t, newNode);
                return true;
            }
            // CAS failed — another thread won. Retry.
        }
        else if (p == q)
            // Self-link (removed node) — restart from head or tail
            p = (t != (t = tail)) ? t : head;
        else
            // Tail fell behind — advance to the real tail
            p = (p != t && t != (t = tail)) ? t : q;
    }
}
```

![](https://cdn.hashnode.com/uploads/covers/637f189ed7d9bcd845996b4b/bd16d531-77db-4316-bc53-f93c5eec6d0c.png align="center")

### The Two-Phase Insert

The insert is split into two steps:

1.  **Link the node:** CAS the `next` pointer of the current last node
    
2.  **Update tail:** CAS the `tail` pointer to the new node
    

![](https://cdn.hashnode.com/uploads/covers/637f189ed7d9bcd845996b4b/a7f41477-389b-4929-a23d-8d081e94f59d.png align="center")

* * *

## How poll() Works — Lock-Free Remove

```java
public E poll() {
    restartFromHead: for (;;) {
        for (Node<E> h = head, p = h, q;; ) {
            final E item;
            
            if ((item = p.item) != null && p.compareAndSetItem(item, null)) {
                // CAS nulled out the item — we "own" this element
                if (p != h)
                    updateHead(h, ((q = p.next) != null) ? q : p);
                return item;
            }
            else if ((q = p.next) == null) {
                updateHead(h, p);
                return null;  // Queue is empty
            }
            else if (p == q)
                continue restartFromHead;
            else
                p = q;  // Advance to next node
        }
    }
}
```

![](https://cdn.hashnode.com/uploads/covers/637f189ed7d9bcd845996b4b/6bb22137-aee9-46e5-8808-0083d2eaf4a9.png align="center")

**Key insight:** Removal doesn't physically unlink the node immediately. Instead, the `item` is CAS'd to null, and the `head` pointer is lazily updated. Nodes with null items are "logically removed" but may still be in the chain briefly.

* * *

## The Helping Mechanism

The most elegant design aspect: **threads help each other**. If Thread A links a node but gets preempted before updating `tail`, Thread B will notice and do it:

![](https://cdn.hashnode.com/uploads/covers/637f189ed7d9bcd845996b4b/219f02c4-90a3-4386-b544-d1b2327cbad2.png align="center")

This "helping" is what makes the algorithm **lock-free** — progress is guaranteed even if any thread is suspended at any point.

* * *

## ConcurrentLinkedDeque — Double-Ended

`ConcurrentLinkedDeque` extends the concept to a **doubly-linked** lock-free structure with operations at both ends:

```java
public class ConcurrentLinkedDeque<E> extends AbstractCollection<E>
        implements Deque<E> {
    
    volatile Node<E> head;
    volatile Node<E> tail;
    
    static final class Node<E> {
        volatile Node<E> prev;  // Added for deque functionality
        volatile E item;
        volatile Node<E> next;
    }
}
```

![](https://cdn.hashnode.com/uploads/covers/637f189ed7d9bcd845996b4b/568f17cf-5f18-4556-9789-c58f13ad2c61.png align="center")

The doubly-linked lock-free deque is significantly more complex than the singly-linked queue because it must maintain **both** `next` and `prev` pointers atomically. It uses a sophisticated multi-step CAS protocol.

### Operations

| Method | Description | Complexity |
| --- | --- | --- |
| `offerFirst(e)` | Add at head | O(1) |
| `offerLast(e)` | Add at tail | O(1) |
| `pollFirst()` | Remove from head | O(1) |
| `pollLast()` | Remove from tail | O(1) |
| `peekFirst()` | Look at head | O(1) |
| `peekLast()` | Look at tail | O(1) |
| `push(e)` / `pop()` | Stack operations (head) | O(1) |
| `size()` | Count elements | **O(n)** |

* * *

## Why size() is O(n)

Both `ConcurrentLinkedQueue` and `ConcurrentLinkedDeque` have **O(n)** `size()`:

```java
public int size() {
    restartFromHead: for (;;) {
        int count = 0;
        for (Node<E> p = first(); p != null; ) {
            if (p.item != null)
                if (++count == Integer.MAX_VALUE)
                    break;  // Overflow protection
            if (p == (p = p.next))
                continue restartFromHead;
        }
        return count;
    }
}
```

**Why?** There's no atomic counter. Adding one would require CAS on every insert and remove, creating a **contention bottleneck** — the exact thing lock-free structures are designed to avoid.

![](https://cdn.hashnode.com/uploads/covers/637f189ed7d9bcd845996b4b/7b72224e-fd68-4c6a-9c54-f2a757f106c2.png align="center")

> **Rule:** If you need to check `size()` frequently, ConcurrentLinkedQueue is the wrong choice. Use an `AtomicInteger` counter alongside it, or use a BlockingQueue.

* * *

## ConcurrentLinkedQueue vs BlockingQueue

| Feature | ConcurrentLinkedQueue | BlockingQueue |
| --- | --- | --- |
| **Blocking** | ❌ Never blocks | ✅ put()/take() block |
| **Lock-free** | ✅ CAS-only | ❌ Uses ReentrantLock |
| **Bounded** | ❌ Unbounded | ✅ (some implementations) |
| **size()** | O(n) approximate | O(1) exact |
| **Use case** | Non-blocking producers/consumers | Blocking producer/consumer |
| **Back-pressure** | None | Natural (full queue blocks) |
| **Best when** | poll() in a spin loop or event loop | Threads should sleep when idle |

![](https://cdn.hashnode.com/uploads/covers/637f189ed7d9bcd845996b4b/282422d7-37b5-49f6-85a5-0c115e883814.png align="center")

* * *

## Common Pitfalls

### Pitfall 1: Spinning on poll() Instead of Blocking

```java
// ❌ TERRIBLE: Burns CPU when queue is empty!
while (true) {
    String item = concurrentQueue.poll();
    if (item != null) {
        process(item);
    }
    // When queue is empty, this loops at 100% CPU doing nothing!
}

// ✅ If you need blocking behavior, use BlockingQueue.take()
String item = blockingQueue.take();  // Thread sleeps when empty

// ✅ Or add a small sleep/yield
while (true) {
    String item = concurrentQueue.poll();
    if (item != null) {
        process(item);
    } else {
        Thread.onSpinWait(); // Java 9+ hint to CPU
    }
}
```

### Pitfall 2: Relying on size()

```java
// ❌ size() is O(n) AND may be inaccurate under concurrency
if (queue.size() == 0) {
    // Another thread might add an element between size() and your next line!
}

// ✅ Use isEmpty() — still a snapshot, but cheaper
if (queue.isEmpty()) { ... }
```

### Pitfall 3: Unbounded Growth

```java
// ❌ ConcurrentLinkedQueue is unbounded — can grow until OOM
ConcurrentLinkedQueue<Task> queue = new ConcurrentLinkedQueue<>();
// If producers outpace consumers, memory grows without limit
// No back-pressure mechanism!

// ✅ Use a bounded BlockingQueue for back-pressure
BlockingQueue<Task> queue = new ArrayBlockingQueue<>(10_000);
```

* * *

## Summary

![](https://cdn.hashnode.com/uploads/covers/637f189ed7d9bcd845996b4b/fc390cee-b24a-4056-a314-e45f3619a495.png align="center")

**The one-liner:** ConcurrentLinkedQueue/Deque are lock-free, CAS-based collections providing O(1) non-blocking insert/remove with a helping mechanism — choose them when blocking is unacceptable and you can handle unbounded growth, otherwise use BlockingQueue.