Course contentsShow
← Computer Science
Lesson 382 of 2,8729. Stacks and QueuesFree lesson

Linked List-Based Queue Implementation

Using a singly linked list with front and rear pointers for efficient queue operations.

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):

  1. Create a new node
  2. If the queue is empty, both front and rear point to this new node
  3. Otherwise, set rear->next to the new node, then update rear to the new node
  4. Time: O(1) — no traversal needed!

Dequeue (remove from front):

  1. Check if the queue is empty (if front is NULL)
  2. Save the front node's data
  3. Move front to front->next
  4. If the queue becomes empty, set rear to NULL too
  5. Delete the old front node
  6. 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.