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.

Practice

1. What is the main advantage of implementing a queue using a linked list instead of an array?

easy

A. Simpler to implement than arrays

B. Faster access to middle elements

C. Uses less memory for small queues

D. Dynamic size without fixed capacity limit

Solution

1. Step 1: Understand queue size limitation in arrays

   Arrays have fixed size, so queues implemented with arrays have a maximum capacity.

2. Step 2: Linked list dynamic sizing

   Linked lists can grow or shrink dynamically as nodes are added or removed, so no fixed size limit.

3. Final Answer:

   Dynamic size without fixed capacity limit -> Option D

4. Quick Check:

   Linked list queues grow dynamically = A [OK]

Hint: Linked lists grow dynamically, arrays have fixed size [OK]

Common Mistakes:

• Thinking linked lists allow faster middle access
• Assuming linked lists always use less memory
• Confusing implementation simplicity

2. Which of the following is the correct way to initialize an empty queue using a linked list in Python?

easy

A. queue = LinkedList()

B. queue = None

C. queue = Queue() with head and tail as None

D. queue = []

Solution

1. Step 1: Understand queue initialization

   An empty queue using linked list usually has head and tail pointers set to None.

2. Step 2: Identify correct initialization

   queue = Queue() with head and tail as None correctly describes a Queue class with head and tail as None, representing empty queue.

3. Final Answer:

   queue = Queue() with head and tail as None -> Option C

4. Quick Check:

   Empty queue has head and tail None = B [OK]

Hint: Empty linked list queue has head and tail as None [OK]

Common Mistakes:

• Using list [] instead of linked list
• Setting queue to None without structure
• Confusing linked list with array initialization

3. What will be the output after performing these operations on an empty linked list queue?

enqueue(10)
enqueue(20)
dequeue()
enqueue(30)
dequeue()

Print the queue elements from front to rear.

medium

A. 30 -> null

B. 20 -> 30 -> null

C. 10 -> 20 -> 30 -> null

D. 20 -> null

Solution

1. Step 1: Perform enqueue(10) and enqueue(20)

   Queue becomes 10 -> 20 -> null.

2. Step 2: Perform dequeue()

   Removes 10, queue is now 20 -> null.

3. Step 3: Perform enqueue(30)

   Queue becomes 20 -> 30 -> null.

4. Step 4: Perform dequeue()

   Removes 20, queue is now 30 -> null.

5. Final Answer:

   30 -> null -> Option A

6. Quick Check:

   After operations, queue front is 30 [OK]

Hint: Track enqueue/dequeue stepwise to find final queue [OK]

Common Mistakes:

• Forgetting to remove front element on dequeue
• Appending dequeue element instead of removing
• Mixing order of operations

4. Identify the error in this dequeue method of a linked list queue:

def dequeue(self):
    if self.head is None:
        return None
    temp = self.head
    self.head = self.head.next
    return temp.data
    self.tail = None

medium

A. The tail is set to None after return, so never updated

B. The method does not check if queue is empty

C. It should update head before returning data

D. temp.data is not a valid attribute

Solution

1. Step 1: Analyze the order of statements

   The return statement occurs before setting tail to None, so tail update never happens.

2. Step 2: Understand impact on queue state

   If last element is dequeued, tail should be set to None to mark empty queue, but it is skipped.

3. Final Answer:

   The tail is set to None after return, so never updated -> Option A

4. Quick Check:

   Return before tail update skips tail reset [OK]

Hint: Return ends function; update tail before return [OK]

Common Mistakes:

• Placing return before all updates
• Not resetting tail when queue becomes empty
• Ignoring empty queue check

5. You want to implement a method to reverse the queue implemented using a linked list without using extra data structures. Which approach is best?

hard

A. Create a new linked list and enqueue elements from old queue in reverse

B. Use recursion to dequeue and enqueue elements in reverse order

C. Traverse the linked list and swap data of nodes pairwise

D. Use a stack to store elements and then enqueue back

Solution

1. Step 1: Understand constraints

   No extra data structures allowed, so stack or new list are not options.

2. Step 2: Use recursion to reverse queue

   Recursion uses call stack implicitly to dequeue all elements, then enqueue them back in reverse order.

3. Final Answer:

   Use recursion to dequeue and enqueue elements in reverse order -> Option B

4. Quick Check:

   Recursion reverses queue without extra structures [OK]

Hint: Recursion uses call stack to reverse without extra structures [OK]

Common Mistakes:

• Using extra data structures despite constraints
• Swapping data pairs does not reverse queue order
• Creating new linked list violates no extra structure rule