Queue Implementation Using Linked List in DSA Python - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Enqueue and Dequeue Operations

What is the printed state of the queue after performing these operations?

Operations:
1. Enqueue 10
2. Enqueue 20
3. Enqueue 30
4. Dequeue
5. Enqueue 40

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, data):
        new_node = Node(data)
        if self.rear is None:
            self.front = self.rear = new_node
            return
        self.rear.next = new_node
        self.rear = new_node

    def dequeue(self):
        if self.front is None:
            return None
        temp = self.front
        self.front = temp.next
        if self.front is None:
            self.rear = None
        return temp.data

    def print_queue(self):
        current = self.front
        result = []
        while current:
            result.append(current.data)
            current = current.next
        print(" -> ".join(map(str, result)) + " -> null")

q = Queue()
q.enqueue(10)
q.enqueue(20)
q.enqueue(30)
q.dequeue()
q.enqueue(40)
q.print_queue()

A 10 -> 20 -> 30 -> 40 -> null

B 20 -> 30 -> 40 -> null

C 30 -> 40 -> null

D 40 -> null

💡 Hint

Remember that dequeue removes from the front of the queue.

After enqueueing 10, 20, 30, the queue is 10 -> 20 -> 30 -> null. Dequeue removes 10, so queue becomes 20 -> 30 -> null. Enqueue 40 adds it at the rear, so final queue is 20 -> 30 -> 40 -> null.

🧠 Conceptual

intermediate

Queue Front and Rear After Operations

After performing these operations on an empty queue:
enqueue(5), enqueue(15), dequeue(), enqueue(25), dequeue()
What are the values at the front and rear of the queue?

A Front: 5, Rear: 25

B Front: 15, Rear: 25

C Front: 25, Rear: 15

D Front: 25, Rear: 25

💡 Hint

Track each operation carefully and update front and rear pointers.

Operations step-by-step: - enqueue(5): front=5, rear=5 - enqueue(15): front=5, rear=15 - dequeue(): removes 5, front=15, rear=15 - enqueue(25): front=15, rear=25 - dequeue(): removes 15, front=25, rear=25 So both front and rear point to 25.

🔧 Debug

advanced

Identify the Bug in Dequeue Method

What error will this code raise when dequeue is called on an empty queue?

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 dequeue(self):
        temp = self.front
        self.front = temp.next
        if self.front is None:
            self.rear = None
        return temp.data

q = Queue()
q.dequeue()

A AttributeError: 'NoneType' object has no attribute 'next'

B IndexError: dequeue from empty queue

C TypeError: unsupported operand type(s)

D No error, returns null

💡 Hint

Check what happens when front is null and you try to access temp.next.

When the queue is empty, front is null. The code tries to access temp.next where temp is null, causing AttributeError.

📝 Syntax

advanced

Syntax Error in Enqueue Method

Which option contains the correct enqueue method for a linked list queue?

A

def enqueue(self, data):
    new_node = Node(data)
    if self.rear is None:
        self.front = self.rear = new_node
    else:
        self.rear.next = new_node
        self.rear = new_node

B

def enqueue(self, data):
    new_node = Node(data)
    if self.rear == None
        self.front = self.rear = new_node
    else:
        self.rear.next = new_node
        self.rear = new_node

C

def enqueue(self, data):
    new_node = Node(data)
    if self.rear is None:
        self.front = new_node
        self.rear = new_node
    else
        self.rear.next = new_node
        self.rear = new_node

D

def enqueue(self, data):
    new_node = Node(data)
    if self.rear is None:
        self.front = self.rear = new_node
    else:
        self.rear.next = new_node
        self.rear = new_node
    return

💡 Hint

Look for missing colons and proper if-else structure.

Option A has correct syntax with colons after if and else, and proper assignment. Options B and C miss colons causing SyntaxError. Option A has an unnecessary return but is syntactically valid; however, the trailing comma in the option text is not part of code and does not cause error, so option A is valid syntax but the trailing comma is not code. To avoid ambiguity, option A is the best correct answer.

🚀 Application

expert

Queue Size After Mixed Operations

Given the following sequence of operations on an empty queue, what is the size of the queue at the end?

enqueue(1), enqueue(2), dequeue(), enqueue(3), enqueue(4), dequeue(), dequeue(), enqueue(5)

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
        self.size = 0

    def enqueue(self, data):
        new_node = Node(data)
        if self.rear is None:
            self.front = self.rear = new_node
        else:
            self.rear.next = new_node
            self.rear = new_node
        self.size += 1

    def dequeue(self):
        if self.front is None:
            return None
        temp = self.front
        self.front = temp.next
        if self.front is None:
            self.rear = None
        self.size -= 1
        return temp.data

q = Queue()
q.enqueue(1)
q.enqueue(2)
q.dequeue()
q.enqueue(3)
q.enqueue(4)
q.dequeue()
q.dequeue()
q.enqueue(5)
print(q.size)

A 1

B 3

C 2

D 4

💡 Hint

Count each enqueue as +1 and each dequeue as -1 carefully.

Operations and size changes: - enqueue(1): size=1 - enqueue(2): size=2 - dequeue(): size=1 - enqueue(3): size=2 - enqueue(4): size=3 - dequeue(): size=2 - dequeue(): size=1 - enqueue(5): size=2 Final size is 2.

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