How to Implement a Queue Using a Linked List in Python

Learn how to build a Python queue with O(1) enqueue and dequeue operations using a singly linked list, including full implementation, key operations, and performance comparison with Python lists.

A queue is a fundamental linear data structure that follows the FIFO (First In, First Out) principle, meaning the first element added is the first one to be removed. Think of a line of customers at a checkout counter: the person who arrives first gets served first.

While queues can be implemented using Python lists or arrays, these approaches suffer from performance issues, particularly O(n) time complexity when removing elements from the front due to element shifting. A linked list-based implementation solves this problem by using dynamically allocated nodes, offering O(1) time complexity for both enqueue and dequeue operations and eliminating the need for a fixed-size buffer.

In this guide, you will learn how to build a fully functional queue from scratch using a singly linked list in Python, complete with all essential operations, practical examples, and common pitfalls to avoid.

Understanding the Queue Structure

Before diving into the code, let's understand the core components:

Node: Each element in the queue is stored in a node that holds the data and a reference (pointer) to the next node.
Front pointer: Always points to the first node in the queue (the next element to be dequeued).
Rear pointer: Always points to the last node in the queue (where new elements are added).
Size counter: Tracks the number of elements currently in the queue.

Key Operations

Operation	Description
Enqueue	Add an element to the rear (end) of the queue
Dequeue	Remove and return the element from the front (beginning) of the queue
Peek (getFront)	View the front element without removing it
getRear	View the rear element without removing it
isEmpty	Check whether the queue is empty
getSize	Get the number of elements currently in the queue

Building the Node Class

Every element in the linked list queue is wrapped in a Node object. Each node stores a piece of data (key) and a reference to the next node in the chain:

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

When a node is first created, its next pointer is set to None because it is not yet connected to any other node.

Building the Queue Class

The MyQueue class manages the linked list and exposes all the queue operations. It maintains three attributes: front, rear, and size.

class MyQueue:
    def __init__(self):
        self.front = None
        self.rear = None
        self.size = 0

Enqueue (Adding an Element)

The enqueue method creates a new node and attaches it to the rear of the queue. If the queue is empty, both front and rear point to the new node:

def enqueue(self, x):
    temp = Node(x)

    if self.rear is None:
        self.front = temp
        self.rear = temp
    else:
        self.rear.next = temp
        self.rear = temp

    self.size += 1

How it works:

A new Node is created with the given value x.
If the queue is empty (self.rear is None), the new node becomes both the front and the rear.
If the queue already has elements, the current rear node's next pointer is set to the new node, and then rear is updated to point to the new node.
The size counter is incremented.

Dequeue (Removing an Element)

The dequeue method removes and returns the value at the front of the queue:

def dequeue(self):
    if self.front is None:
        return None

    res = self.front.key
    self.front = self.front.next

    if self.front is None:
        self.rear = None

    self.size -= 1
    return res

How it works:

If the queue is empty, it returns None.
The value of the front node is stored in res.
The front pointer advances to the next node.
If front becomes None after the removal, the queue is now empty, so rear is also set to None.
The size counter is decremented, and the stored value is returned.

Common mistake: forgetting to reset rear

When the last element is dequeued, the front pointer becomes None. If you forget to also set rear to None, the rear pointer will reference a stale node that is no longer part of the queue. This leads to bugs when you call enqueue again, because the old rear.next assignment will link to a dangling node.

def dequeue(self):
    if self.front is None:
        return None

    res = self.front.key
    self.front = self.front.next
    self.size -= 1
    return res

Always include the check to ensure rear is None when the queue becomes empty.

Peek (Viewing the Front and Rear Elements)

These methods let you inspect the front and rear values without modifying the queue:

def getFront(self):
    if self.front is None:
        return None
    return self.front.key

def getRear(self):
    if self.rear is None:
        return None
    return self.rear.key

isEmpty and getSize (tility Methods)

def isEmpty(self):
    return self.front is None

def getSize(self):
    return self.size

Complete Implementation

Here is the full, ready-to-use implementation:

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


class MyQueue:
    def __init__(self):
        self.front = None
        self.rear = None
        self.size = 0

    def enqueue(self, x):
        """Add an element to the rear of the queue."""
        temp = Node(x)

        if self.rear is None:
            self.front = temp
            self.rear = temp
        else:
            self.rear.next = temp
            self.rear = temp

        self.size += 1

    def dequeue(self):
        """Remove and return the element from the front of the queue."""
        if self.front is None:
            return None

        res = self.front.key
        self.front = self.front.next

        if self.front is None:
            self.rear = None

        self.size -= 1
        return res

    def getFront(self):
        """Return the front element without removing it."""
        if self.front is None:
            return None
        return self.front.key

    def getRear(self):
        """Return the rear element without removing it."""
        if self.rear is None:
            return None
        return self.rear.key

    def isEmpty(self):
        """Check if the queue is empty."""
        return self.front is None

    def getSize(self):
        """Return the current number of elements in the queue."""
        return self.size

Example Usage and Output

queue = MyQueue()

queue.enqueue(10)
queue.enqueue(20)
queue.enqueue(30)

print(queue.dequeue())    # Remove front element
print(queue.getFront())   # View new front
print(queue.getRear())    # View rear
print(queue.isEmpty())    # Is it empty?
print(queue.getSize())    # How many elements?

print(queue.dequeue())
print(queue.dequeue())

print(queue.isEmpty())    # Should be empty now

Output:

10
20
30
False
2
20
30
True

Step-by-step explanation:

Elements 10, 20, and 30 are enqueued.
dequeue() removes and returns 10 (the front). The list becomes 20 → 30.
getFront() returns 20, the new front element.
getRear() returns 30, the rear element.
isEmpty() returns False because two elements remain.
getSize() returns 2.
Two more dequeue() calls remove 20 and 30 respectively.
isEmpty() now returns True since the queue is fully drained.

Why Use a Linked List Instead of a Python List?

You might wonder why you wouldn't just use a regular Python list with append() and pop(0):

queue = []
queue.append(10)
queue.append(20)
queue.append(30)

print(queue.pop(0))

The problem is that pop(0) has O(n) time complexity because every remaining element must be shifted one position to the left. For large queues, this becomes a significant performance bottleneck.

Use collections.deque for production code

If you don't need a custom implementation, Python's built-in collections.deque provides an optimized double-ended queue with O(1) append and pop operations on both ends:

from collections import deque

queue = deque()
queue.append(10)
queue.append(20)
print(queue.popleft())  # 10 obtained in O(1) time

A linked list implementation is ideal for learning purposes, interviews, or scenarios where you need full control over memory and node management.

Time and Space Complexity

Operation	Time Complexity	Explanation
Enqueue	O(1)	Appending to the rear via the `rear` pointer is constant time
Dequeue	O(1)	Removing from the front via the `front` pointer is constant time
Peek (getFront)	O(1)	Directly accessing the `front` node's value
getRear	O(1)	Directly accessing the `rear` node's value
isEmpty	O(1)	A simple `None` check on the `front` pointer
getSize	O(1)	Returns the maintained `size` counter

Space complexity: O(n), where n is the number of elements in the queue. Each element requires one Node object containing the data and a next pointer.

Conclusion

Implementing a queue using a linked list in Python gives you O(1) performance for all core operations (enqueue, dequeue, peek, and size checks) without the overhead of element shifting that comes with list-based approaches.

This implementation is particularly valuable for understanding how queues work internally and is a common topic in coding interviews and data structures coursework.

For production applications, consider using Python's collections.deque, which provides the same performance guarantees with a battle-tested, optimized implementation.