What is ConcurrentLinkedQueue, and how does it achieve thread safety without locks?
answer
- Lock-free FIFO via CAS-with-retry (Michael-Scott queue)
- Unbounded — offer never blocks, poll returns null when empty
- Not a BlockingQueue (no put/take)
- size() is O(n) and only approximate; use isEmpty()
- No nulls; weakly consistent iterators
basics
~20 sIt is a thread-safe, unbounded FIFO queue. Instead of locking, it uses atomic compare-and-swap (CAS) operations to update its head and tail, so many threads can add and remove items at once without blocking each other.
solid answer
~50 sConcurrentLinkedQueue is an unbounded, thread-safe FIFO queue based on a non-blocking linked-node algorithm (a Michael-Scott style queue). Rather than guarding the queue with a lock, each producer and consumer uses compare-and-swap (CAS) to atomically link a new node at the tail or unlink a node at the head; if the CAS fails because another thread won the race, the operation simply retries. This means threads never block waiting for a lock, which gives good throughput under high contention. Because it is non-blocking, offer() always succeeds (the queue is unbounded) and poll() returns null when empty rather than waiting — it is not a BlockingQueue, so there is no take()/put() that waits. size() is O(n) and only an estimate, since it walks the list without locking while concurrent modifications may be happening. It is the go-to queue when you want a simple, lock-free producer/consumer buffer and don't need blocking or bounding.
go deeper
Knows it is a thread-safe FIFO queue you can share between threads safely, and that you don't need to wrap it in synchronized.
Can explain it is lock-free via CAS, is unbounded, is not a BlockingQueue, and that size() is approximate; picks it for non-blocking producer/consumer use.
Articulates the CAS-with-retry / Michael-Scott algorithm, the lazy tail advancement, weakly-consistent iterators, the no-backpressure OOM risk, and contrasts it with LinkedBlockingQueue.
Reasons about lock-free vs wait-free progress guarantees, cache/contention behavior under many producers, when an unbounded non-blocking queue is the right systemic choice vs bounded backpressure, and the memory-model happens-before guarantees CAS provides.
## What problem this solves When multiple threads share a queue, the naive way to keep it correct is to wrap every operation in a lock (e.g. `synchronized`). That works but serializes everything: only one thread touches the queue at a time, and threads that lose the race **block** (the OS suspends them). Under heavy contention that hurts throughput and can cause priority-inversion or convoy effects. **ConcurrentLinkedQueue** is a thread-safe queue that avoids locks entirely. ## Key terms (defined from scratch) - **Queue / FIFO**: a collection where elements are added at one end (the *tail*) and removed from the other (the *head*), so they come out in First-In-First-Out order. - **Thread-safe**: behaves correctly when many threads call it at the same time, with no corruption. - **Lock / blocking**: a lock lets only one thread into a critical section; others *block* (are parked by the OS) until it is released. - **CAS (Compare-And-Swap)**: a single hardware-atomic instruction. `CAS(memoryLocation, expected, new)` writes `new` only if the location currently equals `expected`, and reports whether it succeeded. It is the atomic building block that lets a thread update shared state without holding a lock. - **Non-blocking / lock-free**: an algorithm where threads never have to wait for a lock. Threads coordinate purely through CAS; if a thread's CAS fails because another thread changed the state first, it **retries** rather than blocking. Lock-free guarantees that *some* thread always makes progress system-wide. ## How ConcurrentLinkedQueue works Internally it is a **singly linked list of nodes**, each holding an element and a `next` pointer, plus `head` and `tail` references. It implements a variant of the classic **Michael & Scott non-blocking queue**. - **Enqueue (`offer`/`add`)**: create a new node, then CAS the current tail node's `next` pointer from `null` to the new node. If another thread enqueued first, the CAS fails and the thread retries (re-reading tail). The `tail` reference is advanced lazily — it may lag one node behind, and threads help advance it. This "sometimes stale tail" trick is deliberate: it reduces the number of CAS operations. - **Dequeue (`poll`)**: CAS the `head` to the next node and return the old head's element. If the queue is empty, `poll()` returns `null` immediately — it does **not** wait. Because every mutation is a CAS-with-retry, no thread is ever blocked on a lock; a slow or descheduled thread cannot stall the others. ## Important properties and gotchas - **Unbounded**: it has no capacity limit, so `offer()` always returns `true` and never blocks. If producers outpace consumers, memory grows without bound (a potential OOM risk) — there is no backpressure. - **Not a `BlockingQueue`**: there is no `put()`/`take()` that waits for space or for an element. If you need a consumer that blocks until work arrives, use `LinkedBlockingQueue` or `ArrayBlockingQueue` instead. - **`size()` is O(n) and approximate**: it walks the whole list without locking, and because the list can change during the walk, the result is only a best-effort estimate. Avoid calling it in hot paths or for control flow; prefer `isEmpty()` (which only checks the head). - **Weakly consistent iterators**: an iterator reflects the state at some point at/after creation, never throws `ConcurrentModificationException`, and may or may not show concurrent updates. It does not give a snapshot. - **No null elements**: `null` is reserved as the "empty" sentinel returned by `poll()`/`peek()`, so you cannot store `null`. - **Memory visibility**: successful CAS and volatile reads/writes establish happens-before edges, so an element enqueued by one thread is correctly visible to the thread that dequeues it. ## When to use it Reach for `ConcurrentLinkedQueue` for a high-throughput, multi-producer/multi-consumer hand-off buffer where you don't need blocking semantics or a size bound — for example, work-stealing buffers, event pipelines, or accumulating items to be drained periodically.
- Why is size() discouraged on ConcurrentLinkedQueue, and what should you use instead?size() traverses the entire list without locking, so it is O(n) and, because the queue can change mid-traversal, only an estimate. For an emptiness check use isEmpty(), which only inspects the head and is O(1).
- When would you choose LinkedBlockingQueue over ConcurrentLinkedQueue?When you need blocking semantics (a consumer that waits via take() until an element arrives, or a producer that waits via put() when full) and/or a bounded capacity for backpressure. ConcurrentLinkedQueue offers neither.
saying these in an interview costs you the question
- Calling it a BlockingQueue or expecting poll()/take() to wait for elements
- Trusting size() as exact or calling it in a hot loop instead of isEmpty()
- Assuming it is bounded / provides backpressure — it can grow until OOM
- Thinking 'lock-free' means 'wait-free' (lock-free only guarantees system-wide progress, not per-thread)
- Trying to store null elements