Linked Lists and Nodes That Point
Storing a sequence as nodes that each hold a value and a reference to the next node. Inserting in the middle costs two pointer changes, but reaching the five hundredth item means walking there one node at a time.
What a learner can do afterwards
- Draw the pointer changes needed to insert and to delete a node in the middle
- Compare the cost of insertion and of access for a linked list and for an array
- Say what a null next reference marks and what happens if it is lost
1 · Read
A linked list stores a sequence as nodes, and each node holds a value plus a next reference pointing at the node after it, like paper clips hooked in a chain. An array reaches its five hundredth item by arithmetic on the index, but a list has no index to compute with. Reaching the fifth node means starting at the first and following next references one by one. The final node points at null, which marks the end of the chain.
Picture a linked list holding 1 through 7 in order. To insert a new node between 3 and 4 you change exactly two pointers: the new node points at 4, then node 3 swings its next reference onto the newcomer. To delete node 4 you make one change the other way: node 3 skips over it and points straight at 5. An array insertion would shift every later item along, so pointer surgery is the list answer to shifting.
Costs cut opposite ways. List insertion is two pointer changes but access walks node by node, while array access jumps by index but insertion shifts everything after it. So this arrangement makes insertion cheap and access expensive. If a next reference is lost before its time, every node past the break is stranded with no way to reach it.
Draw four nodes, insert a value after the second node, and guard each pointer before you swing it. Set the newcomer pointing first, then swing the predecessor across. Never drop the only reference to the rest of the chain, or the tail floats away unreachable.
Two pointer changes to insert, one walk per access.
2 · Watch
Take it off screen
Where it sits
8 questions wait behind this lesson, each with its answer explained. Every answer feeds the sky: stars light as they are learned, and dim when it is time to come back.