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.