What You'll Learn
You'll learn how to build a queue using a singly linked list with front and rear pointers to achieve efficient O(1) enqueue and dequeue operations.
Why Use a Linked List for Queues?
Unlike array-based queues that can run out of space or waste memory with circular indexing, a linked list-based queue grows and shrinks dynamically. You never worry about "full" queues or wasted slots.
The Core Structure
A linked list queue maintains two pointers:
- Front pointer: Points to the node at the head of the queue (where we dequeue from)
- Rear pointer: Points to the node at the tail of the queue (where we enqueue to)
Each node contains data and a next pointer, just like in a standard singly linked list.
How the Operations Work
Enqueue (add to rear):
- Create a new node
- If the queue is empty, both
frontandrearpoint to this new node - Otherwise, set
rear->nextto the new node, then updaterearto the new node - Time: O(1) — no traversal needed!
Dequeue (remove from front):
- Check if the queue is empty (if
frontis NULL) - Save the front node's data
- Move
fronttofront->next - If the queue becomes empty, set
rearto NULL too - Delete the old front node
- Time: O(1) — direct access!
Peek:
Simply return front->data without removing the node.
The Advantage
By maintaining both front and rear pointers, you avoid the O(n) traversal that inserting at the tail would normally require with just a head pointer. This makes linked list queues as efficient as any queue implementation.
Key Takeaway: A linked list-based queue uses front and rear pointers to achieve O(1) enqueue and dequeue operations while growing dynamically without wasted space.