How to Implement a Deque Using a List in Python
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)
# Usage
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]
The naive approach has O(n) time complexity for insert_front() and delete_front() because Python lists must shift all elements when modifying the beginning. For small datasets this is fine, but for performance-critical applications, use the circular array approach below.
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")
# Move front index backward (wraps around)
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")
# Calculate rear position
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)
# Insert elements
dq.insert_rear(10)
dq.insert_rear(20)
dq.insert_front(5)
dq.insert_rear(30)
print("After insertions:", dq)
# Peek
print(f"Front: {dq.peek_front()}, Rear: {dq.peek_rear()}")
# Delete from both ends
print(f"Deleted front: {dq.delete_front()}")
print(f"Deleted rear: {dq.delete_rear()}")
print("After deletions:", dq)
# Size and capacity
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)
# Fill the deque
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)
# Delete from front, then insert at rear: demonstrates wrapping
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)
# Attempting to insert into a full deque
try:
dq.insert_rear(4)
except OverflowError as e:
print(f"Error: {e}")
Output:
Error: Deque is full
Always check is_full() before inserting and is_empty() before deleting. Without these checks, the circular deque will silently overwrite existing data or read invalid values.
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) |
For production code, always use Python's built-in collections.deque. It provides O(1) operations at both ends, dynamic sizing, and is implemented in C for maximum performance. The implementations in this guide are valuable for understanding the underlying concepts and for environments where the standard library is not available.