Detailed Explanation of React Virtual DOM and Diff Algorithm

1. Problem Description
Virtual DOM (Virtual DOM) is one of the core features of React. It simulates the real DOM structure using JavaScript objects. When data changes, React first compares the differences in the virtual DOM and then updates the real DOM with minimal changes. Interviews often examine its design motivation, working principles, and especially the optimization strategies of the Diff algorithm.

2. The Role and Design Motivation of Virtual DOM

1. Background Issues:

   • Direct manipulation of the real DOM is costly (reflow, repaint).
   • Frequent DOM updates when data changes traditionally lead to performance bottlenecks.

2. Advantages of Virtual DOM:

   • Consolidate multiple DOM operations into one batch update.
   • Precisely locate changed parts through the Diff algorithm to avoid full updates.

3. Virtual DOM Creation and Comparison Process

1. Virtual DOM Structure:

   • Use JS objects to describe DOM nodes, including tag names, attributes, child nodes, etc.
   • Example:

     const vNode = {
       type: 'div',
       props: { className: 'header' },
       children: [
         { type: 'span', children: 'Hello' }
       ]
     };
     

2. Core Logic of Diff Algorithm:

   • Same-level Comparison: Only compare nodes at the same level, avoiding cross-level comparisons (reducing time complexity from O(n³) to O(n)).
   • Node Type Judgment:
     • Different types (e.g., div changes to p): Directly destroy the old node and its subtree, and create a new node.
     • Same type: Update attributes (e.g., className) and recursively compare child nodes.
   • Key Optimization for List Nodes:
     • Use key to identify node identity, avoiding misdeletion/reconstruction caused by direct index-based comparison.
     • Example: Inserting D into list [A, B, C] (after A). Without key, B and C are mistakenly considered changed; with key, only D is inserted.

4. Specific Steps of the Diff Algorithm

1. Depth-First Traversal:

   • Start from the root node and recursively compare the old and new virtual DOM trees.

2. Attribute Update Strategy:

   • Merge old and new attributes, add or modify attributes (e.g., style), and delete old attributes.

3. Child Node Comparison (Core):

   • Traverse the old and new child node lists using double pointers:
     • Compare new front with old front (reuse node if types match).
     • Compare new back with old back (reuse if types match).
     • Compare new back with old front (move node to the end if types match).
     • Compare new front with old back (move node to the front if types match).
   • If none match, check if any old nodes can be reused (via key mapping).

5. Updating Virtual DOM to Real DOM

1. Generate Patches:

   • The Diff result generates specific DOM operation commands (e.g., ADD_NODE, REMOVE_NODE).

2. Batch Updates:

   • Apply patches to the real DOM to avoid triggering multiple renders for intermediate states.

6. Example Illustration
Assume the old and new virtual DOMs are as follows:

// Old
{ type: 'ul', children: [
  { type: 'li', key: 'a', children: 'A' },
  { type: 'li', key: 'b', children: 'B' }
]}

// New
{ type: 'ul', children: [
  { type: 'li', key: 'c', children: 'C' }, // New
  { type: 'li', key: 'a', children: 'A' }, // Moved
  { type: 'li', key: 'b', children: 'B' }  // Moved
]}

Diff process:

1. Detect new node with key='c', not found in the old list, create a new node.
2. Nodes with key='a' and key='b' exist, move them after c.
3. Ultimately, only one node is inserted and the order is adjusted, avoiding reconstruction of all nodes.

7. Summary
Virtual DOM optimizes DOM operations through JS computation. The Diff algorithm reduces performance overhead through strategies like same-level comparison and Key identification. This mechanism significantly improves rendering efficiency in complex UI scenarios. However, for simple pages, additional JS computation may slow things down, so it's necessary to evaluate based on the actual scenario.