Linked Lists — Chaining Nodes Together

Build the mental model

An array stores values contiguously in memory, so indexing into it is O(1), but deleting or inserting anywhere except the end requires shifting every following element, making that O(n). A linked list solves this differently: each value lives in its own independently allocated node, and each node holds a pointer to the next one instead of relying on physical adjacency. Inserting at the head just means rewiring two pointers — O(1), no shifting anything. That flexibility has a cost, though: there is no index to jump to, so reaching the k-th node means walking pointer by pointer from the head, which is O(n). This is the fundamental array-vs-linked-list trade-off — arrays win when you need fast random access by position, linked lists win when you're constantly inserting or removing at a known point (especially the front) and rarely need to jump around. Neither structure is universally 'better'; the right choice depends entirely on which operation your workload does more of.

Connect it to a real scenario

The Tutorial Platform's lesson navigation naturally maps to a linked list — each lesson node points to the 'next lesson' in the course, so clicking 'Next Lesson' is an O(1) hop. When an editor inserts a new lesson early in a course's sequence, there's no need to re-index the whole list — just rewire two pointers, exactly like head insertion.

Each node holds a value plus a pointer to the next node
Insert/delete at the head is O(1) — no shifting required
Reaching the n-th node requires walking from the head, so it's O(n)

Try the working example

python

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

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

    def insert_at_head(self, value):
        # O(1): just relink the head pointer, no shifting needed
        self.head = Node(value, self.head)

    def print_list(self):
        # O(n): must walk pointer by pointer from the head
        current = self.head
        items = []
        while current:
            items.append(str(current.value))
            current = current.next
        print(" -> ".join(items))

ll = LinkedList()
for lesson in ["intro", "variables", "loops"]:
    ll.insert_at_head(lesson)
ll.print_list()

You should see

Prints "loops -> variables -> intro" — since each insert happens at the head, the most recently inserted lesson appears first.

5-minute try-it

Add a `delete_head()` method to the LinkedList class that removes the head node and makes its `next` the new head — explain why this is O(1).

One important caution

Forgetting to update `self.head` after wiring the new node's `next` — the list still points to the old head, so the insert silently has no effect

Trying to index into a linked list like an array (`ll[3]`) — there's no such operation; you must traverse node by node, which is exactly the O(n) cost this lesson explains

Wikipedia — Linked list — Data Structures & Algorithms