Understanding Virtual DOM and Diff Algorithms in Frontend Frameworks

Virtual DOM

Virtual DOM is a JavaScript object that simulates the real DOM structure, allowing developers to work with an in‑memory representation of the UI. By updating this virtual tree and then diffing it against the previous version, only the necessary real DOM changes are applied, reducing costly re‑flows and repaints.

// 真实的dom结构
111
222
333

When the real DOM changes, a new virtual DOM tree is generated:

// 旧的虚拟dom结构
const oldVDom = {
  tagName: 'ul',
  props: { id: 'list' },
  children: [
    { tagName: 'li', props: { class: 'item1' }, children: ['111'] },
    { tagName: 'li', props: { class: 'item2' }, children: ['222'] },
    { tagName: 'li', props: { class: 'item3' }, children: ['333'] }
  ]
}

After modifying the real DOM (e.g., changing the third li text to "three‑three"), a new virtual DOM is created:

// 新的虚拟dom结构
const newVDom = {
  tagName: 'ul',
  props: { id: 'list' },
  children: [
    { tagName: 'li', props: { class: 'item1' }, children: ['111'] },
    { tagName: 'li', props: { class: 'item2' }, children: ['222'] },
    { tagName: 'li', props: { class: 'item3' }, children: ['three-three'] }
  ]
}

Why Use Virtual DOM?

Before virtual DOM, developers relied on direct DOM manipulation libraries like jQuery, which caused frequent re‑flows. A single render cycle batches all DOM updates, so even if dozens of changes occur, only one real DOM update is performed, dramatically improving performance.

Diff Algorithm

The diff algorithm compares the old and new virtual DOM trees to determine the minimal set of changes. It operates on a same‑layer basis to keep the time complexity at O(n) instead of O(n³) for naïve full‑tree comparisons.

<div>
    <p>ppp</p>
    <ul id='list'>
        <li class='item1'>111</li>
        <li class='item2'>222</li>
        <li class='item3'>333</li>
    </ul>
    <div>div</div>
</div>

Typical diff cases include:

Node type changes (e.g., p → h3 ) – the old node is destroyed and a new one is created.

Same node type but different attributes – only the attribute is updated.

Node addition or removal – new nodes are inserted or old nodes are deleted.

Text content changes – the text node is updated.

Vue2 Diff (Double‑Ended Comparison)

Vue2 uses a double‑ended pointer technique to compare the start and end of the old and new child lists, reusing nodes when possible and moving others as needed.

function patch(oldVnode, newVnode) { // 传入新、旧节点
  if (sameVnode(oldVnode, newVnode)) {
    patchVnode(oldVnode, newVnode)
  } else {
    const oldEl = oldVnode.el
    const parentEle = api.parentNode(oldEl)
    createEle(newVnode)
    if (parentEle !== null) {
      api.insertBefore(parentEle, newVnode.el, api.nextSibling(oldEl))
      api.removeChild(parentEle, oldVnode.el)
      oldVnode = null
    }
  }
  return newVnode
}

The core patchVnode function updates children, text, and attributes, delegating to updateChildren for the heavy‑lifting.

Vue3 Diff (LIS Optimization)

Vue3 improves the algorithm by first matching nodes from both ends, then building a source array that records the position of each new node in the old list. The longest increasing subsequence (LIS) of this array identifies nodes that can stay in place, while the rest are moved.

function vue3Diff(prevChildren, nextChildren, parent) {
  // ... build source array ...
  if (move) {
    const seq = lis(source) // longest increasing subsequence
    let j = seq.length - 1
    for (let i = nextLeft - 1; i >= 0; i--) {
      const cur = source[i]
      if (cur === -1) {
        // new node
        mount(nextNode, parent, refNode)
      } else if (cur === seq[j]) {
        // part of LIS – no move needed
        j--
      } else {
        // need to move
        parent.insertBefore(nextNode.el, refNode)
      }
    }
  } else {
    // simple mount/unmount when no moves are required
  }
}

The LIS step reduces the worst‑case complexity to O(n log n) while still handling pathological cases in O(n²).

Key Usage and Why Not Index

In Vue, the key attribute determines whether a node can be reused. Using a stable, unique key (often an ID) allows the diff algorithm to correctly match old and new nodes. Using the array index as a key causes keys to shift on insertions or deletions, forcing unnecessary re‑creation of components and hurting performance.

Conclusion

The article covered the fundamentals of virtual DOM, why it improves rendering performance, and how diff algorithms—both the double‑ended approach in Vue2 and the LIS‑based optimization in Vue3—efficiently compute minimal DOM updates. Proper key usage is essential for achieving these performance gains.