Create and Initialize Doubly Linked List in DSA Python - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Doubly Linked List after Insertions

What is the printed state of the doubly linked list after inserting nodes with values 10, 20, and 30 at the end?

DSA Python

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

class DoublyLinkedList:
    def __init__(self):
        self.head = None

    def append(self, data):
        new_node = Node(data)
        if not self.head:
            self.head = new_node
            return
        last = self.head
        while last.next:
            last = last.next
        last.next = new_node
        new_node.prev = last

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

dl = DoublyLinkedList()
dl.append(10)
dl.append(20)
dl.append(30)
dl.print_list()

A 10 -> 20 -> 30 -> null

B 30 <-> 20 <-> 10 <-> null

C 10 <-> 20 <-> 30 <-> null

D null <-> 10 <-> 20 <-> 30

💡 Hint

Trace the append method and how nodes link forward and backward.

The append method adds nodes at the end. The print_list method prints nodes from head to tail separated by <-> . So the output shows 10 linked to 20 linked to 30, ending with null.

❓ Predict Output

intermediate

State of Doubly Linked List after Prepending Nodes

What is the printed state of the doubly linked list after prepending nodes with values 5, 15, and 25 in that order?

DSA Python

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

class DoublyLinkedList:
    def __init__(self):
        self.head = None

    def prepend(self, data):
        new_node = Node(data)
        new_node.next = self.head
        if self.head:
            self.head.prev = new_node
        self.head = new_node

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

dl = DoublyLinkedList()
dl.prepend(5)
dl.prepend(15)
dl.prepend(25)
dl.print_list()

A 25 <-> 15 <-> 5 <-> null

B 5 <-> 15 <-> 25 <-> null

C null <-> 25 <-> 15 <-> 5

D 15 <-> 25 <-> 5 <-> null

💡 Hint

Prepending adds nodes at the start, so the last prepended node becomes the head.

Each prepend adds a new node before the current head. The last prepended node (25) becomes the new head. So the list is 25 linked to 15 linked to 5, ending with null.

🔧 Debug

advanced

Identify the Bug in Doubly Linked List Node Removal

What error will occur when trying to remove the node with value 20 using the given remove method?

DSA Python

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

class DoublyLinkedList:
    def __init__(self):
        self.head = None

    def append(self, data):
        new_node = Node(data)
        if not self.head:
            self.head = new_node
            return
        last = self.head
        while last.next:
            last = last.next
        last.next = new_node
        new_node.prev = last

    def remove(self, data):
        current = self.head
        while current:
            if current.data == data:
                if current.prev:
                    current.prev.next = current.next
                else:
                    self.head = current.next
                if current.next:
                    current.next.prev = current.prev
                return
            current = current.next

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

dl = DoublyLinkedList()
dl.append(10)
dl.append(20)
dl.append(30)
dl.remove(20)
dl.print_list()

A ValueError: data not found

B No error, output: 10 <-> 30 <-> null

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

D TypeError: unsupported operand type(s) for +: 'int' and 'NoneType'

💡 Hint

Check what happens when removing the head node and how head is updated.

The bug is fixed by updating the else block inside remove: when removing the head node, it sets self.head = current.next correctly. This ensures the head is updated properly and no AttributeError occurs.

❓ Predict Output

advanced

Output after Reversing a Doubly Linked List

What is the printed state of the doubly linked list after reversing it?

DSA Python

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

class DoublyLinkedList:
    def __init__(self):
        self.head = None

    def append(self, data):
        new_node = Node(data)
        if not self.head:
            self.head = new_node
            return
        last = self.head
        while last.next:
            last = last.next
        last.next = new_node
        new_node.prev = last

    def reverse(self):
        current = self.head
        temp = None
        while current:
            temp = current.prev
            current.prev = current.next
            current.next = temp
            current = current.prev
        if temp:
            self.head = temp.prev

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

dl = DoublyLinkedList()
dl.append(1)
dl.append(2)
dl.append(3)
dl.append(4)
dl.reverse()
dl.print_list()

A 4 <-> 3 <-> 2 <-> 1 <-> null

B 1 <-> 2 <-> 3 <-> 4 <-> null

C null <-> 4 <-> 3 <-> 2 <-> 1

D 1 -> 2 -> 3 -> 4 -> null

💡 Hint

Reversing swaps next and prev pointers for each node and updates head to last node.

The reverse method swaps the next and prev pointers for each node. After the loop, head is updated to the last node processed. So the list order is reversed: 4 linked to 3 linked to 2 linked to 1, ending with null.

🧠 Conceptual

expert

Memory Usage in Doubly Linked List vs Singly Linked List

Which statement correctly explains the difference in memory usage between a doubly linked list and a singly linked list?

A A singly linked list uses more memory because it requires additional pointers to keep track of the previous node.

B A doubly linked list uses less memory because it can be traversed in both directions, reducing the need for extra nodes.

C Both doubly and singly linked lists use the same memory per node because pointers are optimized automatically by the system.

D A doubly linked list uses more memory per node because it stores two pointers (prev and next), while a singly linked list stores only one pointer (next).

💡 Hint

Consider how many pointers each node stores in both list types.

Each node in a doubly linked list stores two pointers: one to the previous node and one to the next node. A singly linked list node stores only one pointer to the next node. Therefore, doubly linked lists use more memory per node.

Practice

1. What is the main difference between a doubly linked list and a singly linked list?

easy

A. A doubly linked list can only be traversed forward.

B. A doubly linked list stores data in arrays instead of nodes.

C. A doubly linked list has nodes with pointers to both next and previous nodes.

D. A doubly linked list does not have a head pointer.

Solution

1. Step 1: Understand node structure in doubly linked list

   Each node in a doubly linked list contains two pointers: one to the next node and one to the previous node.

2. Step 2: Compare with singly linked list

   A singly linked list node has only one pointer to the next node, so it can only be traversed forward.

3. Final Answer:

   A doubly linked list has nodes with pointers to both next and previous nodes. -> Option C

4. Quick Check:

   Doubly linked list nodes have two pointers = C [OK]

Hint: Remember: doubly linked list nodes link both ways [OK]

Common Mistakes:

• Thinking doubly linked list uses arrays
• Assuming it can only go forward
• Confusing head pointer presence

2. Which of the following is the correct way to define a node class for a doubly linked list in Python?

easy

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

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

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

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

Solution

1. Step 1: Identify required attributes for doubly linked list node

   A doubly linked list node must have data, a pointer to the next node, and a pointer to the previous node.

2. Step 2: Check each option for completeness

   class Node: def __init__(self, data): self.data = data self.next = None self.prev = None correctly defines data, next, and prev attributes initialized properly.

3. Final Answer:

   class Node with data, next, and prev attributes initialized -> Option A

4. Quick Check:

   Node needs data, next, prev = A [OK]

Hint: Doubly linked list node needs both next and prev pointers [OK]

Common Mistakes:

• Omitting prev pointer
• Omitting data attribute
• Defining next and prev but missing data

3. What will be the output of the following code that creates a doubly linked list with nodes containing 1, 2, 3?

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

class DoublyLinkedList:
    def __init__(self):
        self.head = None

    def append(self, data):
        new_node = Node(data)
        if not self.head:
            self.head = new_node
            return
        last = self.head
        while last.next:
            last = last.next
        last.next = new_node
        new_node.prev = last

    def display_forward(self):
        current = self.head
        result = []
        while current:
            result.append(current.data)
            current = current.next
        return result

dll = DoublyLinkedList()
dll.append(1)
dll.append(2)
dll.append(3)
print(dll.display_forward())

medium

A. [3, 2, 1]

B. []

C. [1, 3, 2]

D. [1, 2, 3]

Solution

1. Step 1: Append nodes 1, 2, 3 to the doubly linked list

   Nodes are added at the end. First node 1 becomes head, then 2 is linked after 1, then 3 after 2.

2. Step 2: Display nodes forward

   Starting from head, nodes are visited in order 1 -> 2 -> 3, collected in list [1, 2, 3].

3. Final Answer:

   [1, 2, 3] -> Option D

4. Quick Check:

   Appending nodes in order shows [1, 2, 3] [OK]

Hint: Appending adds nodes at end; display forward shows insertion order [OK]

Common Mistakes:

• Confusing order of nodes
• Printing empty list if head is null
• Mixing up forward and backward traversal

4. Identify the error in the following code that tries to append nodes to a doubly linked list:

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

class DoublyLinkedList:
    def __init__(self):
        self.head = None

    def append(self, data):
        new_node = Node(data)
        if self.head is None:
            self.head = new_node
        else:
            last = self.head
            while last.next:
                last = last.next
            last.next = new_node
            new_node.next = last

medium

A. new_node.next should be new_node.prev to link backward

B. Missing return statement after setting head

C. The while loop condition should be last.prev instead of last.next

D. Node class is missing data attribute

Solution

1. Step 1: Analyze append method's linking logic

   After finding last node, code sets last.next = new_node correctly, but sets new_node.next = last, which is wrong.

2. Step 2: Correct backward link pointer

   Backward link should be new_node.prev = last, not new_node.next = last.

3. Final Answer:

   new_node.next should be new_node.prev to link backward -> Option A

4. Quick Check:

   Backward link uses prev pointer = D [OK]

Hint: Backward link uses prev, not next pointer [OK]

Common Mistakes:

• Setting new_node.next instead of new_node.prev
• Forgetting to link backward pointer
• Confusing next and prev pointers

5. You want to create a doubly linked list from a Python list of values [10, 20, 30] and then print the list backward starting from the last node. Which code snippet correctly initializes the doubly linked list and prints the values backward?

hard

A. dll = DoublyLinkedList()
for val in [10, 20, 30]:
dll.append(val)
current = dll.head
while current.prev:
current = current.prev
while current:
print(current.data, end=' ')
current = current.next

B. dll = DoublyLinkedList()
for val in [10, 20, 30]:
dll.append(val)
current = dll.head
while current.next:
current = current.next
while current:
print(current.data, end=' ')
current = current.prev

C. dll = DoublyLinkedList()
for val in [10, 20, 30]:
dll.append(val)
current = dll.head
while current.next:
current = current.next
while current:
print(current.data, end=' ')
current = current.next

D. dll = DoublyLinkedList()
for val in [10, 20, 30]:
dll.append(val)
current = dll.head
while current.prev:
current = current.prev
while current:
print(current.data, end=' ')
current = current.prev

Solution

1. Step 1: Append values 10, 20, 30 to doubly linked list

   Values are appended in order, head points to 10, last node is 30.

2. Step 2: Move to last node by traversing next pointers

   Start at head, move forward while current.next exists to reach last node (30).

3. Step 3: Print backward by moving prev pointers

   From last node, print data and move backward using current.prev until null.

4. Final Answer:

   Traverse forward to the last node using next pointers, then print backward using prev pointers, producing 30 20 10 -> Option B

5. Quick Check:

   Traverse next to last, then prev backward = A [OK]

Hint: Go forward to last node, then traverse backward with prev [OK]

Common Mistakes:

• Trying to move backward from head
• Using next pointer to go backward
• Not moving to last node before backward print