Linked Lists (Singly & Doubly)

Trade contiguous memory for flexible, pointer-based structure, and learn when that trade pays off

Introduction

Lesson 2 showed that arrays pay a real cost for their O(1) indexing: inserting or removing anywhere but the end forces every following element to shift. A linked list takes the opposite trade-off. Instead of one contiguous block, each element lives in its own node, wired to the next one by a pointer. That gives up random access entirely, finding the 500th element means walking 500 pointers, but it makes insertion and removal at a known position a simple, constant-time pointer rewire, no shifting required.

Anatomy of a Singly Linked List

A singly linked list is a chain of nodes. Each node stores a value and a reference to the next node. The list itself only needs to remember one thing: the head, the first node in the chain.

Singly Linked List

123Nonenextnextnext

Figure 1: Each node only knows about the node in front of it

class Node:
    def __init__(self, value: int) -> None:
        self.value = value
        self.next: "Node | None" = None

That's the entire building block. Everything a linked list can do, prepending, appending, searching, deleting, comes down to walking this chain and rewiring next pointers.

Singly Linked List Operations

A minimal singly linked list needs four core operations: adding to the front, adding to the back, finding a value, and deleting a value.

class SinglyLinkedList:
    def __init__(self) -> None:
        self.head: "Node | None" = None

    def prepend(self, value: int) -> None:
        # O(1): no shifting, just relink the head pointer
        new_node = Node(value)
        new_node.next = self.head
        self.head = new_node

    def append(self, value: int) -> None:
        # O(n): this implementation has no tail pointer, so it must
        # walk the whole list to find the last node
        new_node = Node(value)
        if self.head is None:
            self.head = new_node
            return
        current = self.head
        while current.next is not None:
            current = current.next
        current.next = new_node

    def find(self, value: int) -> "Node | None":
        # O(n): no random access, must walk from the head
        current = self.head
        while current is not None:
            if current.value == value:
                return current
            current = current.next
        return None

    def delete(self, value: int) -> bool:
        # O(n) to find the node, O(1) to unlink it once found
        previous = None
        current = self.head
        while current is not None:
            if current.value == value:
                if previous is None:
                    self.head = current.next
                else:
                    previous.next = current.next
                return True
            previous = current
            current = current.next
        return False

    def to_list(self) -> list[int]:
        values: list[int] = []
        current = self.head
        while current is not None:
            values.append(current.value)
            current = current.next
        return values
ll = SinglyLinkedList()
ll.append(1)
ll.append(2)
ll.append(3)
ll.prepend(0)
print(ll.to_list())

ll.delete(2)
print(ll.to_list())
Expected Output:
[0, 1, 2, 3]
[0, 1, 3]
Notice What's O(1) and What's Not
  • prepend is O(1), it only touches the head
  • append is O(n) here, because this implementation has no tail pointer
  • find and delete are O(n), both may need to walk the whole list

Doubly Linked Lists

A doubly linked list gives every node a second pointer, back to the previous node, and the list keeps track of both a head and a tail. The extra pointer per node costs memory, but it unlocks backward traversal and O(1) removal when you already hold a reference to the node you want to remove.

Doubly Linked List

123nextprevnextprev

Figure 2: Every node can be walked forward or backward

class DNode:
    def __init__(self, value: int) -> None:
        self.value = value
        self.prev: "DNode | None" = None
        self.next: "DNode | None" = None
class DoublyLinkedList:
    def __init__(self) -> None:
        self.head: "DNode | None" = None
        self.tail: "DNode | None" = None

    def append(self, value: int) -> DNode:
        # O(1): the tail pointer means no traversal is ever needed
        new_node = DNode(value)
        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
        return new_node

    def remove(self, node: DNode) -> None:
        # O(1): both neighbors are already reachable from "node" itself
        if node.prev is not None:
            node.prev.next = node.next
        else:
            self.head = node.next

        if node.next is not None:
            node.next.prev = node.prev
        else:
            self.tail = node.prev

    def to_list(self) -> list[int]:
        values: list[int] = []
        current = self.head
        while current is not None:
            values.append(current.value)
            current = current.next
        return values
dll = DoublyLinkedList()
a = dll.append(1)
b = dll.append(2)
c = dll.append(3)
print(dll.to_list())

dll.remove(b)   # remove(b) needs no search: b already knows its neighbors
print(dll.to_list())
Expected Output:
[1, 2, 3]
[1, 3]

Python's collections.deque, the tool Lesson 2 recommended for O(1) insertion and removal at both ends, is built on this same doubly linked idea. CPython's real implementation doesn't link one node per element though, it links together fixed-size blocks of elements, trading a little of the pure doubly linked list's flexibility for much better cache performance.

Arrays vs Linked Lists

Neither structure is universally "better", each optimizes for a different access pattern.

OperationDynamic ArraySingly Linked ListDoubly Linked List
Access by indexO(1)O(n)O(n)
Search by valueO(n)O(n)O(n)
Insert / delete at headO(n)O(1)O(1)
Insert / delete at tailO(1) amortizedO(1)* insert / O(n) deleteO(1)
Insert / delete given a node referenceO(n)O(n) (predecessor unknown)O(1)
Extra memory per elementnone1 pointer2 pointers

*Only if a tail pointer is maintained. Even then, deleting the last node of a singly linked list is O(n), you can jump straight to the tail, but you can't step backward to find its new predecessor without a full traversal.

Practical Pattern: Reversing a Linked List

One of the most common linked list exercises: reverse the direction of every pointer using only O(1) extra space, no new list, no recursion stack required.

def reverse(head: "Node | None") -> "Node | None":
    previous = None
    current = head
    while current is not None:
        next_node = current.next   # save it before we overwrite current.next
        current.next = previous    # point backward instead of forward
        previous = current
        current = next_node
    return previous                # previous is now the new head

Start (prev = ∅, cur = 1)

1cur23

Step 1: 1's link flips to ∅

1prev2cur3

Step 2: 2 points back to 1

12prev3cur

Step 3: done, head = 3

123prev = head

Figure 3: Reversing 1 → 2 → 3. Each step flips one node's next to aim at the previous node (amber), while cur walks forward. After three steps every arrow has reversed and prev sits on the new head, 3.

Walking Through It

Three pointers do all the work: previous trails behind, current is the node being rewired, and next_node is saved before the link is broken so the rest of the list isn't lost. By the time current reaches the end, previous is sitting on the old last node, the new head.

Bonus: Detecting a Cycle with Floyd's Tortoise and Hare

A bug (or an intentional circular structure) can make a linked list loop back on itself, turning a simple traversal into an infinite loop. The classic O(n) time, O(1) space solution uses two pointers moving at different speeds:

def has_cycle(head: "Node | None") -> bool:
    # Floyd's Tortoise and Hare: two pointers, one twice as fast as the other
    slow = head
    fast = head
    while fast is not None and fast.next is not None:
        slow = slow.next
        fast = fast.next.next
        if slow is fast:
            # If there's a cycle, the fast pointer eventually laps the slow one
            return True
    return False

If there's no cycle, fast reaches the end first. If there is a cycle, fast eventually wraps around and catches up to slow from behind, the same way a faster runner eventually laps a slower one on a circular track.

Key Takeaways

  • Linked lists trade random access for O(1) rewiring - no shifting is ever required to insert or delete a known node
  • Singly linked lists only point forward, so deleting an arbitrary node needs its predecessor, which means a traversal
  • Doubly linked lists add a prev pointer per node, enabling O(1) removal when you already hold the node
  • Access and search are still O(n) for both variants - there is no way to "jump" to an arbitrary position
  • Python's collections.deque is a production-ready doubly linked list, reach for it instead of writing your own
Data Structures & AlgorithmsLesson 3