Queue Implementation Using Linked List in DSA Python

Mental Model

A queue is a line where the first person in is the first person out. Using a linked list means each person holds a note pointing to the next person.

Analogy: Imagine a line of people waiting to buy tickets. The first person who arrives is the first to get the ticket and leave. Each person holds the hand of the next person, so you can move along the line easily.

front -> [node1] -> [node2] -> [node3] -> null
rear ↑

Dry Run Walkthrough

Input: Start with empty queue, enqueue 10, enqueue 20, dequeue once, enqueue 30

Goal: Show how the queue changes step-by-step with linked list pointers

Step 1: enqueue 10: create node with value 10, set front and rear to it

front -> [10] -> null
rear ↑

Why: First element, so front and rear both point to it

Step 2: enqueue 20: create node with value 20, link rear.next to it, move rear to new node

front -> [10] -> [20] -> null
rear ↑

Why: Add new element at rear, update rear pointer

Step 3: dequeue: remove front node (10), move front to next node (20)

front -> [20] -> null
rear ↑

Why: Remove element from front, update front pointer

Step 4: enqueue 30: create node with value 30, link rear.next to it, move rear to new node

front -> [20] -> [30] -> null
rear ↑

Why: Add new element at rear, update rear pointer

Result:

front -> [20] -> [30] -> null
rear ↑

Annotated Code

DSA Python

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

class Queue:
    def __init__(self):
        self.front = None
        self.rear = None

    def enqueue(self, value):
        new_node = Node(value)
        if self.rear is None:  # empty queue
            self.front = self.rear = new_node
            return
        self.rear.next = new_node  # link new node at rear
        self.rear = new_node       # move rear to new node

    def dequeue(self):
        if self.front is None:  # empty queue
            return None
        removed_value = self.front.data
        self.front = self.front.next  # move front to next node
        if self.front is None:  # queue became empty
            self.rear = None
        return removed_value

    def display(self):
        curr = self.front
        elements = []
        while curr:
            elements.append(str(curr.data))
            curr = curr.next
        print(" -> ".join(elements) + " -> null")

# Driver code
q = Queue()
q.enqueue(10)
q.enqueue(20)
print("After enqueue 10 and 20:")
q.display()
removed = q.dequeue()
print(f"Dequeued: {removed}")
print("After one dequeue:")
q.display()
q.enqueue(30)
print("After enqueue 30:")
q.display()

if self.rear is None: # empty queue

check if queue is empty to initialize front and rear

self.rear.next = new_node # link new node at rear

link new node after current rear

self.rear = new_node # move rear to new node

update rear pointer to new node

if self.front is None: # empty queue

check if queue is empty before dequeue

self.front = self.front.next # move front to next node

remove front node by moving front pointer

if self.front is None: # queue became empty

if queue is empty after dequeue, reset rear pointer

Output

After enqueue 10 and 20:

10 -> 20 -> null

Dequeued: 10

After one dequeue:

20 -> null

After enqueue 30:

20 -> 30 -> null

Complexity Analysis

Time: O(1) for both enqueue and dequeue because we only change pointers at front or rear without traversal

Space: O(n) because each element is stored as a node in the linked list

vs Alternative: Compared to array-based queue, linked list avoids shifting elements on dequeue, making dequeue O(1) instead of O(n)

Edge Cases

dequeue from empty queue

returns None and does not crash

DSA Python

if self.front is None:  # empty queue

enqueue first element into empty queue

front and rear both point to the new node

DSA Python

if self.rear is None:  # empty queue

dequeue last element making queue empty

front and rear both become None

DSA Python

if self.front is None:  # queue became empty

When to Use This Pattern

When you need a first-in-first-out (FIFO) structure with efficient enqueue and dequeue, use a queue with linked list to avoid costly shifts.

Common Mistakes

Mistake: Not updating rear pointer when enqueueing the first element
Fix: Set both front and rear to the new node when queue is empty

Mistake: Not setting rear to None when queue becomes empty after dequeue
Fix: After moving front, if front is None, set rear to None as well

Summary

Implements a queue using a linked list with pointers to front and rear nodes.

Use when you want efficient FIFO operations without shifting elements.

Remember to update both front and rear pointers correctly when queue becomes empty or has one element.