Queue Implementation Using Linked List in DSA Python - Build from Scratch

Queue Implementation Using Linked List

📖 Scenario: Imagine a line of people waiting to buy tickets. The first person who comes in is the first to get the ticket and leave the line. This is how a queue works in computers.

🎯 Goal: You will build a queue using a linked list. You will add people to the end of the line and remove them from the front, just like in real life.

📋 What You'll Learn

Create a Node class to hold data and a link to the next node

Create a Queue class with methods to add (enqueue) and remove (dequeue) nodes

Keep track of the front and rear of the queue

Print the queue contents after operations

💡 Why This Matters

🌍 Real World

Queues are used in real life for waiting lines, printer job scheduling, and handling requests in order.

💼 Career

Understanding queues and linked lists is important for software development roles that involve data processing, task scheduling, and system design.

1

Create the Node class

Create a class called Node with an __init__ method that takes data and sets self.data = data and self.next = None.

DSA Python

# Create the Node class with __init__ method
# Your code here

Hint

Think of Node as a box holding a value and a pointer to the next box.

2

Create the Queue class with front and rear

Create a class called Queue with an __init__ method that sets self.front = None and self.rear = None.

DSA Python

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

# Create the Queue class with __init__ method
# Your code here

Hint

The queue needs to know where the line starts (front) and ends (rear).

3

Add enqueue and dequeue methods

In the Queue class, add a method enqueue(self, data) that adds a new Node with data to the rear. Also add a method dequeue(self) that removes the front node and returns its data. Handle empty queue cases.

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

# Add enqueue and dequeue methods below
# Your code here

Hint

Enqueue adds to the rear. Dequeue removes from the front. Remember to update front and rear carefully.

4

Print the queue contents after enqueue and dequeue

Create a print_queue(queue) function that prints the queue elements from front to rear separated by -> and ending with null. Then create a Queue object called q, enqueue 10, 20, 30, dequeue once, and print the queue using print_queue(q).

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 = new_node
            self.rear = new_node
        else:
            self.rear.next = new_node
            self.rear = new_node

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

# Define print_queue function
# Create Queue object q
# Enqueue 10, 20, 30
# Dequeue once
# Print queue
# Your code here

Hint

Traverse from front to rear and collect data to print. After dequeue, the first element (10) is removed.

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