Queue using Linked List | Complete Guide in Python

Implementing a Queue using a Linked List is a foundational data structure exercise with widespread use in real-world computing and interview questions. This guide provides an easy-to-follow explanation and clean Python implementation to build your queue using linked lists.

Here’s the [Problem Link] to begin with.

Problem Statement

You need to implement a queue with these operations:

• push(item): Inserts an integer item into the queue.
• pop(): Removes the element from the front of the queue and returns it. Return -1 if the queue is empty.

The queue should follow FIFO (First-In-First-Out) order strictly.

Example

q = MyQueue()
q.push(10)  # queue: 10
q.push(20)  # queue: 10 -> 20
print(q.pop())  # Output: 10
print(q.pop())  # Output: 20
print(q.pop())  # Output: -1 (queue empty)

Intuition & Approach

A queue operates by removing from the front and adding to the rear. Linked lists allow efficient insertions and deletions at both ends:

• Maintain pointers front and rear.
• Push: Add new node at the rear. Update rear pointer.
• Pop: Remove node from the front. Update front pointer.
• When queue becomes empty, set both front and rear to None.

Code Implementation

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

class MyQueue:
    def __init__(self):
        self.front = None  # Points to front node
        self.rear = None   # Points to rear node

    # Push operation: add at rear
    def push(self, item):
        new_node = Node(item)
        # Empty queue: front and rear both point to new node
        if self.rear is None:
            self.front = self.rear = new_node
            return
        # Attach new node to rear and update rear pointer
        self.rear.next = new_node
        self.rear = new_node

    # Pop operation: remove from front
    def pop(self):
        if self.front is None:
            return -1  # Queue empty
        popped = self.front.data
        self.front = self.front.next
        # If queue becomes empty, rear also must be None
        if self.front is None:
            self.rear = None
        return popped

Code Explanation

• Node class: Represents linked list nodes storing data and link to the next node.
• MyQueue:
  • front points to the node at the front of the queue.
  • rear points to the node at the rear (end).
• push(item):
  • Create a new node.
  • If empty, both front and rear point to this node.
  • Else, append to rear.next and update rear.
• pop():
  • Return -1 if empty.
  • Else remove the node at front, advance front.
  • If queue becomes empty after pop, also set rear = None.

Time and Space Complexity

• push: O(1) – constant time insertion at rear pointer.
• pop: O(1) – constant time removal at front pointer.
• Space: O(n) – number of elements stored.

This makes linked lists ideal for queues with efficient enqueue and dequeue operations.

Conclusion

Queues implemented with linked lists combine dynamic memory with FIFO order, perfect for situations where size changes dynamically. This problem is a common interview testing knowledge of pointers/references and basic data structure manipulation.

For any changes to the article, kindly email at code@codeanddebug.in or contact us at +91-9712928220.