Programming Concepts

Foundational Data Structures~20 min

Linked Structures as a Mental Model

A list stores items contiguously so any position is instant to reach; a linked structure connects separate nodes by reference, trading that instant access for cheap insertion.

By the end of this lesson, you can

  • Explain the difference between a list's contiguous storage and a linked structure's node-and-reference storage
  • Trace how following next references connects separate nodes into a chain
  • Explain the trade-off between the two — fast insertion versus fast access by position

Why it matters

A Python list stores its items one after another, which is why items[5] is instant no matter how long the list is — Python jumps straight there. That same layout is also why inserting into the middle of a long list is comparatively expensive: everything after the new item has to shift over to make room. A linked structure makes the opposite trade: no shifting on insertion, at the cost of instant access by position.

Mental model

Instead of one contiguous block, a linked structure is a chain of separate nodes, each holding a value and a reference to the next node. Nothing requires the nodes to sit next to each other anywhere — the chain of references is what connects them, wherever they actually are.

PythonTwo nodes, linked by reference
first = {"value": 10, "next": None}
second = {"value": 30, "next": None}
first["next"] = second

current = first
while current is not None:
    print(current["value"])
    current = current["next"]
Output
10
30

Each node here is a small dictionary with a value and a next reference. first["next"] = second is the entire connection — nothing about where either dictionary actually lives in memory matters. Traversal follows next one node at a time, stopping when it reaches None.

Inserting without shifting

PythonInserting a node between two existing ones
middle = {"value": 20, "next": second}
first["next"] = middle

current = first
while current is not None:
    print(current["value"])
    current = current["next"]
Output
10
20
30

Inserting middle touched exactly two references: middle["next"] (set to second) and first["next"] (changed to point at middle instead of second). second itself was never touched — nothing had to shift, no matter how long the chain was before or after this node.

Trace it

Two reference changes are the entire insertion
Stepfirst["next"]middle["next"]Chain, start to end
before insertionsecond(middle doesn't exist yet)10 -> 30
middle = {..., "next": second}secondsecond(middle not yet linked in)
first["next"] = middlemiddlesecond10 -> 20 -> 30

Check your understanding

Given first -> second -> third (in that order), what prints after this runs? new_node = {"value": 99, "next": third} second["next"] = new_node current = first while current is not None: print(current["value"]) current = current["next"]
Or reveal the answer without checking

Answer:first's value, second's value, 99, then third's value
second["next"] now points at new_node, and new_node["next"] already points at third — so traversal follows first -> second -> new_node (99) -> third, in that order.

Why does inserting into the middle of a linked structure avoid the shifting a list requires?
Or reveal the answer without checking

Answer:A node doesn't need to be contiguous with its neighbors, so inserting one only means updating a couple of next references, not moving anything
A list's contiguous layout is exactly what forces a shift on insertion. A linked structure never relies on contiguity, so connecting a new node in is just a couple of reference updates, regardless of where in the chain it happens.

Practice: warm-up

Trace this chain-building program — write down the full chain, in order, after each step.

a = {"value": "A", "next": None}
b = {"value": "B", "next": None}
c = {"value": "C", "next": None}

a["next"] = b
b["next"] = c

Stuck? Reveal one hint at a time.

  1. Hint 1

    After only a["next"] = b, does the chain include c yet?

  2. Hint 2

    Follow next from a all the way to None to write out the full chain at each step.

Reveal the trace

Try the problem yourself before reading this. There is often more than one reasonable approach — treat this as one worked example, not the only correct answer.

after a["next"] = b:              A -> B          (c not yet linked in)
after b["next"] = c:              A -> B -> C

Practice: apply it

This code is meant to insert a node holding "X" right after a, but a node silently disappears from the chain:

a = {"value": "A", "next": None}
b = {"value": "B", "next": None}
a["next"] = b

x = {"value": "X", "next": None}
a["next"] = x
Tracing from a to None, what's actually in the chain now?
Or reveal the answer without checking

Answer:A -> X (B has been silently dropped from the chain)
x["next"] was never set to b, so once a["next"] points at x, nothing in the chain still references b at all — it still exists as a value, but traversal from a can no longer reach it.

Modification challenge: fix this by setting x["next"] = b before reassigning a["next"] = x, so b stays reachable in the chain.

Summary

  • A list stores items contiguously, making access by position instant but insertion in the middle expensive, since everything after has to shift.
  • A linked structure connects separate nodes by reference — a value plus a next pointer — so nodes never need to be contiguous.
  • Inserting a node into a linked structure only means updating a couple of references, regardless of chain length — no shifting.
  • The trade-off: reaching a specific position in a linked structure means following references one at a time from the start, with no equivalent of a list’s instant items[i].

Key terms