Start with five integers [10, 20, 30, 40, 50] held two ways: an array in consecutive slots, and a linked list of five nodes where each node holds a value plus the address of the next. Read the element at position 3, which is 40, in both layouts.
1. Choose contiguous or linked storage
The array sits in one block, so position i lives at base + i × size. The list scatters five nodes across the heap, each pointing to the next, so position i has no address formula and must be reached by hopping.
2. Locate the target position
Array: compute the address for index 3 and issue one load. List: start at the head (10), follow its pointer to 20, then to 30, then to 40. That is four node visits for position 3, and each hop depends on the last, so the CPU cannot overlap the loads.
3. Read the element
Both return 40. The array used one address calculation and one memory read, and the cache line it fetched already holds its neighbors. The list used four pointer reads, each a potential cache miss in a different line.
4. Note what an insert would move
Inserting 35 before 40 flips the costs. The array shifts 40 and 50 one slot right, touching every later element. The list, once it stands on the 30 node, rewires two pointers and touches nothing else. Locating the spot still costs the walk; only the rewiring is O(1).
5. Return with the cost counted
Random access: array O(1), list O(n). Middle insert after locating: array O(n) shifts, list O(1) rewires. Scans favor the array because consecutive bytes stream through cache, while the list pays a pointer chase per node. That is why vectors beat lists on most real workloads, as in Arrays and Linked Lists.
Hardware, runtime, and observability notes
When tracing Trace an Array Read Against a Linked List Walk in a live production environment (subsystem: memory, primary layer: runtime), keep the following step-level cost model and diagnostic checklist in mind:
- Step 1 (runtime): Choose contiguous or linked storage — verifies state invariants before advancing the execution pointer.
- Step 2 (runtime): Locate the target position — verifies state invariants before advancing the execution pointer.
- Step 3 (runtime): Read the element — verifies state invariants before advancing the execution pointer.
- Step 4 (runtime): Note what an insert would move — verifies state invariants before advancing the execution pointer.
- Step 5 (runtime): Return with the cost counted — verifies state invariants before advancing the execution pointer.
Every transition across the runtime boundary carries both a direct CPU/memory cost (cache-line fills, descriptor lookups, lock acquisitions, or context switches) and a tail-latency queueing risk under contention. To verify this trace on your own service, capture latency histograms and hardware/kernel counters across each step boundary, compare cold-cache versus warm-cache execution paths, and confirm that error or timeout branches release all acquired descriptors, locks, and buffers cleanly.