How to Implement a Deque Using a List in Python

Learn how to build a deque (double-ended queue) in Python using both a simple list approach (with O(n) front operations) and an efficient circular array implementation (with O(1) operations at both ends).

A deque (double-ended queue) supports insertion and deletion at both ends: front and rear. While Python's collections.deque provides an optimized built-in implementation, understanding how to build one using a list reveals important concepts about data structure efficiency and circular array design. This guide covers both a simple list-based approach and an efficient circular array implementation.

Two Implementation Approaches

Approach	Front Operations	Rear Operations	Space
Naive (plain list)	O(n): shifting required	O(1)	Dynamic
Circular array	O(1): index math	O(1)	Fixed capacity

Method 1: Naive Implementation Using a Plain List

The simplest approach uses Python's list directly with insert(0, ...) for front insertion and pop(0) for front deletion:

class SimpleDeque:
    """Deque using a plain Python list (simple but inefficient for front ops)."""

    def __init__(self):
        self._data = []

    def insert_front(self, value):
        """Insert at the front: O(n) due to shifting."""
        self._data.insert(0, value)

    def insert_rear(self, value):
        """Insert at the rear: O(1) amortized."""
        self._data.append(value)

    def delete_front(self):
        """Remove and return the front element: O(n) due to shifting."""
        if self.is_empty():
            raise IndexError("Delete from an empty deque")
        return self._data.pop(0)

    def delete_rear(self):
        """Remove and return the rear element: O(1)."""
        if self.is_empty():
            raise IndexError("Delete from an empty deque")
        return self._data.pop()

    def peek_front(self):
        if self.is_empty():
            raise IndexError("Peek from an empty deque")
        return self._data[0]

    def peek_rear(self):
        if self.is_empty():
            raise IndexError("Peek from an empty deque")
        return self._data[-1]

    def is_empty(self):
        return len(self._data) == 0

    def size(self):
        return len(self._data)

    def display(self):
        return list(self._data)


dq = SimpleDeque()
dq.insert_front(10)
dq.insert_rear(20)
dq.insert_front(5)
print("Deque:", dq.display())

print("Deleted front:", dq.delete_front())
print("Deleted rear:", dq.delete_rear())
print("Deque:", dq.display())

Output:

Deque: [5, 10, 20]
Deleted front: 5
Deleted rear: 20
Deque: [10]

Method 2: Efficient Circular Array Implementation

A circular array eliminates the shifting problem by using modular arithmetic to wrap indices around the array. Instead of moving elements, we simply update the front index.

How the Circular Array Works

Capacity: 5, Front: 2, Size: 3

Index:    [0]   [1]   [2]   [3]   [4]
Values:   None  None   A     B     C
                       ↑                 
                     front    → rear at index (2+3-1)%5 = 4

When inserting at the front, the front index moves backward (wrapping to the end of the array). When inserting at the rear, the element goes to position (front + size) % capacity.

Complete Implementation

class CircularDeque:
    """Deque implementation using a circular array for O(1) operations."""

    def __init__(self, capacity):
        self._data = [None] * capacity
        self._capacity = capacity
        self._size = 0
        self._front = 0

    def is_empty(self):
        return self._size == 0

    def is_full(self):
        return self._size == self._capacity

    def size(self):
        return self._size

    def insert_front(self, value):
        """Insert at the front: O(1)."""
        if self.is_full():
            raise OverflowError("Deque is full")
        self._front = (self._front - 1) % self._capacity
        self._data[self._front] = value
        self._size += 1

    def insert_rear(self, value):
        """Insert at the rear: O(1)."""
        if self.is_full():
            raise OverflowError("Deque is full")
        rear = (self._front + self._size) % self._capacity
        self._data[rear] = value
        self._size += 1

    def delete_front(self):
        """Remove and return the front element: O(1)."""
        if self.is_empty():
            raise IndexError("Delete from an empty deque")
        value = self._data[self._front]
        self._data[self._front] = None  # Clean up
        self._front = (self._front + 1) % self._capacity
        self._size -= 1
        return value

    def delete_rear(self):
        """Remove and return the rear element: O(1)."""
        if self.is_empty():
            raise IndexError("Delete from an empty deque")
        rear = (self._front + self._size - 1) % self._capacity
        value = self._data[rear]
        self._data[rear] = None  # Clean up
        self._size -= 1
        return value

    def peek_front(self):
        if self.is_empty():
            raise IndexError("Peek from an empty deque")
        return self._data[self._front]

    def peek_rear(self):
        if self.is_empty():
            raise IndexError("Peek from an empty deque")
        rear = (self._front + self._size - 1) % self._capacity
        return self._data[rear]

    def display(self):
        """Return elements in order from front to rear."""
        if self.is_empty():
            return []
        return [
            self._data[(self._front + i) % self._capacity]
            for i in range(self._size)
        ]

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

Using the Circular Deque

dq = CircularDeque(5)

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

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

print(f"Deleted front: {dq.delete_front()}")
print(f"Deleted rear: {dq.delete_rear()}")
print("After deletions:", dq)

print(f"Size: {dq.size()}, Full: {dq.is_full()}")

Output:

After insertions: CircularDeque([5, 10, 20, 30])
Front: 5, Rear: 30
Deleted front: 5
Deleted rear: 30
After deletions: CircularDeque([10, 20])
Size: 2, Full: False

Demonstrating the Wrap-Around Behavior

dq = CircularDeque(4)

dq.insert_rear(1)
dq.insert_rear(2)
dq.insert_rear(3)
dq.insert_rear(4)
print("Full deque:", dq.display())
print("Internal array:", dq._data)

dq.delete_front()  # Remove 1
dq.delete_front()  # Remove 2
dq.insert_rear(5)  # Wraps to beginning of internal array
dq.insert_rear(6)

print("\nAfter wrap-around:")
print("Deque (logical order):", dq.display())
print("Internal array:", dq._data)
print(f"Front index: {dq._front}")

Output:

Full deque: [1, 2, 3, 4]
Internal array: [1, 2, 3, 4]

After wrap-around:
Deque (logical order): [3, 4, 5, 6]
Internal array: [5, 6, 3, 4]
Front index: 2

The internal array shows that elements 5 and 6 wrapped around to indices 0 and 1, while the logical order (front to rear) remains correct.

Common Mistake: Not Handling the Full/Empty State

A circular deque can silently overwrite data if you don't check for full capacity:

dq = CircularDeque(3)
dq.insert_rear(1)
dq.insert_rear(2)
dq.insert_rear(3)

try:
    dq.insert_rear(4)
except OverflowError as e:
    print(f"Error: {e}")

Output:

Error: Deque is full

Complexity Comparison

Operation	Naive (List)	Circular Array
`insert_front()`	O(n)	O(1)
`insert_rear()`	O(1) amortized	O(1)
`delete_front()`	O(n)	O(1)
`delete_rear()`	O(1)	O(1)
`peek_front()`	O(1)	O(1)
`peek_rear()`	O(1)	O(1)
`size()`	O(1)	O(1)
`display()`	O(n)	O(n)
Space	Dynamic	Fixed (pre-allocated)

When to Use Each Approach

Approach	Best For
Naive list	Quick prototyping, small datasets, learning
Circular array	Performance-critical applications, fixed-size buffers
`collections.deque`	Production Python code (optimized C implementation)