Skip to main content
CodeFlow
data structures~14 minRoute 02 2 of 9

Linked List

A chain of nodes — fast inserts, no random access.

Prerequisites:Arrays & Lists

Story — a chain of paper notes

Imagine notes scattered across a table — but each note ends with "next: see the green note". To read them in order, you start at the first one (the head) and follow the pointer on each note to the next.

That's a linked list. Each node holds a value and a pointer to the next node. The list ends when a node points to null (the "no more notes" signal).

Linker says

The trade: I can insert anywhere in O(1) if I have a pointer to the spot — no shifting. But I can't jump to the middle by index; I have to walk there.

See it — head, tail, the chain

Each node shows its value and a pointer (●) to the next. Watch insert-at-head zip in instantly; insert-at-tail walks the chain.

  1. A●
  2. B●
  3. C●

Three nodes, each pointing to the next.

length = 3 · head = A

✎ Sharpen your pencil

After watching insert-at-head and insert-at-tail, explain in one sentence why one is fast and the other is slow.

Linker says

I trade random access for cheap insertions. Adding a node at the head costs the same whether I have 10 nodes or 10 million.

Try it — when does an array beat a list?

Exercise. You need a structure that supports (a) frequent inserts at the front, (b) very rare reads, and (c) no random access. Array or linked list?

Reveal answer

Linked list. Front-insert is O(1) for a list, O(n) for an array. With no random-access requirement, you don't pay for the linked list's slow indexing.

Code it — five languages, one chain

Most languages don't ship a linked list — you build one with a tiny Node class (or struct) holding a value and a pointer to the next. The shape repeats: one node knows itself and one neighbour.

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

# build A -> B -> C
c = Node("C")
b = Node("B", c)
head = Node("A", b)

print(head.value)         # "A"
print(head.next.value)    # "B"

Quiz it — make it stick

  1. Question 1

    You have a linked list of 1,000,000 nodes. How long does it take to access the 500,000th element?

  2. True or false — Question 2

    Inserting at the head of a linked list is faster than inserting at the head of a dynamic array.

  3. Predict — Question 3

    After this snippet runs, what does head.next.next.value print?

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

c = Node("C")
b = Node("B", c)
head = Node("A", b)
print(head.next.next.value)

No Dumb Questions

Real questions other learners asked on this page.

  • Why use a linked list when arrays exist?
    Cheap front-insert, cheap mid-insert when you already have a pointer to the spot. Useful inside other data structures (queues, LRU caches). For most application code, a dynamic array is better — fewer allocations, better cache behaviour.
  • What's a doubly-linked list?
    Each node has a `prev` pointer too — so you can walk backward as well as forward. Costs more memory per node; pays for itself when you need bidirectional traversal or O(1) removal of an arbitrary node.
  • Are linked lists slower than arrays in practice?
    Often yes — modern CPUs are much faster reading contiguous memory than chasing pointers. Linked lists win on big-O for specific operations but can lose on real benchmarks because of cache misses.