Singly vs Doubly Linked Lists

Linked lists come in several structural varieties. The two most common are the Singly Linked List (unidirectional) and the Doubly Linked List (bidirectional).

Singly Linked List (SLL)

In a Singly Linked List, each node points only forward to its successor (next).

Copy codeHead
 |
 v
[ 10 | * ] ---> [ 20 | * ] ---> [ 30 | null ]

Advantages:

• Smaller Memory Footprint: Only one reference pointer (next) per node.
• Simpler implementation with fewer pointer updates during insertion and deletion.

Limitations:

• One-way traversal: You cannot step backward.
• Deletion is awkward: Deleting a given node N requires traversing from head to find the node immediately preceding N in O(n) time.

Doubly Linked List (DLL)

In a Doubly Linked List, each node maintains two reference pointers:

1. next: Points to the successor node.
2. prev: Points to the predecessor node.

Copy codeHead                                         Tail
 |                                            |
 v                                            v
null <-- [ * | 10 | * ] <===> [ * | 20 | * ] <===> [ * | 30 | * ] --> null

In Kotlin:

Copy codeclass DoublyNode<T>(
    var data: T,
    var prev: DoublyNode<T>? = null,
    var next: DoublyNode<T>? = null
)

Deletion Comparison: The Decisive Advantage of DLL

Consider deleting a node target when you already hold a direct reference to it:

In Singly Linked List: O(n)

You cannot modify prev.next because you don't know who prev is! You must scan from head:

Copy code// Singly Linked List: O(n) traversal needed to find predecessor
fun deleteNode(head: Node<T>, target: Node<T>) {
    var curr = head
    while (curr.next != null && curr.next != target) {
        curr = curr.next!!
    }
    curr.next = target.next // Bypass target
}

In Doubly Linked List: O(1)

Because the node knows its predecessor (node.prev), removal is instantaneous:

Copy code// Doubly Linked List: O(1) constant time removal!
fun deleteNode(target: DoublyNode<T>) {
    target.prev?.next = target.next
    target.next?.prev = target.prev
    target.prev = null
    target.next = null
}

This O(1) node self-deletion is why LRU Caches and Android Navigation Stacks rely on Doubly Linked Lists.

Comprehensive Comparison Matrix

Summary

• Choose Singly Linked Lists when memory is constrained and traversal is strictly forward (e.g., hash collision buckets).
• Choose Doubly Linked Lists when bidirectional navigation or O(1) node removal is needed (e.g., LRU cache, text editor cursors).