Keyed List Diffing

Position-based diffing breaks the moment a list changes order. After this lesson your program does what React does for a keyed list: it reads the old and new key lists and prints which nodes stay, which move, which are created and which are destroyed.

Why position is the wrong identity

Take three rows, each with a text input the user has typed into, and delete the first row. A positional diff compares new row 0 with old row 0 and rewrites its label, then row 1 with row 1, and finally removes the last DOM node. Every surviving DOM node now carries the typed text of a different row. The data was right and the screen is wrong, and a flicker, a lost focus or a restarted animation comes with it.

A key fixes this by saying which old child a new child is. It must be:

• stable: the same item has the same key on every render, so use a database id, not a counter you reassign.
• unique among siblings, and only among siblings.
• not the index when the list can reorder or change length. An index is position, which brings the bug back. A random key is worse: every render produces new identities and every row remounts.

A key is not an attribute. It never reaches the DOM and the component never receives it.

The algorithm

React's list reconciliation is a single pass over the new list, with one marker.

1. Record the position of every old key.
2. Walk the new list in order, keeping lastPlaced, the largest old position of any child kept in place so far. It starts at 0.
3. For each new key:
   • not in the old list: INSERT a new node;
   • in the old list at position j with j less than lastPlaced: an already-placed node sits after this one in the old order, so this node has to move: MOVE. lastPlaced does not change;
   • otherwise KEEP, and lastPlaced becomes j.
4. Every old key that no longer appears is destroyed: REMOVE.

A MOVE reuses the existing node, so its state survives. It is never a REMOVE plus an INSERT.

Worked trace for old x,y,z and new z,x,w,y:

Nothing was removed, so the output ends there. Notice what happened: z stayed and everything that used to be before it had to move. Compare two cases with four items p,q,r,s. Moving the first item to the end (new q,r,s,p) is one KEEP after another and a single MOVE of p. Moving the last item to the front (new s,p,q,r) keeps s and then moves all three others. That asymmetry is a known property of the single-pass algorithm, and Vue 3 removes it: it finds the longest increasing subsequence of the old positions, leaves exactly those nodes in place and moves the rest, which gives one move for s,p,q,r. Solid and Svelte avoid the problem by not diffing lists at all.

Printing order

Print the operations for the new list in order, one per key, and then one REMOVE per vanished key in the order they appeared in the old list.

Common mistakes

• Raising lastPlaced on a MOVE. Only a KEEP moves the marker; otherwise later siblings are wrongly kept or moved.
• Reporting a reorder as REMOVE and INSERT, which destroys the state a key exists to preserve.
• Comparing keys as numbers. 10 and 9 are strings; only equality matters.
• Printing REMOVE lines before the new list is walked, or in new-list order.
• Using the index as a key in your own components. This exercise cannot catch that, but your users will.

Your exercise

The starter reads the two lists and prints your operations, or NO CHANGES when there are none. You write keyed_diff. Keys are unique within a list.