Linear Structures

Linked lists

Nodes and pointers: cheap inserts, slow lookups

~11 minLesson 5 of 25Written by Claude Opus 4.8

Give up instant random access, and in return you can splice a new element into the middle of your data by writing just two pointers - no shifting, no copying.

An array is a single unbroken slab of memory: element $i$ lives at $ba se + i \times s i z e$ , so you can leap straight to it - but inserting in the middle means shoving every later element over by one. A makes the opposite trade. Its elements are scattered , each carrying a little arrow - a - to the next one. To insert, you don't move anything. You just re-aim a couple of arrows.

The idea in one line

A node = your data + a pointer to the next node. The list is held together only by those pointers, starting from a head reference. Nothing is contiguous, so there is no "index

i

" to jump to - but that same looseness means inserting or deleting is just rewiring, not shifting.

A node is data plus a pointer

Every node stores two things: a value and a next pointer holding the memory address of the following node. Follow next from the head and you visit the whole list; the last node's next is null, marking the tail. Because there's no formula from index to address, reaching the $i$ -th node means traversing - walking $i$ hops from the head.

Singly linked - each node points only forward (next). Compact; you can only walk one direction.
Doubly linked - each node also holds a prev pointer, so you can walk backward and delete a node given only itself. The cost is an extra pointer per node to keep consistent.

Rewire it yourself - the playground

Below, boxes are nodes at fixed spots in "memory"; arrows are next pointers. Pick an operation and step through it: the highlighted arrow is the single pointer being written at that step. Watch closely - the boxes never move. Only the arrows change. That is the whole personality of a linked list.

Pointer-rewiring playground: choose an operation, then step it one pointer-write at a time. The boxes never move, only the arrows change.

box live nodedashed box free memoryarrow next-pointerarrow pointer being written this step

valueat position

position

HEAD -> 10 -> 20 -> 30 -> 40 -> null

Singly-linked list in memory. Boxes are nodes; arrows are next-pointers. Pick an operation and step through the rewiring.

The "aha": rewiring, not shifting

An array insert-in-the-middle touches up to

n

elements - everything after the gap slides over. The linked-list insert you just stepped through touches exactly two pointers, no matter how long the list is. The nodes' physical positions are irrelevant; the list's order lives entirely in the arrows.

Where the costs actually land

Insertion and deletion are

O (1)

given a pointer to the spot - you rewire a constant number of links. The catch is getting that pointer. To reach position

k

you must traverse from the head:

find position k = O (k) \leq O (n), then splice = O (1) .

So "insert at the head" is a true

O (1)

win, but "insert at position

k

you haven't reached yet" is dominated by the

O (k)

walk. Compare that to an array, where finding index

k

O (1)

but the splice is

O (n)

. The two structures move the cost to opposite ends.

A sentinel makes the edges disappear

Insertion and deletion have annoying special cases at the head (there's no predecessor to rewire). A (or dummy) node - a permanent, value-less node sitting before the real head - gives every real node a predecessor. Now "insert at head" is just "insert after the sentinel," and one code path handles all positions. It's a tiny trick that erases a whole class of null-check bugs.

The code is just two assignments

A node is a two-field record; inserting after a node you already hold is a pair of pointer writes. Order matters: wire the new node's next before you redirect the predecessor, or you'll lose the rest of the list.

class Node:
    def __init__(self, value):
        self.value = value
        self.next  = None          # pointer to the next Node (or None = tail)

def insert_after(node, value):
    fresh = Node(value)
    fresh.next = node.next        # 1. new node points at the old successor
    node.next  = fresh            # 2. predecessor now points at the new node
    # two writes, O(1) - nothing else in the list is touched

Two writes, O(1) - nothing else in the list is touched.

Array vs. linked list - the whole tradeoff

Neither wins outright. Pick the structure whose cheap operations match what your program does most.

Operation	Array (contiguous)	Singly linked list
Access $i$ -th element	O(1)	O(n)
Insert / delete at head	O(n)	O(1)
Insert / delete after a held node	O(n)	O(1)
Search for a value	O(n)	O(n)
Memory per element	value only	value + pointer(s)
Cache locality	excellent (neighbors adjacent)	poor (nodes scattered)

The hidden tax: cache locality

Big-O says "search a value" is

O (n)

for both - but on real hardware, walking an array is often far faster. The CPU pulls in whole cache lines, so an array's neighbors ride along for free. A linked list's nodes live wherever the allocator put them, so each hop can be a fresh cache miss. Linked lists shine when you're constantly splicing at known points, not when you're scanning.

Check yourself

To insert a node right after a node you already hold a pointer to, how many pointers change?

Which task is O(1) on an array but O(n) on a singly linked list?

What does inserting into the middle of a linked list cost, and why is it different from an array?

Tie the O(1) splice to the two pointer writes. Try to state it, then check.

Lock it in

A node is a value plus a next pointer; the list is just those pointers from a head.
Insert and delete are two pointer writes, O(1) once you hold the spot - no shifting.
The catch is reaching position k: traversal is O(k), so array and list flip the cost.
A sentinel node gives the head a predecessor and erases the edge-case null checks.
Arrays win on random access and cache locality; lists win on splicing at known points.

Primary source

Harvard's CS50x builds pointers and linked lists from raw memory in C - the best way to feel that a "pointer" really is an address. To watch insert, delete, and search animate on your own input, drive the USF Data Structure Visualizations (see the Linked List page).

Ask your teacher (where this reappears)

Want to see how a doubly linked list makes prev-deletion

O (1)

, or how skip lists layer pointers to regain fast search? Ask me. Here's the LLM tie-in, spelled out in memoization and queues to the KV cache in the LLM course: during text generation, an LLM's KV cache grows like an append-only linked list - the keys and values for each past token are computed once and the list is extended by a single node per new token, never recomputed or shifted. Same "extend one node at a time" move you just animated.