Nodes and Pointers

lesson 4-1 · ~13 min · 10/29

Quiz

Warm-up from lesson 2-3: inserting at the FRONT of an array is O(n). Why?

Chains instead of blocks

A linked list stores items in separate nodes scattered anywhere in memory. Each node holds two things:

a value
a pointer called next: a reference to the following node (or None at the end)

A pointer is just an address, like the ones you computed in lesson 2-1, except now stored inside the data instead of derived from a formula. The list itself keeps only one thing: a pointer to the first node, the head.

Since nodes don't need to sit side by side, inserting a node never shifts anything: you create it and rewire one or two pointers. The price: there is no index formula anymore. To reach item i you must traverse, following next pointers one hop at a time from the head. Reading by position becomes O(n).

Traversal: `current` starts at the head and hops along `next` pointers until it reaches None. Reaching node i costs i hops.

Code exercise · python

Run this. A Node class is tiny: a value and a next pointer. We wire three nodes into a chain by hand, then traverse from the head printing each value, exactly like the animated figure.

Code exercise · python

Your turn: two traversal utilities. `length(head)` hops through the whole chain counting nodes. `value_at(head, i)` takes exactly i hops from the head and returns that node's value. Both are the loop from the demo above with a different job.

Quiz

In a linked list with 1,000 nodes, what does reading the 700th value cost, and why?