Dequeue Using Linked List in DSA Python

Mental Model

A dequeue lets you add or remove items from both ends quickly using a linked list.

Analogy: Imagine a line of people where you can join or leave from the front or the back easily without shifting anyone.

front -> [1] -> [2] -> [3] -> back
↑head                 ↑tail

Dry Run Walkthrough

Input: Start with empty dequeue, then enqueue 1 at rear, enqueue 2 at rear, enqueue 3 at front, dequeue from rear, dequeue from front

Goal: Show how elements are added and removed from both ends using linked list pointers

Step 1: enqueue 1 at rear

front -> [1] -> null
↑head/tail

Why: First element becomes both front and rear

Step 2: enqueue 2 at rear

front -> [1] -> [2] -> null
↑head          ↑tail

Why: Add new node after tail and update tail pointer

Step 3: enqueue 3 at front

front -> [3] -> [1] -> [2] -> null
↑head          ↑tail

Why: Add new node before head and update head pointer

Step 4: dequeue from rear

front -> [3] -> [1] -> null
↑head          ↑tail

Why: Remove tail node and update tail pointer to previous node

Step 5: dequeue from front

front -> [1] -> null
↑head/tail

Why: Remove head node and update head pointer

Result:

front -> [1] -> null
↑head/tail

Annotated Code

DSA Python

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

class Dequeue:
    def __init__(self):
        self.head = None
        self.tail = None

    def enqueue_front(self, data):
        new_node = Node(data)
        if not self.head:  # empty dequeue
            self.head = self.tail = new_node
            return
        new_node.next = self.head  # link new node to current head
        self.head.prev = new_node  # link current head back to new node
        self.head = new_node       # update head to new node

    def enqueue_rear(self, data):
        new_node = Node(data)
        if not self.tail:  # empty dequeue
            self.head = self.tail = new_node
            return
        self.tail.next = new_node  # link current tail to new node
        new_node.prev = self.tail  # link new node back to current tail
        self.tail = new_node       # update tail to new node

    def dequeue_front(self):
        if not self.head:  # empty dequeue
            return None
        data = self.head.data
        self.head = self.head.next  # move head forward
        if self.head:
            self.head.prev = None  # remove backward link
        else:
            self.tail = None  # dequeue is empty now
        return data

    def dequeue_rear(self):
        if not self.tail:  # empty dequeue
            return None
        data = self.tail.data
        self.tail = self.tail.prev  # move tail backward
        if self.tail:
            self.tail.next = None  # remove forward link
        else:
            self.head = None  # dequeue is empty now
        return data

    def __str__(self):
        result = []
        curr = self.head
        while curr:
            result.append(str(curr.data))
            curr = curr.next
        return ' -> '.join(result) + ' -> null'

# Driver code using dry_run input
q = Dequeue()
q.enqueue_rear(1)
q.enqueue_rear(2)
q.enqueue_front(3)
print(q)  # after enqueues
q.dequeue_rear()
print(q)  # after dequeue rear
q.dequeue_front()
print(q)  # after dequeue front

if not self.head: # empty dequeue self.head = self.tail = new_node

handle empty dequeue by setting head and tail to new node

new_node.next = self.head self.head.prev = new_node self.head = new_node

insert new node at front and update pointers

if not self.tail: # empty dequeue self.head = self.tail = new_node

handle empty dequeue by setting head and tail to new node

self.tail.next = new_node new_node.prev = self.tail self.tail = new_node

insert new node at rear and update pointers

self.head = self.head.next if self.head: self.head.prev = None else: self.tail = None

remove front node and update head and tail pointers

self.tail = self.tail.prev if self.tail: self.tail.next = None else: self.head = None

remove rear node and update tail and head pointers

Output

3 -> 1 -> 2 -> null

3 -> 1 -> null

1 -> null

Complexity Analysis

Time: O(1) for all enqueue and dequeue operations because we only update pointers at ends

Space: O(n) because we store n nodes in the linked list

vs Alternative: Compared to array-based dequeue, linked list avoids shifting elements, so operations at both ends are always O(1)

Edge Cases

empty dequeue

enqueue sets head and tail to new node; dequeue returns None safely

DSA Python

if not self.head:  # empty dequeue
    self.head = self.tail = new_node

single element dequeue

dequeue removes node and sets head and tail to None

DSA Python

else:
    self.tail = None  # dequeue is empty now

multiple enqueues and dequeues

pointers update correctly to maintain list integrity

DSA Python

self.head.prev = None
self.tail.next = None

When to Use This Pattern

When you need to add or remove items from both ends efficiently, use a dequeue with a doubly linked list to get O(1) operations.

Common Mistakes

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

Mistake: Not handling empty dequeue case leading to errors
Fix: Check if head or tail is None before operations and handle accordingly

Summary

Implements a dequeue using a doubly linked list allowing fast add/remove at both ends.

Use when you want a flexible queue that supports operations at front and rear efficiently.

The key is to keep track of both head and tail pointers and update next and prev links carefully.