Why Doubly Linked List Over Singly Linked List in DSA Python - Why This Pattern

Mental Model

A doubly linked list lets you move forward and backward easily, unlike a singly linked list which only moves forward.

Analogy: Think of a train with cars connected front and back. You can walk from the first car to the last or go back from the last to the first. A singly linked list is like a train where you can only walk forward.

Head -> 1 ↔ 2 ↔ 3 ↔ 4 -> null
Each node points both ways with arrows ← and ->

Dry Run Walkthrough

Input: list: 1->2->3, delete last node

Goal: Show how deleting the last node is easier with a doubly linked list than with a singly linked list

Step 1: Start at head node 1

Head -> 1 ↔ 2 ↔ 3 -> null

Why: We begin at the start to find the last node

Step 2: Move forward to node 2

Head -> 1 ↔ [curr->2] ↔ 3 -> null

Why: We need to reach the last node to delete it

Step 3: Move forward to node 3 (last node)

Head -> 1 ↔ 2 ↔ [curr->3] -> null

Why: We found the last node to delete

Step 4: Use backward pointer from node 3 to node 2 and remove node 3

Head -> 1 ↔ 2 -> null

Why: Backward pointer lets us directly access node before last to update its next pointer

Result:

Head -> 1 ↔ 2 -> null
Last node deleted easily using backward pointer

Annotated Code

DSA Python

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

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

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

    def delete_last(self):
        if not self.head:
            return
        curr = self.head
        while curr.next:
            curr = curr.next  # advance curr to last node
        if curr.prev:
            curr.prev.next = None  # remove last node by updating prev node's next
        else:
            self.head = None  # list had one node, now empty

    def print_list(self):
        curr = self.head
        res = []
        while curr:
            res.append(str(curr.val))
            curr = curr.next
        print(" -> ".join(res) + " -> null")

# Driver code
dll = DoublyLinkedList()
dll.append(1)
dll.append(2)
dll.append(3)
dll.print_list()  # before deletion

dll.delete_last()
dll.print_list()  # after deletion

while curr.next: curr = curr.next # advance curr to last node

move curr forward to reach last node

if curr.prev: curr.prev.next = None # remove last node by updating prev node's next

use backward pointer to unlink last node quickly

else: self.head = None # list had one node, now empty

handle case when list has only one node

Output

1 -> 2 -> 3 -> null

1 -> 2 -> null

Complexity Analysis

Time: O(n) because we traverse nodes to reach the last one

Space: O(n) for storing n nodes in the list

vs Alternative: Singly linked list requires traversing to the second last node to delete last, no backward pointer to jump back, so doubly linked list saves time in backward operations

Edge Cases

empty list

delete_last does nothing safely

DSA Python

if not self.head:
    return

list with one node

head becomes None after deletion

DSA Python

else:
    self.head = None  # list had one node, now empty

When to Use This Pattern

When you need to move both forward and backward in a list or delete nodes from the end efficiently, reach for doubly linked list because it has backward pointers.

Common Mistakes

Mistake: Trying to delete last node in singly linked list without tracking previous node
Fix: Use a doubly linked list or keep track of previous node during traversal

Summary

Doubly linked list allows easy forward and backward traversal.

Use it when you need to delete or insert nodes from both ends efficiently.

The key is having pointers in both directions to avoid costly traversals.