Doubly Linked List

Jr Codex DSA Notes

Level: Intermediate Prerequisites: Chapter 1 Time to complete: ~20 minutes

Table of Contents

1. What a Doubly Linked List Adds
2. The Node Class
3. Insertion
4. Deletion
5. Backward Traversal
6. Complexity Comparison
7. Summary & Next Steps

1. What a Doubly Linked List Adds

A singly linked list (Chapter 1) can only move forward, and deleting a node requires a separate search just to find its predecessor. A doubly linked list gives every node a prev pointer in addition to next — at the cost of one extra pointer's worth of memory per node, you gain O(1) deletion (given a reference to the node) and the ability to traverse in either direction.

None ← [ 3 | prev | next ] ⇄ [ 7 | prev | next ] ⇄ [ 1 | prev | next ] → None

2. The Node Class

class Node:
    def __init__(self, value):
        self.value = value
        self.next = None
        self.prev = None
 
class DoublyLinkedList:
    def __init__(self):
        self.head = None
        self.tail = None       # tracked explicitly — this is what makes tail ops O(1)

3. Insertion

def insert_at_tail(dll, value):
    new_node = Node(value)
    if dll.tail is None:            # empty list
        dll.head = new_node
        dll.tail = new_node
        return
    new_node.prev = dll.tail
    dll.tail.next = new_node
    dll.tail = new_node
    # O(1) — no traversal needed, because dll.tail is tracked directly
 
def insert_at_head(dll, value):
    new_node = Node(value)
    if dll.head is None:
        dll.head = new_node
        dll.tail = new_node
        return
    new_node.next = dll.head
    dll.head.prev = new_node
    dll.head = new_node
    # O(1)

Compare this to Chapter 1's singly linked insert_at_tail, which was O(n) without a tracked tail pointer. A doubly linked list makes tracking tail "free" to use in both directions, since tail.prev lets you walk backward from it too.

4. Deletion

def delete_node(dll, node):
    if node.prev is not None:
        node.prev.next = node.next
    else:
        dll.head = node.next          # node was the head
 
    if node.next is not None:
        node.next.prev = node.prev
    else:
        dll.tail = node.prev          # node was the tail
    # O(1) — given a direct reference to `node`, no search needed at all

This is the headline advantage over a singly linked list: deletion is O(1) given the node, because node.prev already tells you what to rewire — no separate O(n) search for the predecessor.

5. Backward Traversal

def print_backward(tail):
    current = tail
    while current is not None:
        print(current.value, end=" -> ")
        current = current.prev
    print("None")
    # O(n) — impossible on a singly linked list without extra bookkeeping

6. Complexity Comparison

The doubly linked list's advantages aren't free — every node carries an extra pointer, and every insert/delete must maintain twice as many links (easy to introduce bugs by forgetting to update one side). Python's collections.deque (Module 5) is implemented internally using a doubly linked structure of blocks, which is exactly why it offers O(1) operations at both ends.

7. Summary & Next Steps

Key Takeaways

• A doubly linked list adds a prev pointer to each node, enabling O(1) deletion given a node reference and backward traversal.
• The tradeoff is one extra pointer per node and more bookkeeping on every insert/delete.
• Python's deque (Module 5, Chapter 4) relies on this idea internally to achieve O(1) operations at both ends.

Concept Check

1. Why is deleting a node O(1) in a doubly linked list but O(n) in a singly linked list (given only a reference to the node itself)?
2. What's the memory cost of adding the prev pointer, and when might that cost not be worth it?
3. Why does collections.deque use a structure related to doubly linked lists?

Next Chapter

→ Chapter 3: Common Linked List Patterns

Jr Codex — 1-on-1 Personalized Coaching | Back to Module Index