• The number of nodes in the list is in the range [0, 10⁴]
• -10⁵ <= Node.val <= 10⁵

A linked list stores the same thing an array does — a run of values in order — but it stores it in a completely different shape, and that shape decides what is cheap and what is expensive. Before any algorithm, we have to understand the shape, because every technique in this section is a consequence of it.

Recall how an array lives in memory: one solid, contiguous block, its elements numbered 0, 1, 2, … Because the block is unbroken and every slot is the same size, the machine can compute the address of element k with plain arithmetic — start address plus k times slot size — and jump straight there. That is why arr[k] is instant for any k.

A linked list makes no such promise. Its elements — called nodes — are scattered anywhere in memory, with no relationship between their addresses. Each node is a tiny package holding two things: a value, and a pointer named next that stores the memory address of the following node. The final node's next holds a special empty value, null, meaning "the chain stops here." One separate pointer, the head, holds the address of the very first node. That is the whole structure — a value and an arrow to the next one, repeated.

Because the addresses are unrelated, no arithmetic can hand you the k-th node. The only thing any node knows is where the next one lives. So to reach node k you must physically stand on node 0, follow its arrow to node 1, follow that to node 2, and so on — k hops, no shortcut. This single fact is the root of every linked-list algorithm you will meet.

Walking the chain from head to tail is traversal. You keep one pointer — call it curr — start it at the head, do whatever the task needs with curr.val, then advance it by overwriting it with curr.next. When curr becomes null you have stepped off the end, and you stop.

curr = head
while curr:                # stop when we step off the end (null)
    process(curr.val)      # e.g. print it, compare it, add it to a total
    curr = curr.next       # follow the arrow to the next node

Two details in that loop are load-bearing. First, the condition tests curr itself, not curr.next: an empty list has head == null, so the test fails on entry and we correctly do nothing — no special case required. Second, the last line moves the pointer, not the data; curr = curr.next doesn't touch the list, it only re-aims our own finger at the next node.

Each node is visited exactly once, and the work at a node is a fixed handful of operations — read a value, follow one pointer. So an N-node list costs about N steps: O(N) time, linear — double the list, double the work. And no method can beat O(N) for a full traversal, because the only route to the last node runs through all the earlier ones. Space is O(1): we hold a single curr pointer no matter how long the list grows.

That same fact has a sharp consequence: reaching one specific node by position also costs O(N), not O(1). An array gives you arr[k] for free; a linked list charges you k hops. This is the deal the structure strikes — it gives up instant random access in exchange for cheap insertion and deletion in the middle, where you only rewire a couple of arrows instead of shifting every later element over.

And the empty case, head = [ ]: head is null from the start, the body never runs, and we report nothing — the exact same loop, no extra if.

Everything ahead is traversal with a job bolted on: sometimes you carry a second pointer moving at a different speed (finding the middle, detecting a cycle), sometimes you rewire arrows as you pass (reversing, deleting), sometimes you walk two lists at once (merging). But the skeleton never changes — start at head, act, follow next, stop at null — and two questions decide every linked-list problem: what extra information must I carry as I walk? and if I rewire a link, did I save what it pointed to first? Train that pair of questions now; they are the whole game.