Child Reconciliation Algorithm

The list-diffing algorithm React runs when a component returns several children, read from reconcileChildrenArray, updateSlot, mapRemainingChildren and placeChild in the React 19.2.5 build (react-dom-client.development.js), whose source is ReactChildFiber.js. Part of React Internals. The rules it implements (type and key) are explained in Reconciliation. My own notes and clarifications are marked with > 💬.

Interview Q&A

The problem: pairing old children with new ones

A fiber’s children are a singly linked list: parent.child is the first, then .sibling to the next. The component has just returned a new array of elements. React must decide, for each new element:

• reuse an old fiber (same key and same type) → update props, keep state
• create a new fiber → insert
• mark a reused fiber as moved → move in the DOM

It must also decide which old fibers have no match → delete.

Doing this with nested loops is O(n²), and optimal moves need more bookkeeping. React does it in O(n) with a Map, accepting some extra moves in rare cases.

The algorithm

Simplified from reconcileChildrenArray(returnFiber, currentFirstChild, newChildren, lanes):

function reconcileChildrenArray(returnFiber, currentFirstChild, newChildren) {
	let resultingFirstChild = null
	let previousNewFiber = null
	let oldFiber = currentFirstChild
	let lastPlacedIndex = 0
	let newIdx = 0
	let nextOldFiber = null

	// PASS 1: walk both lists in lockstep while keys line up
	for (; oldFiber !== null && newIdx < newChildren.length; newIdx++) {
		nextOldFiber = oldFiber.sibling
		// updateSlot returns null if the KEYS differ;
		// if keys match but TYPES differ it returns a brand-new fiber
		const newFiber = updateSlot(returnFiber, oldFiber, newChildren[newIdx])
		if (newFiber === null) break                    // keys diverged → leave the fast path
		if (oldFiber && newFiber.alternate === null) {
			deleteChild(returnFiber, oldFiber)          // same key, different type → replace
		}
		lastPlacedIndex = placeChild(newFiber, lastPlacedIndex, newIdx)
		link(newFiber)
		oldFiber = nextOldFiber
	}

	// PASS 2a: the new list ended → everything left in the old list goes
	if (newIdx === newChildren.length) {
		deleteRemainingChildren(returnFiber, oldFiber)
		return resultingFirstChild
	}

	// PASS 2b: the old list ended → everything left in the new list is an insert
	if (oldFiber === null) {
		for (; newIdx < newChildren.length; newIdx++) {
			const newFiber = createChild(returnFiber, newChildren[newIdx])
			lastPlacedIndex = placeChild(newFiber, lastPlacedIndex, newIdx)
			link(newFiber)
		}
		return resultingFirstChild
	}

	// PASS 3: keys diverged in the middle → match by key through a Map
	const existingChildren = mapRemainingChildren(oldFiber)  // key ?? index → fiber
	for (; newIdx < newChildren.length; newIdx++) {
		const newFiber = updateFromMap(existingChildren, returnFiber, newIdx, newChildren[newIdx])
		if (newFiber !== null) {
			if (newFiber.alternate !== null) {
				existingChildren.delete(newFiber.key === null ? newIdx : newFiber.key)  // consumed
			}
			lastPlacedIndex = placeChild(newFiber, lastPlacedIndex, newIdx)
			link(newFiber)
		}
	}
	existingChildren.forEach((child) => deleteChild(returnFiber, child))  // leftovers
	return resultingFirstChild
}

The move decision, from the actual source (flag constants named):

function placeChild(newFiber, lastPlacedIndex, newIndex) {
	newFiber.index = newIndex
	const current = newFiber.alternate
	if (current !== null) {
		const oldIndex = current.index
		if (oldIndex < lastPlacedIndex) {
			newFiber.flags |= Placement   // this is a MOVE
			return lastPlacedIndex
		} else {
			return oldIndex               // this item can STAY where it is
		}
	} else {
		newFiber.flags |= Placement       // this is an INSERTION
		return lastPlacedIndex
	}
}

And the map, verbatim apart from formatting:

function mapRemainingChildren(currentFirstChild) {
	for (var existingChildren = new Map(); null !== currentFirstChild; )
		null !== currentFirstChild.key
			? existingChildren.set(currentFirstChild.key, currentFirstChild)
			: existingChildren.set(currentFirstChild.index, currentFirstChild),
			(currentFirstChild = currentFirstChild.sibling)
	return existingChildren
}

Unkeyed children are stored under their index. That’s the whole reason “no key” behaves exactly like key={index}.

Why it works: the lastPlacedIndex idea

Think of the old list as positions 0…n−1. Walking the new list left to right, React keeps the largest old index it has decided to keep in place. As long as each reused child’s old index is increasing, those children are already in the right relative order and none of them has to move. The first child whose old index is smaller than lastPlacedIndex was before something that is now before it, so it moves.

A move is implemented as a DOM insert. In the commit, a fiber with Placement is inserted with insertBefore its next sibling that is not itself being placed (getHostSibling), or appended if there is none. Inserting an already-attached node moves it.

The React source comments on the tradeoff: this algorithm “can’t optimize by searching from both ends since we don’t have backpointers on fibers.” A fiber has sibling but no previousSibling, so React never walks the list backwards.

Child reconciliation, step by step

Notation: letters are keys, and the number in parentheses is the old index. lp = lastPlacedIndex after that child.

Append: [a, b, c] → [a, b, c, d]

1 DOM operation. The fast path handles it.

Remove from the middle: [a, b, c] → [a, c]

1 DOM operation.

Prepend: [a, b, c] → [x, a, b, c]

1 DOM operation. With index keys the same change becomes: key 0 matches old key 0 (the a fiber) → updated to show x, key 1 → shows a, key 2 → shows b, and key 3 is inserted to show c. That’s 3 updates and 1 insert, and all local state is shifted by one row.

Move first to last: [a, b, c, d] → [b, c, d, a]

1 move.

Move last to first: [a, b, c, d] → [d, a, b, c]

3 moves, although moving d alone would do. This is the known worst case: because React commits to “stay” greedily from the left, bringing an item from the end to the front moves everything else.

In practice this rarely matters. Moves are cheap next to rendering, and the fibers (and their state) are all reused either way. It matters for things that are sensitive to DOM moves: an <iframe> or <video> that restarts when moved, CSS transitions, or focus. If you have a list where items often jump to the top, the moved items are the ones that lose iframe/video state.

How other frameworks differ

Vue 3 (and Inferno before it) also trims the matching prefix, but it trims the matching suffix too, because its virtual nodes live in arrays that can be indexed from both ends. For the middle it computes the longest increasing subsequence of old indices, which is exactly the largest set of nodes that can stay, and moves only the rest. That’s optimal in moves at O(n log n). React’s greedy lastPlacedIndex is a cheap approximation of the same idea: it keeps an increasing subsequence, just not necessarily the longest one.

Rules and caveats

• Give dynamic lists stable, unique keys from the data (id), never Math.random() (every item remounts every render) and not the index unless the list never reorders or inserts.
• Keys only need to be unique among siblings. They’re compared within one parent’s children.
• Same key and different type is not a match. The old fiber is deleted and a new one created.
• Duplicate keys trigger a dev warning (warnOnInvalidKey). The second one behaves unpredictably because the Map holds only one fiber per key.
• Fragments and nested arrays are separate lists. [<A/>, [<B/>, <C/>]] reconciles the inner array as its own child with its own index.

Sources

• React 19.2.5 source: react-dom-client.development.js (reconcileChildrenArray, updateSlot, updateElement, mapRemainingChildren, placeChild, useFiber)
• React source: ReactChildFiber.js (unminified, with comments)
• Legacy React docs: Reconciliation, Keys

Primary source: github.com/facebook/react/blob/main/packages/react-reconciler/src/ReactChildFiber.js