Linked List-Based Queue Implementation

In our exploration of array-based queues, we encountered a fundamental tension: linear arrays waste space, and circular queues add complexity. Every dequeue operation in a linear array leaves a 'ghost slot' that cannot be reclaimed without expensive shifting operations. Circular queues solve this through modular arithmetic—but at the cost of more intricate pointer management and the need to distinguish between full and empty states.

There exists a more elegant solution: the linked list-based queue. By leveraging the dynamic nature of linked lists, we can implement queues that:

• Never waste space: Each node holds exactly one element, no empty slots
• Grow and shrink organically: Memory is allocated and freed on demand
• Achieve true O(1) operations: No amortization, no occasional expensive resizes
• Eliminate full/empty ambiguity: The distinction is trivially clear

The linked list queue represents one of the most natural marriages between a data structure and an abstract data type. Once you understand how singly linked lists work, implementing a queue becomes almost self-evident.

Before we dive into the linked list implementation, let's sharpen our understanding of what a queue truly requires. Unlike stacks, which access only one end, queues demand efficient access to both ends:

The Queue Contract (ADT Perspective):

The critical observation: enqueue happens at one end, dequeue at the other. This two-ended access pattern is what distinguishes queues from stacks and creates the implementation challenge we must address.

Why arrays struggle with this pattern:

Arrays excel at random access and operations at one end (the high-index end). But queues need efficient operations at both ends:

1. Insertion at rear: Arrays can do this in O(1) at the high end (if capacity permits)
2. Removal from front: Arrays must shift all remaining elements—O(n)

Circular arrays solve this by treating the array as a ring, but they introduce complexity around wrapping, capacity management, and distinguishing empty from full states.

Linked lists offer a more direct solution. Instead of fighting against the array's structure, we use a data structure whose very nature supports the operations we need.

Let's refresh our understanding of singly linked lists and examine how their properties map to queue requirements.

Singly Linked List Structure:

A singly linked list consists of nodes, where each node contains:

1. Data: The value stored in this node
2. Next: A reference to the next node in the sequence (or null if this is the last node)

The list typically maintains a head pointer that references the first node. Operations at the head are O(1): we can insert a new node at the front or remove the front node by simply updating the head pointer.

Standard Singly Linked List Operation Complexities:

The problem for queues:

With only a head pointer, we can efficiently:

• Dequeue (remove from front): O(1) — This maps perfectly to removing from head
• Enqueue (add to rear): O(n) — We must traverse to find the tail!

This asymmetry means that a standard singly linked list with only a head pointer cannot implement an efficient queue. We'd get O(n) enqueue operations, making the data structure impractical for any serious use case.

The solution: maintain a tail pointer.

By keeping track of both the first and last nodes, we gain O(1) access to both ends—exactly what queues require.

The transformation from a head-only linked list to a queue-capable structure requires exactly one addition: a tail pointer.

Enhanced Singly Linked List for Queues:

We maintain two pointers:

1. Head (Front of Queue): Points to the first node — where dequeues happen
2. Tail (Rear of Queue): Points to the last node — where enqueues happen

This simple addition changes our operation complexities dramatically:

Why tail insertion becomes O(1):

With a tail pointer, inserting at the end no longer requires traversal:

1. Create a new node with the given data
2. Set the current tail's next pointer to the new node
3. Update the tail pointer to the new node

No traversal needed—we go directly to the tail and append. This is the key operation for enqueue.

Why tail removal remains O(n):

Even with a tail pointer, removing the last node requires finding the second-to-last node (to become the new tail). In a singly linked list, there's no back pointer—we can't go backwards from the tail. We'd need to traverse from the head to find it.

For queues, this doesn't matter! We remove from the front (head), not the rear (tail). Dequeue is O(1).

This is the elegant match: queues need insertion at one end and removal at the other. With head and tail pointers, we get O(1) for both critical operations.

Now let's explicitly map each queue operation to its linked list equivalent. This mapping reveals why the implementation is so natural.

The Complete Mapping:

Visualizing the flow:

Consider a queue with elements [10, 20, 30] where 10 is at the front (first to be dequeued):

FRONT (head) --> [10] --> [20] --> [30] <-- REAR (tail)

Enqueue(40):

• Create node with value 40
• Current tail (30) points to new node
• Update tail pointer to new node

FRONT (head) --> [10] --> [20] --> [30] --> [40] <-- REAR (tail)

Dequeue():

• Store value at head (10)
• Update head to point to next node (20)
• Return stored value (10)

FRONT (head) --> [20] --> [30] --> [40] <-- REAR (tail)

The structure grows and shrinks dynamically, with memory allocated and freed per operation.

To fully appreciate the linked list approach, let's contrast it with the array-based implementations we studied earlier. This comparison will solidify your understanding of when each approach is appropriate.

Detailed analysis:

Linear Array Queue Problems:

• After several dequeues, the front of the array accumulates 'dead' space
• Either shift elements (O(n) per dequeue) or periodically compact (still expensive)
• Fundamentally unsuitable for queues with significant throughput

Circular Array Queue Trade-offs:

• Elegant solution to the space problem using modular arithmetic
• Requires careful handling of wrap-around
• Distinguishing full from empty requires either wasting one slot or maintaining a separate count
• Resizing is complicated—elements may wrap across the array boundary

Linked List Queue Advantages:

• No null slots, no wrap-around, no empty/full ambiguity
• Each node allocated independently—grows without resizing
• Pure O(1) operations with no edge cases for wrap-around
• Shrinks automatically as elements are dequeued (memory returned to system)

Linked List Queue Disadvantages:

• Each node requires pointer storage (typically 8 bytes on 64-bit systems)
• Nodes are scattered in memory—poor cache locality
• Frequent small allocations may stress the memory allocator
• Slightly higher constant factor per operation due to pointer dereferencing

With the conceptual foundation established, let's define the concrete building block of our queue: the Node.

A node in our linked list queue is identical to a standard singly linked list node—a simple container with two components:

1. data: The value stored in this queue slot
2. next: A reference to the next node in the queue (toward the rear), or null if this is the rear

Generic Node Definition:

Memory considerations:

Each node consumes:

• Size of the data element (varies by type)
• Size of a pointer/reference (typically 8 bytes on 64-bit systems)

For a queue storing 64-bit integers:

• Array-based queue: 8 bytes per element
• Linked list queue: 8 bytes (int) + 8 bytes (next pointer) = 16 bytes per element

This 2x overhead per element is the price of dynamic flexibility. For larger objects (strings, complex records, serialized data), the pointer overhead becomes proportionally smaller.

Real-world observation: In task queues, message queues, and event systems, the payload is typically much larger than 8 bytes. A 1KB task payload makes the 8-byte pointer overhead negligible (< 1%).

With our Node structure defined, let's outline the LinkedQueue class itself. This skeleton shows the fields and method signatures—we'll implement each method in detail in subsequent pages.

Key design decisions:

1. head (front) pointer: Points to the first node—where dequeues occur
2. tail (rear) pointer: Points to the last node—where enqueues occur
3. size counter: Provides O(1) size queries without traversal
4. Generic typing: Queue is parameterized by element type T

Critical invariants we must maintain:

1. If the queue is empty: Both head and tail are null, count is 0
2. If the queue has one element: head and tail point to the SAME node
3. If the queue has multiple elements: head points to the front, tail to the rear, and following next pointers from head eventually reaches tail
4. The tail's next is always null: It's the last node
5. count always equals the number of reachable nodes from head

These invariants are essential for correctness. Every method must preserve them, and we can use them to detect bugs during testing.

We've established the conceptual foundation for implementing queues using singly linked lists. Let's consolidate our key insights:

What's next:

With the conceptual model established, we'll now examine the specific roles of the head and tail pointers in greater detail. Understanding how head serves as our front pointer and tail as our rear pointer—and executing the invariant-preserving updates during enqueue and dequeue—is crucial for correct implementation.