Why Doubly Linked List Over Singly Linked List in DSA Python - Challenge Your Understanding

Challenge - 5 Problems

🧠 Conceptual

intermediate

Why use a doubly linked list instead of a singly linked list?

Which of the following is the main advantage of a doubly linked list over a singly linked list?

A It allows traversal in both forward and backward directions.

B It uses less memory per node than a singly linked list.

C It requires fewer pointers to manage the list.

D It can only be traversed from the head to the tail.

💡 Hint

Think about how you can move through the list in both directions.

A doubly linked list has two pointers per node, allowing traversal forward and backward. A singly linked list only allows forward traversal.

❓ Predict Output

intermediate

Output of traversing a doubly linked list backwards

What will be the output of the following code that traverses a doubly linked list backwards?

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
        self.tail = None

    def append(self, data):
        new_node = Node(data)
        if not self.head:
            self.head = new_node
            self.tail = new_node
        else:
            self.tail.next = new_node
            new_node.prev = self.tail
            self.tail = new_node

    def traverse_backward(self):
        current = self.tail
        result = []
        while current:
            result.append(current.data)
            current = current.prev
        print(' -> '.join(map(str, result)) + ' -> null')

# Create list and append elements
dll = DoublyLinkedList()
dll.append(1)
dll.append(2)
dll.append(3)
dll.traverse_backward()

A 1 -> 2 -> 3 -> null

B 3 -> 2 -> 1 -> null

C null -> 3 -> 2 -> 1

D 1 -> null

💡 Hint

Look at how the traversal starts from the tail and moves using the prev pointer.

The traversal starts at the tail node (3) and moves backward using the prev pointer, printing 3, then 2, then 1.

🔧 Debug

advanced

Identify the bug in doubly linked list node removal

What is the error in the following code that removes a node from a doubly linked list?

DSA Python

def remove_node(node):
    if node.prev:
        node.prev.next = node.next
    if node.next:
        node.next.prev = node.prev
    node = None

A The node is not properly disconnected because setting 'node = None' only changes the local reference.

B The code will raise an AttributeError if node.prev is None.

C The code does not update the head or tail pointers of the list.

D The code will cause a memory leak by not freeing the node.

💡 Hint

Think about what 'node = None' does inside the function.

Setting 'node = None' only changes the local variable inside the function, it does not remove references to the node outside the function.

❓ Predict Output

advanced

Result of inserting a node in the middle of a doubly linked list

What will be the printed output after inserting a node with value 4 between nodes 3 and 5?

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 insert_after(self, prev_node, data):
        if not prev_node:
            return
        new_node = Node(data)
        new_node.next = prev_node.next
        new_node.prev = prev_node
        if prev_node.next:
            prev_node.next.prev = new_node
        prev_node.next = new_node

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

# Setup list
dll = DoublyLinkedList()
dll.append(1)
dll.append(3)
dll.append(5)

# Insert 4 after 3
current = dll.head
while current and current.data != 3:
    current = current.next

dll.insert_after(current, 4)
dll.print_list()

A 1 -> 4 -> 3 -> 5 -> null

B 1 -> 3 -> 5 -> null

C 1 -> 3 -> 5 -> 4 -> null

D 1 -> 3 -> 4 -> 5 -> null

💡 Hint

Check how the new node is linked between 3 and 5.

The new node with value 4 is inserted after node 3 and before node 5, so the list becomes 1 -> 3 -> 4 -> 5 -> null.

🧠 Conceptual

expert

Memory trade-offs of doubly linked lists

Why might a doubly linked list be less memory efficient than a singly linked list?

A Because doubly linked lists store nodes in contiguous memory blocks.

B Because doubly linked lists require extra memory for storing data values twice.

C Because each node stores two pointers, increasing memory usage per node.

D Because doubly linked lists use recursion which consumes more stack memory.

💡 Hint

Think about how many pointers each node holds in both list types.

Doubly linked list nodes have two pointers (prev and next), so they use more memory per node than singly linked lists, which have only one pointer.