Dequeue Using Linked List in DSA Python - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Dequeue Operations

What is the printed state of the dequeue after these operations?

Operations:
1. Add 10 at rear
2. Add 20 at rear
3. Add 5 at front
4. Remove from rear
5. Add 15 at front

DSA Python

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

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

    def add_front(self, data):
        new_node = Node(data)
        if self.front is None:
            self.front = self.rear = new_node
        else:
            new_node.next = self.front
            self.front.prev = new_node
            self.front = new_node

    def add_rear(self, data):
        new_node = Node(data)
        if self.rear is None:
            self.front = self.rear = new_node
        else:
            self.rear.next = new_node
            new_node.prev = self.rear
            self.rear = new_node

    def remove_front(self):
        if self.front is None:
            return None
        data = self.front.data
        self.front = self.front.next
        if self.front is None:
            self.rear = None
        else:
            self.front.prev = None
        return data

    def remove_rear(self):
        if self.rear is None:
            return None
        data = self.rear.data
        self.rear = self.rear.prev
        if self.rear is None:
            self.front = None
        else:
            self.rear.next = None
        return data

    def display(self):
        current = self.front
        result = []
        while current:
            result.append(str(current.data))
            current = current.next
        print(" -> ".join(result) + " -> null")

dq = Dequeue()
dq.add_rear(10)
dq.add_rear(20)
dq.add_front(5)
dq.remove_rear()
dq.add_front(15)
dq.display()

A 5 -> 10 -> 15 -> null

B 15 -> 5 -> 10 -> null

C 15 -> 10 -> 5 -> null

D 10 -> 5 -> 15 -> null

💡 Hint

Trace each operation step-by-step, updating front and rear pointers.

After adding 10 and 20 at rear, dequeue is 10 -> 20. Adding 5 at front makes it 5 -> 10 -> 20. Removing rear removes 20, leaving 5 -> 10. Adding 15 at front results in 15 -> 5 -> 10.

🧠 Conceptual

intermediate

Number of Nodes After Operations

If you start with an empty dequeue and perform these operations:
add_front(1), add_rear(2), add_front(3), remove_rear(), remove_front(), add_rear(4)
How many nodes remain in the dequeue?

A 0

B 1

C 3

D 2

💡 Hint

Count nodes after each operation carefully.

Operations add 1 (front), 2 (rear), 3 (front) → 3 nodes. Removing rear removes 2 → 2 nodes. Removing front removes 3 → 1 node. Adding 4 at rear → 2 nodes total.

🔧 Debug

advanced

Identify the Bug in remove_front Method

What error will occur when calling remove_front on a dequeue with only one node, given this code snippet?

DSA Python

def remove_front(self):
    if self.front is None:
        return None
    data = self.front.data
    self.front = self.front.next
    self.front.prev = None
    return data

A No error, returns data correctly

B TypeError: unsupported operand type(s)

C AttributeError: 'NoneType' object has no attribute 'prev'

D IndexError: list index out of range

💡 Hint

Consider what happens when front becomes None after removal.

When the only node is removed, self.front becomes None. Then self.front.prev causes AttributeError because None has no attribute 'prev'.

❓ Predict Output

advanced

Output After Mixed Add and Remove Operations

What is the printed state of the dequeue after these operations?

Operations:
add_rear(7)
add_front(3)
add_rear(9)
remove_front()
remove_rear()
add_front(1)
add_rear(11)
display()

DSA Python

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

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

    def add_front(self, data):
        new_node = Node(data)
        if self.front is None:
            self.front = self.rear = new_node
        else:
            new_node.next = self.front
            self.front.prev = new_node
            self.front = new_node

    def add_rear(self, data):
        new_node = Node(data)
        if self.rear is None:
            self.front = self.rear = new_node
        else:
            self.rear.next = new_node
            new_node.prev = self.rear
            self.rear = new_node

    def remove_front(self):
        if self.front is None:
            return None
        data = self.front.data
        self.front = self.front.next
        if self.front is None:
            self.rear = None
        else:
            self.front.prev = None
        return data

    def remove_rear(self):
        if self.rear is None:
            return None
        data = self.rear.data
        self.rear = self.rear.prev
        if self.rear is None:
            self.front = None
        else:
            self.rear.next = None
        return data

    def display(self):
        current = self.front
        result = []
        while current:
            result.append(str(current.data))
            current = current.next
        print(" -> ".join(result) + " -> null")

dq = Dequeue()
dq.add_rear(7)
dq.add_front(3)
dq.add_rear(9)
dq.remove_front()
dq.remove_rear()
dq.add_front(1)
dq.add_rear(11)
dq.display()

A 1 -> 7 -> 11 -> null

B 3 -> 7 -> 9 -> null

C 7 -> 11 -> null

D 1 -> 9 -> 11 -> null

💡 Hint

Track the front and rear after each operation carefully.

Start: empty add_rear(7): 7 add_front(3): 3 -> 7 add_rear(9): 3 -> 7 -> 9 remove_front(): removes 3 → 7 -> 9 remove_rear(): removes 9 → 7 add_front(1): 1 -> 7 add_rear(11): 1 -> 7 -> 11

🧠 Conceptual

expert

Time Complexity of Dequeue Operations Using Linked List

What is the time complexity of add_front, add_rear, remove_front, and remove_rear operations in a dequeue implemented using a doubly linked list?

A All operations are O(1)

B add_front and add_rear are O(1), remove_front and remove_rear are O(n)

C add_front and remove_front are O(1), add_rear and remove_rear are O(n)

D All operations are O(n)

💡 Hint

Consider how pointers are updated in a doubly linked list.

In a doubly linked list, both ends are directly accessible. Adding or removing nodes at front or rear involves only pointer changes, so all operations take constant time O(1).

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