Concurrent Queue: Linked List Implementation
What you'll learn: How to build a thread-safe queue using linked nodes with fine-grained locking to allow concurrent enqueue and dequeue operations.
The Core Idea
Unlike array-based queues with their fixed capacity, a linked-list implementation grows dynamically by allocating nodes as needed. The classic approach uses two locks: one protecting the head (for dequeue) and another protecting the tail (for enqueue). This allows producers and consumers to work simultaneously without blocking each other—a technique called fine-grained locking.
How It Works
Think of a physical queue at two service counters: one person joins at the back while another leaves from the front. They never interfere because they're at opposite ends.
Your queue maintains:
- A
headpointer (protected byhead_lock) - A
tailpointer (protected bytail_lock) - A dummy node that separates head and tail initially
Enqueue acquires tail_lock, creates a new node, links it after the current tail, then updates tail to point to the new node.
Dequeue acquires head_lock, checks if the queue is empty (head.next == null), removes the node after the dummy, and returns its value.
The dummy node prevents head and tail from pointing to the same actual data node, eliminating the need for both locks during normal operations.
Why Two Locks Matter
With a single lock, every enqueue blocks every dequeue. With two locks, producers and consumers truly run in parallel, dramatically improving throughput when both operations happen frequently. You only need both locks during edge cases or complex operations.
Key Takeaway: A linked-list concurrent queue with separate head and tail locks enables true parallelism between enqueue and dequeue operations, making it ideal for producer-consumer scenarios with high contention.