A 40-line Diff Algorithm Implementation for React's Virtual DOM

Any framework that relies on a virtual DOM must compare the before and after node trees, which requires a Diff algorithm. Although many articles describe the logic, the concepts are often quickly forgotten after reading.

Design Idea of the Diff Algorithm

We can categorize the situations a Diff algorithm needs to handle into three groups:

Node attribute changes (e.g., className, style).

Node insertion or deletion.

Node movement.

Based on these three cases, a common design is:

Determine which case the current node belongs to.

If it is an insertion or deletion, execute the corresponding logic.

If it is an attribute change, execute the attribute‑update logic.

If it is a movement, execute the move logic.

In practice, the priority of these operations is considered equal, but node movement occurs less frequently, so most frameworks (React, Vue) check the more common cases first and handle the rare cases later.

Demo Introduction

First we define the data structure of a virtual DOM node:

type Flag = 'Placement' | 'Deletion';

interface Node {
  key: string;
  flag?: Flag;
  index?: number;
}

key uniquely identifies a node, while flag indicates the operation that should be performed on the real DOM after the diff (placement for insertion/move, deletion for removal).

The index records the node’s position among its siblings.

Core Diff Function

The diff function receives the node list before and after the update and returns a new list where each node is marked with the appropriate flag:

type NodeList = Node[];

function diff(before: NodeList, after: NodeList): NodeList {
  // ...implementation
}

Example:

// before
const before = [{key: 'a'}];
// after
const after = [{key: 'd'}];
// diff(before, after) returns
[
  {key: "d", flag: "Placement"},
  {key: "a", flag: "Deletion"}
]

Here {key: "d", flag: "Placement"} means a new DOM node for d should be inserted, while {key: "a", flag: "Deletion"} means the DOM node for a should be removed.

Algorithm Steps

Preparation before traversal.

Traverse the after list.

Post‑traversal cleanup.

Preparation

We store each node from before in a Map keyed by node.key for O(1) lookup and record its original index:

const result: NodeList = [];
const beforeMap = new Map
();
before.forEach((node, i) => {
  node.index = i;
  beforeMap.set(node.key, node);
});

Traversing the After List

During the traversal, if a node exists in beforeMap it is reusable; otherwise it is a new node and receives a Placement flag. For reusable nodes we compare its original index with lastPlacedIndex (the index of the last node that did not need to move). If the original index is smaller, the node has moved to the right and we mark it with Placement . Otherwise we update lastPlacedIndex and keep the node in place.

let lastPlacedIndex = 0;
for (let i = 0; i < after.length; i++) {
  const afterNode = after[i];
  afterNode.index = i;
  const beforeNode = beforeMap.get(afterNode.key);

  if (beforeNode) {
    // reusable node
    beforeMap.delete(beforeNode.key);
    const oldIndex = beforeNode.index as number;
    if (oldIndex < lastPlacedIndex) {
      // move to the right
      afterNode.flag = 'Placement';
      result.push(afterNode);
      continue;
    } else {
      // stay in place
      lastPlacedIndex = oldIndex;
    }
  } else {
    // new node
    afterNode.flag = 'Placement';
    result.push(afterNode);
  }
}

Post‑Traversal Cleanup

After processing after , any nodes left in beforeMap could not be reused and must be deleted:

beforeMap.forEach(node => {
  node.flag = 'Deletion';
  result.push(node);
});

The final result array contains all nodes with their appropriate Placement or Deletion flags, ready for the real‑DOM update phase.

Conclusion

The most challenging part of the Diff algorithm is handling the lastPlacedIndex logic that decides whether a reusable node should be moved. By following the demo and stepping through the code, you can gain a solid understanding of how React’s reconciliation works under the hood.

Reference

Online demo: https://codesandbox.io/s/naughty-matan-6fq7n6?file=/src/diff.ts