Double Ended Queue Deque in DSA Python

Mental Model

A deque lets you add or remove items from both ends easily, like a line where people can join or leave from front or back.

Analogy: Imagine a train with doors at both front and back. Passengers can get on or off from either door without waiting for the whole train to stop at one end.

front -> [ ] -> [ ] -> [ ] -> back
↑front pointer      ↑back pointer

Dry Run Walkthrough

Input: Start with empty deque, then add 1 at front, add 2 at back, add 3 at front, remove from back

Goal: Show how elements are added and removed from both ends and how the deque changes

Step 1: Add 1 at front

front -> [1] -> back

Why: We start by putting 1 in the empty deque at the front

Step 2: Add 2 at back

front -> [1] -> [2] -> back

Why: Add 2 at the back to grow the deque from the other end

Step 3: Add 3 at front

front -> [3] -> [1] -> [2] -> back

Why: Add 3 at front pushes existing elements back

Step 4: Remove from back

front -> [3] -> [1] -> back

Why: Removing from back takes out the last element (2)

Result:

front -> [3] -> [1] -> back

Annotated Code

DSA Python

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

class Deque:
    def __init__(self):
        self.front = None
        self.back = None

    def add_front(self, value):
        new_node = Node(value)
        if not self.front:  # empty deque
            self.front = self.back = new_node
        else:
            new_node.next = self.front  # link new node to current front
            self.front.prev = new_node  # link current front back to new node
            self.front = new_node       # update front pointer

    def add_back(self, value):
        new_node = Node(value)
        if not self.back:  # empty deque
            self.front = self.back = new_node
        else:
            new_node.prev = self.back  # link new node back to current back
            self.back.next = new_node  # link current back next to new node
            self.back = new_node       # update back pointer

    def remove_front(self):
        if not self.front:
            return None  # empty deque
        value = self.front.value
        self.front = self.front.next  # move front pointer forward
        if self.front:
            self.front.prev = None
        else:
            self.back = None  # deque became empty
        return value

    def remove_back(self):
        if not self.back:
            return None  # empty deque
        value = self.back.value
        self.back = self.back.prev  # move back pointer backward
        if self.back:
            self.back.next = None
        else:
            self.front = None  # deque became empty
        return value

    def __str__(self):
        values = []
        curr = self.front
        while curr:
            values.append(str(curr.value))
            curr = curr.next
        return ' -> '.join(values) + ' -> null'

# Driver code using dry_run input
deque = Deque()
deque.add_front(1)
deque.add_back(2)
deque.add_front(3)
deque.remove_back()
print(deque)

if not self.front: # empty deque

check if deque is empty before adding first node

new_node.next = self.front # link new node to current front

link new node forward to old front to insert at front

self.front.prev = new_node # link current front back to new node

link old front back to new node to maintain double links

self.front = new_node # update front pointer

update front pointer to new node

new_node.prev = self.back # link new node back to current back

link new node back to old back to insert at back

self.back.next = new_node # link current back next to new node

link old back forward to new node

self.back = new_node # update back pointer

update back pointer to new node

self.front = self.front.next # move front pointer forward

remove front by moving front pointer forward

self.front.prev = None

disconnect old front from deque

self.back = self.back.prev # move back pointer backward

remove back by moving back pointer backward

self.back.next = None

disconnect old back from deque

Output

3 -> 1 -> null

Complexity Analysis

Time: O(1) for add or remove operations because we only change pointers at ends without traversing

Space: O(n) because we store n elements in nodes linked by pointers

vs Alternative: Compared to a list where adding/removing at front is O(n) due to shifting, deque is faster with O(1) at both ends

Edge Cases

empty deque

add operations set both front and back to new node; remove operations return None safely

DSA Python

if not self.front:  # empty deque

deque with single element

removing front or back empties deque and sets both pointers to None

DSA Python

else:
    self.back = None  # deque became empty

When to Use This Pattern

When a problem needs fast insertions and deletions from both ends, use a deque because it supports O(1) operations at front and back.

Common Mistakes

Mistake: Forgetting to update both next and prev pointers when adding or removing nodes
Fix: Always update both forward and backward links to keep the deque consistent

Mistake: Not handling empty deque case when removing elements
Fix: Check if deque is empty before removing and update pointers to None when deque becomes empty

Summary

A deque is a double-ended queue allowing adding and removing elements from both front and back efficiently.

Use a deque when you need quick access and updates at both ends of a sequence.

The key is to keep track of front and back pointers and update links carefully to maintain the structure.