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.

Practice

1. What is a dequeue (double-ended queue) implemented using a linked list?

easy

A. A queue where elements can only be added at the rear

B. A list that only allows insertion at the front

C. A stack implemented using arrays

D. A data structure where elements can be added or removed from both ends

Solution

1. Step 1: Understand dequeue operations

   A dequeue allows insertion and deletion from both front and rear ends.

2. Step 2: Linked list implementation

   Using a linked list, nodes can be added or removed from both ends efficiently.

3. Final Answer:

   A data structure where elements can be added or removed from both ends -> Option D

4. Quick Check:

   Dequeue = double-ended queue [OK]

Hint: Dequeue means double-ended queue, both ends allowed [OK]

Common Mistakes:

• Confusing dequeue with stack or simple queue
• Thinking insertion is only at one end
• Assuming array implementation only

2. Which of the following is the correct way to initialize an empty dequeue using a linked list in Python?

easy

A. class Dequeue: def __init__(self): self.front = None; self.rear = None

B. class Dequeue: def __init__(self): self.list = []

C. class Dequeue: def __init__(self): self.head = 0; self.tail = 0

D. class Dequeue: def __init__(self): self.front = 0; self.rear = 0

Solution

1. Step 1: Identify linked list pointers

   For linked list, front and rear pointers are initialized to None to indicate empty.

2. Step 2: Check options

   class Dequeue: def __init__(self): self.front = None; self.rear = None correctly initializes front and rear as None; others use incorrect types or structures.

3. Final Answer:

   class Dequeue: def __init__(self): self.front = None; self.rear = None -> Option A

4. Quick Check:

   Linked list empty pointers = None [OK]

Hint: Empty linked list pointers are None, not zero or list [OK]

Common Mistakes:

• Using list instead of linked list
• Initializing pointers with 0 instead of None
• Confusing front/rear with indices

3. What will be the output after performing these operations on an empty dequeue implemented with linked list?
dq.insert_rear(10)
dq.insert_front(20)
dq.insert_rear(30)
dq.delete_front()
Print the dequeue from front to rear.

medium

A. 20 -> 10 -> 30 -> null

B. 20 -> 30 -> null

C. 10 -> 30 -> null

D. 30 -> 10 -> 20 -> null

Solution

1. Step 1: Perform insert_rear(10) on empty dequeue

   Dequeue becomes: 10 -> null

2. Step 2: Perform insert_front(20)

   Dequeue becomes: 20 -> 10 -> null

3. Step 3: Perform insert_rear(30)

   Dequeue becomes: 20 -> 10 -> 30 -> null

4. Step 4: Perform delete_front()

   Remove 20 from front, dequeue becomes: 10 -> 30 -> null

5. Final Answer:

   10 -> 30 -> null -> Option C

6. Quick Check:

   After operations, front to rear = 10, 30 [OK]

Hint: Track each operation stepwise front to rear [OK]

Common Mistakes:

• Forgetting delete_front removes front element
• Mixing order of insert_front and insert_rear
• Printing rear to front instead of front to rear

4. Identify the error in this dequeue linked list method for deleting from rear:

def delete_rear(self):
    if self.rear is None:
        return None
    temp = self.rear
    self.rear = self.rear.next
    return temp.data

medium

A. Does not check if dequeue is empty

B. Incorrectly moves rear pointer forward instead of backward

C. Returns data before deleting node

D. Uses wrong variable name for rear

Solution

1. Step 1: Understand rear pointer movement

   In linked list, rear points to last node; to delete rear, rear must move backward (to previous node).

2. Step 2: Analyze code

   Code moves rear to rear.next (forward), which is incorrect for rear deletion.

3. Final Answer:

   Incorrectly moves rear pointer forward instead of backward -> Option B

4. Quick Check:

   Rear deletion moves pointer backward [OK]

Hint: Rear deletion moves pointer backward, not forward [OK]

Common Mistakes:

• Moving rear pointer forward instead of backward
• Not handling empty dequeue properly
• Confusing front and rear pointers

5. You want to implement a dequeue using a doubly linked list to support these operations efficiently:
1. Insert at front
2. Insert at rear
3. Delete from front
4. Delete from rear

Which of the following is the best approach to maintain pointers for O(1) time complexity for all operations?

hard

A. Maintain front and rear pointers; each node has next and prev links

B. Maintain only front pointer; traverse list for rear operations

C. Use singly linked list with only next pointers and rear pointer

D. Use array to simulate linked list with indices

Solution

1. Step 1: Understand operation requirements

   All operations must be O(1), so no traversal allowed.

2. Step 2: Analyze pointer needs

   Doubly linked list with front and rear pointers allows insert/delete at both ends in O(1).

3. Step 3: Check options

   Maintain front and rear pointers; each node has next and prev links matches this approach; others require traversal or use arrays which are not linked lists.

4. Final Answer:

   Maintain front and rear pointers; each node has next and prev links -> Option A

5. Quick Check:

   Doubly linked list + front/rear pointers = O(1) ops [OK]

Hint: Use doubly linked list with front and rear pointers [OK]

Common Mistakes:

• Using singly linked list causing O(n) rear operations
• Maintaining only one pointer causing traversal
• Confusing arrays with linked lists