How to Implement a Deque Using a Doubly Linked List in Python

Learn how to build a deque from scratch in Python using a doubly linked list for O(1) insertions/deletions at both ends, with full implementation and edge-case handling.

A deque (double-ended queue) is a versatile data structure that supports insertion and deletion at both ends in constant time. While Python's collections.deque provides a built-in implementation, building one from scratch using a doubly linked list deepens your understanding of pointer manipulation and data structure design. This guide walks through a complete implementation with all standard deque operations.

Why Use a Doubly Linked List?

A doubly linked list is the ideal backing structure for a deque because:

Each node has pointers to both the next and previous nodes
Insertions and deletions at either end take O(1) time
No element shifting is required (unlike array-based implementations)
Memory is allocated per node, so no resizing overhead

None ← [10] ⇄ [20] ⇄ [30] → None
        ↑                    ↑
       front                rear

Node Structure

Each node in the doubly linked list stores a value and two pointers:

class Node:
    """A node in a doubly linked list."""

    def __init__(self, value):
        self.value = value
        self.next = None
        self.prev = None

Complete Deque Implementation

The deque class maintains references to the front and rear nodes, along with a size counter for O(1) size queries:

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


class Deque:
    """Deque implementation using a doubly linked list."""

    def __init__(self):
        self.front = None
        self.rear = None
        self._size = 0

    def is_empty(self):
        """Return True if the deque is empty."""
        return self._size == 0

    def size(self):
        """Return the number of elements."""
        return self._size

    def insert_front(self, value):
        """Insert an element at the front."""
        new_node = Node(value)
        if self.is_empty():
            self.front = self.rear = new_node
        else:
            new_node.next = self.front
            self.front.prev = new_node
            self.front = new_node
        self._size += 1

    def insert_rear(self, value):
        """Insert an element at the rear."""
        new_node = Node(value)
        if self.is_empty():
            self.front = self.rear = new_node
        else:
            new_node.prev = self.rear
            self.rear.next = new_node
            self.rear = new_node
        self._size += 1

    def delete_front(self):
        """Remove and return the front element."""
        if self.is_empty():
            raise IndexError("Delete from an empty deque")
        value = self.front.value
        self.front = self.front.next
        if self.front is None:
            self.rear = None
        else:
            self.front.prev = None
        self._size -= 1
        return value

    def delete_rear(self):
        """Remove and return the rear element."""
        if self.is_empty():
            raise IndexError("Delete from an empty deque")
        value = self.rear.value
        self.rear = self.rear.prev
        if self.rear is None:
            self.front = None
        else:
            self.rear.next = None
        self._size -= 1
        return value

    def peek_front(self):
        """Return the front element without removing it."""
        if self.is_empty():
            raise IndexError("Peek from an empty deque")
        return self.front.value

    def peek_rear(self):
        """Return the rear element without removing it."""
        if self.is_empty():
            raise IndexError("Peek from an empty deque")
        return self.rear.value

    def display(self):
        """Return all elements as a list (front to rear)."""
        elements = []
        current = self.front
        while current is not None:
            elements.append(current.value)
            current = current.next
        return elements

    def __repr__(self):
        return f"Deque({self.display()})"

    def __len__(self):
        return self._size

Using the Deque

Basic Operations

dq = Deque()

dq.insert_rear(10)
dq.insert_rear(20)
dq.insert_rear(30)
print("After rear insertions:", dq)

dq.insert_front(5)
print("After front insertion:", dq)

print(f"Front: {dq.peek_front()}, Rear: {dq.peek_rear()}")

removed = dq.delete_front()
print(f"Removed from front: {removed}")
print("After front deletion:", dq)

removed = dq.delete_rear()
print(f"Removed from rear: {removed}")
print("After rear deletion:", dq)

print(f"Size: {dq.size()}, Empty: {dq.is_empty()}")

Output:

After rear insertions: Deque([10, 20, 30])
After front insertion: Deque([5, 10, 20, 30])
Front: 5, Rear: 30
Removed from front: 5
After front deletion: Deque([10, 20, 30])
Removed from rear: 30
After rear deletion: Deque([10, 20])
Size: 2, Empty: False

Step-by-Step Pointer Visualization

Here is how the internal structure changes with each operation:

dq = Deque()

dq.insert_rear(10)

dq.insert_rear(20)

dq.insert_front(5)

dq.delete_front()  # removes 5

dq.delete_rear()   # removes 20

Using the Deque as a Stack or Queue

A deque can function as both a stack (LIFO) and a queue (FIFO):

stack = Deque()
stack.insert_rear(1)   # push
stack.insert_rear(2)   # push
stack.insert_rear(3)   # push
print("Stack pop:", stack.delete_rear())   # pop → 3
print("Stack pop:", stack.delete_rear())   # pop → 2

queue = Deque()
queue.insert_rear(1)    # enqueue
queue.insert_rear(2)    # enqueue
queue.insert_rear(3)    # enqueue
print("Queue dequeue:", queue.delete_front())  # dequeue → 1
print("Queue dequeue:", queue.delete_front())  # dequeue → 2

Output:

Stack pop: 3
Stack pop: 2
Queue dequeue: 1
Queue dequeue: 2

Common Mistake: Not Handling the Single-Element Case

When the deque has only one element, both front and rear point to the same node. Deleting it requires updating both pointers to None:

dq = Deque()
dq.insert_rear(42)  # front and rear both point to [42]


value = dq.delete_front()
print(f"Removed: {value}")
print(f"Front: {dq.front}")  # None
print(f"Rear: {dq.rear}")    # None: correctly updated

Output:

Removed: 42
Front: None
Rear: None

Error Handling for Empty Deque Operations

Attempting to delete or peek from an empty deque should raise a clear error:

dq = Deque()

try:
    dq.delete_front()
except IndexError as e:
    print(f"Error: {e}")

try:
    dq.peek_rear()
except IndexError as e:
    print(f"Error: {e}")

Output:

Error: Delete from an empty deque
Error: Peek from an empty deque

Time and Space Complexity

Operation	Time Complexity	Description
`insert_front()`	O(1)	Create node, update 2 pointers
`insert_rear()`	O(1)	Create node, update 2 pointers
`delete_front()`	O(1)	Update front pointer
`delete_rear()`	O(1)	Update rear pointer
`peek_front()`	O(1)	Return front value
`peek_rear()`	O(1)	Return rear value
`size()`	O(1)	Return stored counter
`is_empty()`	O(1)	Check counter
`display()`	O(n)	Traverse all nodes

Space Complexity: O(n) where n is the number of elements stored.

All core deque operations run in constant time O(1), which is the primary advantage of the doubly linked list implementation over array-based approaches that may require O(n) shifts for front insertions or deletions.