Video lesson: Arrays and Linked Lists: Cost Follows Access Pattern

Lesson promise

By the end, the learner should be able to explain the core model for arrays and linked lists: cost follows access pattern, apply it to a concrete input, and identify when its usual shortcut or guarantee stops applying. This is a recording brief; publish it as a playable lesson after the narration and visual sequence have been produced and reviewed.

Narration draft

An array stores elements in contiguous indexed positions. This makes locating element i a direct address calculation and often keeps nearby values close in cache. A linked list stores each value alongside a reference to another node, which makes traversal follow pointers instead of predictable offsets.

Inserting into the middle of a packed array shifts later values, while inserting a node into a linked list can update a constant number of references once the insertion point is already known. Finding that point still requires traversal. Dynamic arrays balance capacity and memory use by occasionally allocating a larger block and copying elements.

Constant-time indexing does not imply constant-time insertion, and constant-time pointer rewiring does not imply constant-time list operations overall. Linked structures add allocation and pointer-chasing costs. Arrays may reserve unused capacity, but their locality often makes them faster for scans than a theoretically similar pointer-based structure.

Visual sequence

1. Put the input and assumptions on screen. Ask the learner to predict the next state before revealing it.
2. Animate the representation and show the operation one transition at a time.
3. Pause at the boundary case in the companion article and compare the result with the invariant.
4. End with the exercise prompt: Choose a representation for a queue with frequent append, front removal, and occasional iteration. State which operations dominate and what guarantees your implementation needs.

Companion material

Use the article, trace, and interactive concept flow as the learner’s written and visual references. The video remains planned until an actual playable media URL and reviewed transcript are available.