09. Linked Lists — Singly, Doubly, Circular

What problem does this solve? Arrays store elements in contiguous memory — inserting or deleting at the front costs O(n) because all elements must shift. Linked lists store elements in separate nodes connected by pointers, allowing O(1) insertion/deletion at known positions.

1. Singly Linked List — The Foundation

Mental Model

Node Structure

python
Run Inline
# runnable
class Node:
    """A node in a singly linked list."""
    def __init__(self, data):
        self.data = data
        self.next = None
    def __repr__(self):
        return f"Node({self.data})"

Full Singly Linked List Implementation

python
Run Inline
# runnable
class SinglyLinkedList:
    def __init__(self):
        self.head = None
        self.tail = None
        self._size = 0
    def __len__(self):
        return self._size
    def __repr__(self):
        nodes = []
        curr = self.head
        while curr:
            nodes.append(str(curr.data))
            curr = curr.next
        return " → ".join(nodes) if nodes else "Empty"
    # ---- Insertion ----
    def add_first(self, data):
        """Insert at head. O(1)"""
        new_node = Node(data)
        new_node.next = self.head
        self.head = new_node
        if self.tail is None:  # Was empty
            self.tail = new_node
        self._size += 1
    def add_last(self, data):
        """Insert at tail. O(1) with tail pointer."""
        new_node = Node(data)
        if self.tail is None:  # Empty list
            self.head = self.tail = new_node
        else:
            self.tail.next = new_node
            self.tail = new_node
        self._size += 1
    def add_after(self, prev_node, data):
        """Insert after a given node. O(1)"""
        if prev_node is None:
            raise ValueError("Previous node cannot be None")
        new_node = Node(data)
        new_node.next = prev_node.next
        prev_node.next = new_node
        if prev_node == self.tail:
            self.tail = new_node
        self._size += 1
    # ---- Deletion ----
    def remove_first(self):
        """Remove head. O(1)"""
        if self.head is None:
            raise IndexError("Remove from empty list")
        data = self.head.data
        self.head = self.head.next
        if self.head is None:  # List is now empty
            self.tail = None
        self._size -= 1
        return data
    def remove_last(self):
        """Remove tail. O(n) — need to find second-to-last."""
        if self.head is None:
            raise IndexError("Remove from empty list")
        if self.head == self.tail:  # Single element
            data = self.head.data
            self.head = self.tail = None
            self._size -= 1
            return data
        # Traverse to find second-to-last
        curr = self.head
        while curr.next != self.tail:
            curr = curr.next
        # Now curr is second-to-last
        data = self.tail.data
        curr.next = None
        self.tail = curr
        self._size -= 1
        return data
    # ---- Search ----
    def search(self, target):
        """Find target in list. O(n)"""
        curr = self.head
        while curr:
            if curr.data == target:
                return True
            curr = curr.next
        return False
    # ---- Utility ----
    def reverse(self):
        """Reverse the list in-place. O(n)"""
        prev = None
        curr = self.head
        self.tail = self.head  # Old head becomes new tail
        while curr:
            next_temp = curr.next
            curr.next = prev
            prev = curr
            curr = next_temp
        self.head = prev
# Test
sll = SinglyLinkedList()
sll.add_last(10)
sll.add_last(20)
sll.add_last(30)
sll.add_first(5)
print(f"List: {sll}")          # 5 → 10 → 20 → 30
print(f"Length: {len(sll)}")   # 4
sll.reverse()
print(f"Reversed: {sll}")      # 30 → 20 → 10 → 5
print(f"Removed first: {sll.remove_first()}")  # 30
print(f"After remove: {sll}")  # 20 → 10 → 5

Operation Complexities

2. Doubly Linked List

Mental Model

Implementation

python
Run Inline
# runnable
class DNode:
    def __init__(self, data):
        self.data = data
        self.prev = None
        self.next = None
    def __repr__(self):
        return f"DNode({self.data})"
class DoublyLinkedList:
    def __init__(self):
        self.head = None
        self.tail = None
        self._size = 0
    def __len__(self):
        return self._size
    def __repr__(self):
        nodes = []
        curr = self.head
        while curr:
            nodes.append(str(curr.data))
            curr = curr.next
        return " ↔ ".join(nodes) if nodes else "Empty"
    def add_first(self, data):
        """Insert at head. O(1)"""
        new_node = DNode(data)
        if self.head is None:
            self.head = self.tail = new_node
        else:
            new_node.next = self.head
            self.head.prev = new_node
            self.head = new_node
        self._size += 1
    def add_last(self, data):
        """Insert at tail. O(1)"""
        new_node = DNode(data)
        if self.tail is None:
            self.head = self.tail = new_node
        else:
            new_node.prev = self.tail
            self.tail.next = new_node
            self.tail = new_node
        self._size += 1
    def remove_first(self):
        """Remove head. O(1)"""
        if self.head is None:
            raise IndexError("Remove from empty list")
        data = self.head.data
        self.head = self.head.next
        if self.head:
            self.head.prev = None
        else:
            self.tail = None
        self._size -= 1
        return data
    def remove_last(self):
        """Remove tail. O(1) — key advantage over singly linked."""
        if self.tail is None:
            raise IndexError("Remove from empty list")
        data = self.tail.data
        self.tail = self.tail.prev
        if self.tail:
            self.tail.next = None
        else:
            self.head = None
        self._size -= 1
        return data
    def remove_node(self, node):
        """Remove a specific node given its reference. O(1)"""
        if node.prev:
            node.prev.next = node.next
        else:
            self.head = node.next
        if node.next:
            node.next.prev = node.prev
        else:
            self.tail = node.prev
        self._size -= 1
# Test
dll = DoublyLinkedList()
dll.add_last(10)
dll.add_last(20)
dll.add_last(30)
dll.add_first(5)
print(f"Doubly: {dll}")           # 5 ↔ 10 ↔ 20 ↔ 30
print(f"Removed last: {dll.remove_last()}")  # 30
print(f"After: {dll}")            # 5 ↔ 10 ↔ 20

3. Circular Linked List

Mental Model

Key Uses

• Round-robin scheduling (process scheduling in OS)
• Repeat playlists (music players)
• Josephus problem (counting out)

python
Run Inline
# runnable
class CircularLinkedList:
    def __init__(self):
        self.head = None
        self._size = 0
    def add(self, data):
        """Add to end (which wraps to head)."""
        new_node = Node(data)
        if self.head is None:
            self.head = new_node
            new_node.next = new_node  # Points to itself
        else:
            # Traverse to last node
            curr = self.head
            while curr.next != self.head:
                curr = curr.next
            curr.next = new_node
            new_node.next = self.head
        self._size += 1
    def traverse(self, steps):
        """Traverse n steps from head, showing each node."""
        curr = self.head
        result = []
        for _ in range(steps):
            result.append(str(curr.data))
            curr = curr.next
        return " → ".join(result)
cll = CircularLinkedList()
cll.add(1)
cll.add(2)
cll.add(3)
print(f"Circular (10 steps): {cll.traverse(10)}")
# 1 → 2 → 3 → 1 → 2 → 3 → 1 → 2 → 3 → 1

4. Comparison: Linked List vs Array

5. Common Bugs

python
Run Inline
# BUG 1: Losing the rest of the list when inserting
def buggy_insert(self, data):
    new_node = Node(data)
    curr = self.head
    while curr and curr.data < data:
        curr = curr.next
    # curr is now at insertion point
    new_node.next = curr.next  # Bug: curr might be None!
    curr.next = new_node        # Bug: curr might be None!
# BUG 2: Forgetting to update tail
def buggy_add_last(self, data):
    new_node = Node(data)
    self.tail.next = new_node
    self.tail = new_node      # Correct: must update tail
# BUG 3: Creating a cycle (infinitely looping list)
def buggy_add(self, data):
    new_node = Node(data)
    curr = self.head
    while curr.next:  # This never terminates if there's a cycle!
        curr = curr.next
    curr.next = new_node
# BUG 4: Forgetting to handle empty list
def buggy_remove_first(self):
    self.head = self.head.next  # AttributeError if self.head is None!

6. Applications of Linked Lists

• Undo functionality in editors (doubly linked list of states)
• Music playlist (circular for repeat, or doubly for prev/next)
• Hash table chaining (linked list at each bucket)
• Adjacency list for graphs (linked list of neighbors)
• Memory management (free lists in operating systems)
• Browser history (back/forward navigation)

Practice Questions

Answers

A1.

python
Run Inline
def has_cycle(head):
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow == fast:
            return True
    return False

A2.

python
Run Inline
def find_middle(head):
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
    return slow.data

A3. You need to find the node BEFORE the tail to update its next to None. In a singly linked list, you can only traverse forward from the head, requiring O(n) traversal.

A4.

python
Run Inline
def merge_sorted(l1, l2):
    dummy = Node(0)
    tail = dummy
    while l1 and l2:
        if l1.data <= l2.data:
            tail.next = l1
            l1 = l1.next
        else:
            tail.next = l2
            l2 = l2.next
        tail = tail.next
    tail.next = l1 or l2
    return dummy.next

A5. Doubly linked list allows O(1) push/pop at both ends. Singly linked needs O(n) to pop from the tail.

A6. Stack needs push/pop at same end. Singly linked list with head pointer gives O(1) for both. Array-based stack (Python list) is more cache-friendly and generally faster.

A7. Iterative shown above. Recursive:

python
Run Inline
def reverse_recursive(node, prev=None):
    if node is None:
        return prev
    next_node = node.next
    node.next = prev
    return reverse_recursive(next_node, node)

A8. Find middle (2), reverse second half (5→4→3), then interleave.

A9. Array cache locality means modern CPUs can traverse arrays ~10-50x faster than linked lists due to cache misses. The O(n) insert at front is acceptable because Python's list amortizes over many operations.

A10.

python
Run Inline
def josephus(n, k):
    # Create circular list of 1..n
    head = Node(1)
    curr = head
    for i in range(2, n + 1):
        curr.next = Node(i)
        curr = curr.next
    curr.next = head  # Make circular

    prev, curr = curr, head
    while prev.next != prev:  # More than 1 node
        for _ in range(k - 1):
            prev = curr
            curr = curr.next
        prev.next = curr.next  # Remove curr
        curr = prev.next
    return curr.data  # Survivor