Dequeue Using Linked List in DSA Python - Execution Trace

Concept Flow - Dequeue Using Linked List

Create new node

↓

Is dequeue empty?

Yes→Set head and tail to new node

No↓

Add at front or rear?

↓

Insert at head

↓

Update pointers

↓

Done

↓

Is dequeue empty?

Yes→Underflow error

No↓

Remove from front or rear?

↓

Delete head

↓

Update pointers

↓

Done

Shows how nodes are added or removed from front or rear in a linked list based dequeue, updating pointers accordingly.

Execution Sample

DSA Python

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

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

    def insert_rear(self, val):
        new_node = Node(val)
        if not self.tail:
            self.head = self.tail = new_node
        else:
            self.tail.next = new_node
            self.tail = new_node

    def delete_front(self):
        if not self.head:
            return None
        val = self.head.val
        self.head = self.head.next
        if not self.head:
            self.tail = None
        return val

This code inserts at the rear and deletes from the front of a dequeue implemented with a linked list.

Execution Table

Step	Operation	Nodes in List	Pointer Changes	Visual State
1	Insert 10 at rear	10	head -> 10, tail -> 10	10 -> null
2	Insert 20 at rear	10 -> 20	tail.next -> 20, tail -> 20	10 -> 20 -> null
3	Insert 30 at rear	10 -> 20 -> 30	tail.next -> 30, tail -> 30	10 -> 20 -> 30 -> null
4	Delete front	20 -> 30	head -> 20	20 -> 30 -> null
5	Delete front	30	head -> 30	30 -> null
6	Delete front	empty	head -> None, tail -> None	null
7	Delete front (empty)	empty	No change	null

💡 Stops after deleting all nodes; next delete returns None as dequeue is empty.

Variable Tracker

Variable	Start	After Step 1	After Step 2	After Step 3	After Step 4	After Step 5	After Step 6	After Step 7
head	None	Node(10)	Node(10)	Node(10)	Node(20)	Node(30)	None	None
tail	None	Node(10)	Node(20)	Node(30)	Node(30)	Node(30)	None	None
List Size	0	1	2	3	2	1	0	0

Key Moments - 3 Insights

Why does the tail pointer update only when inserting at rear?

Because tail always points to the last node. When inserting at rear (see Step 2 and 3), tail moves to new node. In deletion from front (Step 4-6), tail changes only if list becomes empty (Step 6).

What happens when deleting from an empty dequeue?

No pointers change and operation returns None (Step 7). This prevents errors by checking if head is None before deletion.

Why does the head pointer move forward on deletion?

Deleting front removes the first node, so head moves to next node (Step 4 and 5). This effectively removes the old front node from the list.

Visual Quiz - 3 Questions

Look at the execution table, what is the visual state after Step 3?

A 20 -> 30 -> null

B 10 -> 20 -> 30 -> null

C 30 -> null

D null

💡 Hint

Check the 'Visual State' column in Step 3 of the execution table.

At which step does the dequeue become empty?

A Step 5

B Step 4

C Step 6

D Step 7

💡 Hint

Look at the 'Nodes in List' and 'Pointer Changes' columns to see when head and tail become None.

If we insert 40 at rear after Step 6, what will be the new visual state?

A 40 -> null

B 30 -> 40 -> null

C null

D 10 -> 20 -> 30 -> 40 -> null

💡 Hint

After Step 6, list is empty. Inserting at rear sets head and tail to new node only.

Concept Snapshot

Dequeue using linked list:
- Insert at front or rear by adding nodes and updating head/tail pointers.
- Delete from front or rear by removing nodes and updating pointers.
- If list empty, head and tail are None.
- Tail updates only on rear insert or when list becomes empty.
- Head moves forward on front deletion.

Full Transcript

This visual trace shows how a dequeue works using a linked list. We add nodes at the rear by creating a new node and linking it after the tail, then moving the tail pointer. Deletion from the front removes the head node and moves the head pointer forward. When the list becomes empty, both head and tail become None. Trying to delete from an empty dequeue returns None safely. The execution table tracks each step's operation, the nodes present, pointer changes, and the visual linked list state. Variable tracker shows how head, tail, and list size change after each step. Key moments clarify why pointers update as they do and how empty conditions are handled. The quiz tests understanding of list state at key steps and effects of operations.

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