本文不讲解 vDom 实现，mount 挂载，以及 render 函数。只讨论三种 diff 算法。VNode 类型不考虑 component、functional-component、Fragment、Teleport。只考虑 Element 和 Text。此文章全部代码可参考该项目（https://github.com/sunyanzhe/virtual-dom）。

下面的 diff 算法中会出现几个方法，在这里进行罗列，并说明其功能

• mount(vnode, parent, [refNode]): 通过vnode生成真实的DOM节点。parent为其父级的真实 DOM 节点，refNode为真实的DOM节点，其父级节点为parent。如果refNode不为空，vnode生成的DOM节点就会插入到refNode之前；如果refNode为空，那么vnode生成的DOM节点就作为最后一个子节点插入到parent中

• patch(prevNode, nextNode, parent): 可以简单的理解为给当前DOM节点进行更新，并且调用diff算法对比自身的子节点;

一、React-Diff

React 的思路是递增法。通过对比新的列表中的节点，在原本的列表中的位置是否是递增，来判断当前节点是否需要移动。

1. 实现原理

来看这样一个例子。

nextList为新的列表，prevList为旧列表。这个例子我们一眼能看出来，新列表是不需要进行移动的。下面我用react的递增思想，解释一下为什么新列表中的节点不需要移动。

我们首先遍历nextList，并且找到每一个节点，在prevList中的位置。

function foo(prevList, nextList) {
    for (let i = 0; i < nextList.length; i++) {
        let nextItem = nextList[i];
        for (let j = 0; j < prevList.length; j++) {
            let prevItem = prevList[j]
            if (nextItem === prevItem) {

            }
        }
    }
}

找到位置以后，与上一个节点的位置进行对比，如果当前的位置大于上一个位置，说明当前节点不需要移动。因此我们要定义一个lastIndex来记录上一个节点的位置。

function foo(prevList, nextList) {
    let lastIndex = 0
    for (let i = 0; i < nextList.length; i++) {
        let nextItem = nextList[i];
        for (let j = 0; j < prevList.length; j++) {
            let prevItem = prevList[j]
            if (nextItem === prevItem) {
                if (j < lastIndex) {
                    // 需要移动节点
                } else {
                    // 不需要移动节点，记录当前位置，与之后的节点进行对比
                    lastIndex = j
                }
            }
        }
    }
}

在上面的例子中，nextList每个节点在prevList的位置为0 1 2 3。每一项都要比前一项要大，所以不需要移动，这就是react的diff算法的原理。

2. 找到需要移动的节点

在上一小节中，我们是通过对比值是否相等，查找的对应位置。但是在 vdom 中，每一个节点都是一个 vNode，我们应该如何进行判断呢？

答案就是key，我们通过对每个节点的key进行赋值，并且让处于同一children数组下的vnode的key都不相同，以此来确定每个节点的唯一性，并进行新旧列表的对比。

function reactDiff(prevChildren, nextChildren, parent) {
    let lastIndex = 0
    for (let i = 0; i < nextChildren.length; i++) {
        let nextChild = nextChildren[i];
        for (let j = 0; j < prevChildren.length; j++) {
            let prevChild = prevChildren[j]
            if (nextChild.key === prevChild.key) {
                patch(prevChild, nextChild, parent)
                if (j < lastIndex) {
                    // 需要移动节点
                } else {
                    // 不需要移动节点，记录当前位置，与之后的节点进行对比
                    lastIndex = j
                }
            }
        }
    }
}

3. 移动节点

首先我们先明确一点，移动节点所指的节点是DOM节点。vnode.el指向该节点对应的真实DOM节点。patch方法会将更新过后的DOM节点，赋值给新的vnode的el属性。

为了画图方便，我们用key的值来表示vnode节点。为了行文方便，我们把key值为a的vnode简写为vnode-a，vnode-a对应的真实 DOM 节点为DOM-A

我们来将上图的例子代入reactDiff中执行。我们遍历新列表，并查找vnode在旧列表中的位置。当遍历到vnode-d时，之前遍历在旧列表的位置为0 < 2 < 3，说明A C D这三个节点都是不需要移动的。此时lastIndex = 3, 并进入下一次循环，发现vnode-b在旧列表的index为1，1 < 3，说明DOM-B要移动。

通过观察我们能发现，只需要把DOM-B移动到DOM-D之后就可以了。也就是找到需要移动的 VNode，我们称该 VNode 为 α，将 α 对应的真实的 DOM 节点移动到，α 在新列表中的前一个 VNode 对应的真实 DOM 的后面。

在上述的例子中，就是将vnode-b对应的真实 DOM 节点DOM-B, 移动到vnode-b在新列表中的前一个VNode——vnode-d对应的真实 DOM 节点DOM-D的后面。

function reactDiff(prevChildren, nextChildren, parent) {
    let lastIndex = 0
    for (let i = 0; i < nextChildren.length; i++) {
        let nextChild = nextChildren[i];
        for (let j = 0; j < prevChildren.length; j++) {
            let prevChild = prevChildren[j]
            if (nextChild.key === prevChild.key) {
                patch(prevChild, nextChild, parent)
                if (j < lastIndex) {
                    // 移动到前一个节点的后面
                    let refNode = nextChildren[i - 1].el.nextSibling;
                    parent.insertBefore(nextChild.el, refNode)
                } else {
                    // 不需要移动节点，记录当前位置，与之后的节点进行对比
                    lastIndex = j
                }
            }
        }
    }
}

为什么是这样移动的呢？首先我们列表是从头到尾遍历的。这就意味着对于当前VNode节点来说，该节点之前的所有节点都是排好序的，如果该节点需要移动，那么只需要将 DOM 节点移动到前一个vnode节点之后就可以，因为在新列表中vnode的顺序就是这样的。

4. 添加节点

上一小节我们只讲了如何移动节点，但是忽略了另外一种情况，就是在新列表中有全新的VNode节点，在旧列表中找不到。遇到这种情况，我们需要根据新的VNode节点生成DOM节点，并插入DOM树中。

至此，我们面临两个问题：1.如何发现全新的节点、2. 生成的DOM节点插入到哪里

我们先来解决第一个问题，找节点还是比较简单的，我们定义一个find变量值为false。如果在旧列表找到了key
相同的vnode，就将find的值改为true。当遍历结束后判断find值，如果为false，说明当前节点为新节点。

function reactDiff(prevChildren, nextChildren, parent) {
  let lastIndex = 0
  for (let i = 0; i < nextChildren.length; i++) {
    let nextChild = nextChildren[i],
      find = false
    for (let j = 0; j < prevChildren.length; j++) {
      let prevChild = prevChildren[j]
      if (nextChild.key === prevChild.key) {
        find = true
        patch(prevChild, nextChild, parent)
        if (j < lastIndex) {
          // 移动到前一个节点的后面
          let refNode = nextChildren[i - 1].el.nextSibling
          parent.insertBefore(nextChild.el, refNode)
        } else {
          // 不需要移动节点，记录当前位置，与之后的节点进行对比
          lastIndex = j
        }
        break
      }
    }
    if (!find) {
      // 插入新节点
    }
  }
}

找到新节点后，下一步就是插入到哪里了，这里的逻辑其实是和移动节点的逻辑是一样的。我们观察上图可以发现，新的vnode-c是紧跟在vnode-b后面的，并且vnode-b的 DOM 节点——DOM-B是已经排好序的，所以我们只需要将vnode-c生成的 DOM 节点插入到DOM-B之后就可以了。

但是这里有一种特殊情况需要注意，就是新的节点位于新列表的第一个，这时候我们需要找到旧列表第一个节点，将新节点插入到原来第一个节点之前就可以了。

function reactDiff(prevChildren, nextChildren, parent) {
  let lastIndex = 0
  for (let i = 0; i < nextChildren.length; i++) {
    let nextChild = nextChildren[i],
      find = false
    for (let j = 0; j < prevChildren.length; j++) {
      let prevChild = prevChildren[j]
      if (nextChild.key === prevChild.key) {
        find = true
        patch(prevChild, nextChild, parent)
        if (j < lastIndex) {
          // 移动到前一个节点的后面
          let refNode = nextChildren[i - 1].el.nextSibling
          parent.insertBefore(nextChild.el, refNode)
        } else {
          // 不需要移动节点，记录当前位置，与之后的节点进行对比
          lastIndex = j
        }
        break
      }
    }
    if (!find) {
      // 插入新节点
      let refNode = i <= 0 ? prevChildren[0].el : nextChildren[i - 1].el.nextSibling
      mount(nextChild, parent, refNode)
    }
  }
}

5. 移除节点

有增就有减，当旧的节点不在新列表中时，我们就将其对应的 DOM 节点移除。

function reactDiff(prevChildren, nextChildren, parent) {
  let lastIndex = 0
  for (let i = 0; i < nextChildren.length; i++) {
    let nextChild = nextChildren[i],
      find = false
    for (let j = 0; j < prevChildren.length; j++) {
      let prevChild = prevChildren[j]
      if (nextChild.key === prevChild.key) {
        find = true
        patch(prevChild, nextChild, parent)
        if (j < lastIndex) {
          // 移动到前一个节点的后面
          let refNode = nextChildren[i - 1].el.nextSibling
          parent.insertBefore(nextChild.el, refNode)
        } else {
          // 不需要移动节点，记录当前位置，与之后的节点进行对比
          lastIndex = j
        }
        break
      }
    }
    if (!find) {
      // 插入新节点
      let refNode = i <= 0 ? prevChildren[0].el : nextChildren[i - 1].el.nextSibling
      mount(nextChild, parent, refNode)
    }
  }
  for (let i = 0; i < prevChildren.length; i++) {
    let prevChild = prevChildren[i],
      key = prevChild.key,
      has = nextChildren.find((item) => item.key === key)
    if (!has) parent.removeChild(prevChild.el)
  }
}

以上就是 React 的 diff 算法的思路。

目前的reactDiff的时间复杂度为O(m*n)，我们可以用空间换时间，把key与index的关系维护成一个Map，从而将时间复杂度降低为O(n)，具体的代码可以查看此项目。

我们接下来看这样一个例子

根据reactDiff的思路，我们需要先将DOM-A移动到DOM-C之后，然后再将DOM-B移动到DOM-A之后，完成Diff。但是我们通过观察可以发现，只要将DOM-C移动到DOM-A之前就可以完成Diff。

这里是有可优化的空间的，接下来我们介绍vue2.x中的diff算法——双端比较，该算法解决了上述的问题。

二、Vue2.X Diff —— 双端比较

所谓双端比较就是新列表和旧列表两个列表的头与尾互相对比，，在对比的过程中指针会逐渐向内靠拢，直到某一个列表的节点全部遍历过，对比停止。

1. 实现原理

我们先用四个指针指向两个列表的头尾

function vue2Diff(prevChildren, nextChildren, parent) {
  let oldStartIndex = 0,
    oldEndIndex = prevChildren.length - 1
  ;(newStartIndex = 0), (newEndIndex = nextChildren.length - 1)
  let oldStartNode = prevChildren[oldStartIndex],
    oldEndNode = prevChildren[oldEndIndex],
    newStartNode = nextChildren[nextStartIndex],
    newEndNode = nextChildren[nextEndIndex]
}

我们根据四个指针找到四个节点，然后进行对比，那么如何对比呢？我们按照以下四个步骤进行对比

1. 使用旧列表的头一个节点oldStartNode与新列表的头一个节点newStartNode对比

2. 使用旧列表的最后一个节点oldEndNode与新列表的最后一个节点newEndNode对比

3. 使用旧列表的头一个节点oldStartNode与新列表的最后一个节点newEndNode对比

4. 使用旧列表的最后一个节点oldEndNode与新列表的头一个节点newStartNode对比

使用以上四步进行对比，去寻找key相同的可复用的节点，当在某一步中找到了则停止后面的寻找。具体对比顺序如下图

对比顺序代码结构如下:

function vue2Diff(prevChildren, nextChildren, parent) {
  let oldStartIndex = 0,
    oldEndIndex = prevChildren.length - 1
  ;(newStartIndex = 0), (newEndIndex = nextChildren.length - 1)
  let oldStartNode = prevChildren[oldStartIndex],
    oldEndNode = prevChildren[oldEndIndex],
    newStartNode = nextChildren[newStartIndex],
    newEndNode = nextChildren[newEndIndex]

  if (oldStartNode.key === newStartNode.key) {
  } else if (oldEndNode.key === newEndNode.key) {
  } else if (oldStartNode.key === newEndNode.key) {
  } else if (oldEndNode.key === newStartNode.key) {
  }
}

当对比时找到了可复用的节点，我们还是先patch给元素打补丁，然后将指针进行前/后移一位指针。根据对比节点的不同，我们移动的指针和方向也不同，具体规则如下：

1. 当旧列表的头一个节点oldStartNode与新列表的头一个节点newStartNode对比时key相同。那么旧列表的头指针oldStartIndex与新列表的头指针newStartIndex同时向后移动一位。

2. 当旧列表的最后一个节点oldEndNode与新列表的最后一个节点newEndNode对比时key相同。那么旧列表的尾指针oldEndIndex与新列表的尾指针newEndIndex同时向前移动一位。

3. 当旧列表的头一个节点oldStartNode与新列表的最后一个节点newEndNode对比时key相同。那么旧列表的头指针oldStartIndex向后移动一位；新列表的尾指针newEndIndex向前移动一位。

4. 当旧列表的最后一个节点oldEndNode与新列表的头一个节点newStartNode对比时key相同。那么旧列表的尾指针oldEndIndex向前移动一位；新列表的头指针newStartIndex向后移动一位。

function vue2Diff(prevChildren, nextChildren, parent) {
  let oldStartIndex = 0,
    oldEndIndex = prevChildren.length - 1,
    newStartIndex = 0,
    newEndIndex = nextChildren.length - 1
  let oldStartNode = prevChildren[oldStartIndex],
    oldEndNode = prevChildren[oldEndIndex],
    newStartNode = nextChildren[newStartIndex],
    newEndNode = nextChildren[newEndIndex]

  if (oldStartNode.key === newStartNode.key) {
    patch(oldvStartNode, newStartNode, parent)

    oldStartIndex++
    newStartIndex++
    oldStartNode = prevChildren[oldStartIndex]
    newStartNode = nextChildren[newStartIndex]
  } else if (oldEndNode.key === newEndNode.key) {
    patch(oldEndNode, newEndNode, parent)

    oldEndIndex--
    newEndIndex--
    oldEndNode = prevChildren[oldEndIndex]
    newEndNode = nextChildren[newEndIndex]
  } else if (oldStartNode.key === newEndNode.key) {
    patch(oldStartNode, newEndNode, parent)

    oldStartIndex++
    newEndIndex--
    oldStartNode = prevChildren[oldStartIndex]
    newEndNode = nextChildren[newEndIndex]
  } else if (oldEndNode.key === newStartNode.key) {
    patch(oldEndNode, newStartNode, parent)

    oldEndIndex--
    nextStartIndex++
    oldEndNode = prevChildren[oldEndIndex]
    newStartNode = nextChildren[newStartIndex]
  }
}

在小节的开头，提到了要让指针向内靠拢，所以我们需要循环。循环停止的条件是当其中一个列表的节点全部遍历完成，代码如下

function vue2Diff(prevChildren, nextChildren, parent) {
  let oldStartIndex = 0,
    oldEndIndex = prevChildren.length - 1,
    newStartIndex = 0,
    newEndIndex = nextChildren.length - 1
  let oldStartNode = prevChildren[oldStartIndex],
    oldEndNode = prevChildren[oldEndIndex],
    newStartNode = nextChildren[newStartIndex],
    newEndNode = nextChildren[newEndIndex]
  while (oldStartIndex <= oldEndIndex && newStartIndex <= newEndIndex) {
    if (oldStartNode.key === newStartNode.key) {
      patch(oldStartNode, newStartNode, parent)

      oldStartIndex++
      newStartIndex++
      oldStartNode = prevChildren[oldStartIndex]
      newStartNode = nextChildren[newStartIndex]
    } else if (oldEndNode.key === newEndNode.key) {
      patch(oldEndNode, newEndNode, parent)

      oldEndIndex--
      newndIndex--
      oldEndNode = prevChildren[oldEndIndex]
      newEndNode = nextChildren[newEndIndex]
    } else if (oldStartNode.key === newEndNode.key) {
      patch(oldvStartNode, newEndNode, parent)

      oldStartIndex++
      newEndIndex--
      oldStartNode = prevChildren[oldStartIndex]
      newEndNode = nextChildren[newEndIndex]
    } else if (oldEndNode.key === newStartNode.key) {
      patch(oldEndNode, newStartNode, parent)

      oldEndIndex--
      newStartIndex++
      oldEndNode = prevChildren[oldEndIndex]
      newStartNode = nextChildren[newStartIndex]
    }
  }
}

至此整体的循环我们就全部完成了，下面我们需要考虑这样两个问题：

• 什么情况下DOM节点需要移动

• DOM节点如何移动

我们来解决第一个问题：什么情况下需要移动，我们还是以上图为例。

当我们在第一个循环时，在第四步发现旧列表的尾节点oldEndNode与新列表的头节点newStartNode的key相同，是可复用的DOM节点。通过观察我们可以发现，原本在旧列表末尾的节点，却是新列表中的开头节点，没有人比他更靠前，因为他是第一个，所以我们只需要把当前的节点移动到原本旧列表中的第一个节点之前，让它成为第一个节点即可。

function vue2Diff(prevChildren, nextChildren, parent) {
  // ...
  while (oldStartIndex <= oldEndIndex && newStartIndex <= newEndIndex) {
    if (oldStartNode.key === newStartNode.key) {
      // ...
    } else if (oldEndNode.key === newEndNode.key) {
      // ...
    } else if (oldStartNode.key === newEndNode.key) {
      // ...
    } else if (oldEndNode.key === newStartNode.key) {
      patch(oldEndNode, newStartNode, parent)
      // 移动到旧列表头节点之前
      parent.insertBefore(oldEndNode.el, oldStartNode.el)

      oldEndIndex--
      newStartIndex++
      oldEndNode = prevChildren[oldEndIndex]
      newStartNode = nextChildren[newStartIndex]
    }
  }
}

然后我们进入第二次循环，我们在第二步发现，旧列表的尾节点oldEndNode和新列表的尾节点newEndNode为复用节点。原本在旧列表中就是尾节点，在新列表中也是尾节点，说明该节点不需要移动，所以我们什么都不需要做。

同理，如果是旧列表的头节点oldStartNode和新列表的头节点newStartNode为复用节点，我们也什么都不需要做。

进入第三次循环，我们在第三部发现，旧列表的头节点oldStartNode和新列表的尾节点newEndNode为复用节点。到这一步聪明如你肯定就一眼可以看出来了，我们只要将DOM-A移动到DOM-B后面就可以了。

依照惯例我们还是解释一下，原本旧列表中是头节点，然后在新列表中是尾节点。那么只要在旧列表中把当前的节点移动到原本尾节点的后面，就可以了。

function vue2Diff(prevChildren, nextChildren, parent) {
  // ...
  while (oldStartIndex <= oldEndIndex && newStartIndex <= newEndIndex) {
    if (oldStartNode.key === newStartNode.key) {
      // ...
    } else if (oldEndNode.key === newEndNode.key) {
      // ...
    } else if (oldStartNode.key === newEndNode.key) {
      patch(oldStartNode, newEndNode, parent)
      parent.insertBefore(oldStartNode.el, oldEndNode.el.nextSibling)

      oldStartIndex++
      newEndIndex--
      oldStartNode = prevChildren[oldStartIndex]
      newEndNode = nextChildren[newEndIndex]
    } else if (oldEndNode.key === newStartNode.key) {
      //...
    }
  }
}

OK，进入最后一个循环。在第一步旧列表头节点oldStartNode与新列表头节点newStartNode位置相同，所以啥也不用做。然后结束循环，这就是Vue2 双端比较的原理。

2. 非理想情况

上一小节，我们讲了双端比较的原理，但是有一种特殊情况，当四次对比都没找到复用节点时，我们只能拿新列表的第一个节点去旧列表中找与其key相同的节点。

function vue2Diff(prevChildren, nextChildren, parent) {
  //...
  while (oldStartIndex <= oldEndIndex && newStartIndex <= newEndIndex) {
    if (oldStartNode.key === newStartNode.key) {
      //...
    } else if (oldEndNode.key === newEndNode.key) {
      //...
    } else if (oldStartNode.key === newEndNode.key) {
      //...
    } else if (oldEndNode.key === newStartNode.key) {
      //...
    } else {
      // 在旧列表中找到 和新列表头节点key 相同的节点
      let newKey = newStartNode.key,
        oldIndex = prevChildren.findIndex((child) => child.key === newKey)
    }
  }
}

找节点的时候其实会有两种情况：一种在旧列表中找到了，另一种情况是没找到。我们先以上图为例，说一下找到的情况。

当我们在旧列表中找到对应的VNode，我们只需要将找到的节点的DOM元素，移动到开头就可以了。这里的逻辑其实和第四步的逻辑是一样的，只不过第四步是移动的尾节点，这里是移动找到的节点。DOM移动后，由我们将旧列表中的节点改为undefined，这是至关重要的一步，因为我们已经做了节点的移动了所以我们不需要进行再次的对比了。最后我们将头指针newStartIndex向后移一位。

function vue2Diff(prevChildren, nextChildren, parent) {
  //...
  while (oldStartIndex <= oldEndIndex && newStartIndex <= newEndIndex) {
    if (oldStartNode.key === newStartNode.key) {
      //...
    } else if (oldEndNode.key === newEndNode.key) {
      //...
    } else if (oldStartNode.key === newEndNode.key) {
      //...
    } else if (oldEndNode.key === newStartNode.key) {
      //...
    } else {
      // 在旧列表中找到 和新列表头节点key 相同的节点
      let newtKey = newStartNode.key,
        oldIndex = prevChildren.findIndex((child) => child.key === newKey)

      if (oldIndex > -1) {
        let oldNode = prevChildren[oldIndex]
        patch(oldNode, newStartNode, parent)
        parent.insertBefore(oldNode.el, oldStartNode.el)
        prevChildren[oldIndex] = undefined
      }
      newStartNode = nextChildren[++newStartIndex]
    }
  }
}

如果在旧列表中没有找到复用节点呢？很简单，直接创建一个新的节点放到最前面就可以了，然后后移头指针newStartIndex。

function vue2Diff(prevChildren, nextChildren, parent) {
  //...
  while (oldStartIndex <= oldEndIndex && newStartIndex <= newEndIndex) {
    if (oldStartNode.key === newStartNode.key) {
      //...
    } else if (oldEndNode.key === newEndNode.key) {
      //...
    } else if (oldStartNode.key === newEndNode.key) {
      //...
    } else if (oldEndNode.key === newStartNode.key) {
      //...
    } else {
      // 在旧列表中找到 和新列表头节点key 相同的节点
      let newtKey = newStartNode.key,
        oldIndex = prevChildren.findIndex((child) => child.key === newKey)

      if (oldIndex > -1) {
        let oldNode = prevChildren[oldIndex]
        patch(oldNode, newStartNode, parent)
        parent.insertBefore(oldNode.el, oldStartNode.el)
        prevChildren[oldIndex] = undefined
      } else {
        mount(newStartNode, parent, oldStartNode.el)
      }
      newStartNode = nextChildren[++newStartIndex]
    }
  }
}

最后当旧列表遍历到undefind时就跳过当前节点。

function vue2Diff(prevChildren, nextChildren, parent) {
  //...
  while (oldStartIndex <= oldEndIndex && newStartIndex <= newEndIndex) {
    if (oldStartNode === undefind) {
      oldStartNode = prevChildren[++oldStartIndex]
    } else if (oldEndNode === undefind) {
      oldEndNode = prevChildren[--oldEndIndex]
    } else if (oldStartNode.key === newStartNode.key) {
      //...
    } else if (oldEndNode.key === newEndNode.key) {
      //...
    } else if (oldStartNode.key === newEndNode.key) {
      //...
    } else if (oldEndNode.key === newStartNode.key) {
      //...
    } else {
      // ...
    }
  }
}

3.添加节点

我们先来看一个例子

这个例子非常简单，几次循环都是尾节点相同，尾指针一直向前移动，直到循环结束，如下图：

此时oldEndIndex以及小于了oldStartIndex，但是新列表中还有剩余的节点，我们只需要将剩余的节点依次插入到oldStartNode的DOM之前就可以了。为什么是插入oldStartNode之前呢？原因是剩余的节点在新列表的位置是位于oldStartNode之前的，如果剩余节点是在oldStartNode之后，oldStartNode就会先行对比，这个需要思考一下，其实还是与第四步的思路一样。

function vue2Diff(prevChildren, nextChildren, parent) {
  //...
  while (oldStartIndex <= oldEndIndex && newStartIndex <= newEndIndex) {
    // ...
  }
  if (oldEndIndex < oldStartIndex) {
    for (let i = newStartIndex; i <= newEndIndex; i++) {
      mount(nextChildren[i], parent, prevStartNode.el)
    }
  }
}

4.移除节点

与上一小节的情况相反，当新列表的newEndIndex小于newStartIndex时，我们将旧列表剩余的节点删除即可。这里我们需要注意，旧列表的undefind。在第二小节中我们提到过，当头尾节点都不相同时，我们会去旧列表中找新列表的第一个节点，移动完 DOM 节点后，将旧列表的那个节点改为undefind。所以我们在最后的删除时，需要注意这些undefind，遇到的话跳过当前循环即可。

function vue2Diff(prevChildren, nextChildren, parent) {
  //...
  while (oldStartIndex <= oldEndIndex && newStartIndex <= newEndIndex) {
    // ...
  }
  if (oldEndIndex < oldStartIndex) {
    for (let i = newStartIndex; i <= newEndIndex; i++) {
      mount(nextChildren[i], parent, prevStartNode.el)
    }
  } else if (newEndIndex < newStartIndex) {
    for (let i = oldStartIndex; i <= oldEndIndex; i++) {
      if (prevChildren[i]) {
        partent.removeChild(prevChildren[i].el)
      }
    }
  }
}

5.小结

至此双端比较全部完成，以下是全部代码。

function vue2diff(prevChildren, nextChildren, parent) {
  let oldStartIndex = 0,
    newStartIndex = 0,
    oldStartIndex = prevChildren.length - 1,
    newStartIndex = nextChildren.length - 1,
    oldStartNode = prevChildren[oldStartIndex],
    oldEndNode = prevChildren[oldStartIndex],
    newStartNode = nextChildren[newStartIndex],
    newEndNode = nextChildren[newStartIndex]
  while (oldStartIndex <= oldStartIndex && newStartIndex <= newStartIndex) {
    if (oldStartNode === undefined) {
      oldStartNode = prevChildren[++oldStartIndex]
    } else if (oldEndNode === undefined) {
      oldEndNode = prevChildren[--oldStartIndex]
    } else if (oldStartNode.key === newStartNode.key) {
      patch(oldStartNode, newStartNode, parent)

      oldStartIndex++
      newStartIndex++
      oldStartNode = prevChildren[oldStartIndex]
      newStartNode = nextChildren[newStartIndex]
    } else if (oldEndNode.key === newEndNode.key) {
      patch(oldEndNode, newEndNode, parent)

      oldStartIndex--
      newStartIndex--
      oldEndNode = prevChildren[oldStartIndex]
      newEndNode = nextChildren[newStartIndex]
    } else if (oldStartNode.key === newEndNode.key) {
      patch(oldStartNode, newEndNode, parent)
      parent.insertBefore(oldStartNode.el, oldEndNode.el.nextSibling)
      oldStartIndex++
      newStartIndex--
      oldStartNode = prevChildren[oldStartIndex]
      newEndNode = nextChildren[newStartIndex]
    } else if (oldEndNode.key === newStartNode.key) {
      patch(oldEndNode, newStartNode, parent)
      parent.insertBefore(oldEndNode.el, oldStartNode.el)
      oldStartIndex--
      newStartIndex++
      oldEndNode = prevChildren[oldStartIndex]
      newStartNode = nextChildren[newStartIndex]
    } else {
      let newKey = newStartNode.key,
        oldIndex = prevChildren.findIndex((child) => child && child.key === newKey)
      if (oldIndex === -1) {
        mount(newStartNode, parent, oldStartNode.el)
      } else {
        let prevNode = prevChildren[oldIndex]
        patch(prevNode, newStartNode, parent)
        parent.insertBefore(prevNode.el, oldStartNode.el)
        prevChildren[oldIndex] = undefined
      }
      newStartIndex++
      newStartNode = nextChildren[newStartIndex]
    }
  }
  if (newStartIndex > newStartIndex) {
    while (oldStartIndex <= oldStartIndex) {
      if (!prevChildren[oldStartIndex]) {
        oldStartIndex++
        continue
      }
      parent.removeChild(prevChildren[oldStartIndex++].el)
    }
  } else if (oldStartIndex > oldStartIndex) {
    while (newStartIndex <= newStartIndex) {
      mount(nextChildren[newStartIndex++], parent, oldStartNode.el)
    }
  }
}

三、 Vue3 Diff —— 最长递增子序列

vue3的diff借鉴于inferno，该算法其中有两个理念。第一个是相同的前置与后置元素的预处理；第二个则是最长递增子序列，此思想与React的diff类似又不尽相同。下面我们来一一介绍。

1. 前置与后置的预处理

我们看这两段文字

Hello World

Hey World

其实就简单的看一眼我们就能发现，这两段文字是有一部分是相同的，这些文字是不需要修改也不需要移动的，真正需要进行修改中间的几个字母，所以diff就变成以下部分：

text1: 'llo'
text2: 'y'

接下来换成vnode，我们以下图为例。

图中的被绿色框起来的节点，他们是不需要移动的，只需要进行打补丁patch就可以了。我们把该逻辑写成代码。

function vue3Diff(prevChildren, nextChildren, parent) {
  let j = 0,
    prevEnd = prevChildren.length - 1,
    nextEnd = nextChildren.length - 1,
    prevNode = prevChildren[j],
    nextNode = nextChildren[j]
  while (prevNode.key === nextNode.key) {
    patch(prevNode, nextNode, parent)
    j++
    prevNode = prevChildren[j]
    nextNode = nextChildren[j]
  }

  prevNode = prevChildren[prevEnd]
  nextNode = prevChildren[nextEnd]

  while (prevNode.key === nextNode.key) {
    patch(prevNode, nextNode, parent)
    prevEnd--
    nextEnd--
    prevNode = prevChildren[prevEnd]
    nextNode = prevChildren[nextEnd]
  }
}

这时候，我们就需要考虑边界情况了，这里有两种情况。一种是j > prevEnd；另一种是j > nextEnd。

我们以这张图为例，此时j > prevEnd且j <= nextEnd，我们只需要把新列表中j到nextEnd之间剩下的节点插入进去就可以了。相反， 如果j > nextEnd时，我们把旧列表中j到prevEnd之间的节点删除就可以了。

function vue3Diff(prevChildren, nextChildren, parent) {
  // ...
  if (j > prevEnd && j <= nextEnd) {
    let nextpos = nextEnd + 1,
      refNode = nextpos >= nextChildren.length ? null : nextChildren[nextpos].el
    while (j <= nextEnd) mount(nextChildren[j++], parent, refNode)
  } else if (j > nextEnd && j <= prevEnd) {
    while (j <= prevEnd) parent.removeChild(prevChildren[j++].el)
  }
}

我们再继续思考，在我们while循环时，指针是从两端向内逐渐靠拢的，所以我们应该在循环中就应该去判断边界情况，我们使用label语法，当我们触发边界情况时，退出全部的循环，直接进入判断。代码如下：

function vue3Diff(prevChildren, nextChildren, parent) {
  let j = 0,
    prevEnd = prevChildren.length - 1,
    nextEnd = nextChildren.length - 1,
    prevNode = prevChildren[j],
    nextNode = nextChildren[j]
  // label语法
  outer: {
    while (prevNode.key === nextNode.key) {
      patch(prevNode, nextNode, parent)
      j++
      // 循环中如果触发边界情况，直接break，执行outer之后的判断
      if (j > prevEnd || j > nextEnd) break outer
      prevNode = prevChildren[j]
      nextNode = nextChildren[j]
    }

    prevNode = prevChildren[prevEnd]
    nextNode = prevChildren[nextEnd]

    while (prevNode.key === nextNode.key) {
      patch(prevNode, nextNode, parent)
      prevEnd--
      nextEnd--
      // 循环中如果触发边界情况，直接break，执行outer之后的判断
      if (j > prevEnd || j > nextEnd) break outer
      prevNode = prevChildren[prevEnd]
      nextNode = prevChildren[nextEnd]
    }
  }

  // 边界情况的判断
  if (j > prevEnd && j <= nextEnd) {
    let nextpos = nextEnd + 1,
      refNode = nextpos >= nextChildren.length ? null : nextChildren[nextpos].el
    while (j <= nextEnd) mount(nextChildren[j++], parent, refNode)
  } else if (j > nextEnd && j <= prevEnd) {
    while (j <= prevEnd) parent.removeChild(prevChildren[j++].el)
  }
}

2. 判断是否需要移动

其实几个算法看下来，套路已经很明显了，就是找到移动的节点，然后给他移动到正确的位置。把该加的新节点添加好，把该删的旧节点删了，整个算法就结束了。这个算法也不例外，我们接下来看一下它是如何做的。

当前/后置的预处理结束后，我们进入真正的diff环节。首先，我们先根据新列表剩余的节点数量，创建一个source数组，并将数组填满-1。

我们先写这块逻辑。

function vue3Diff(prevChildren, nextChildren, parent) {
  //...
  outer: {
    // ...
  }

  // 边界情况的判断
  if (j > prevEnd && j <= nextEnd) {
    // ...
  } else if (j > nextEnd && j <= prevEnd) {
    // ...
  } else {
    let prevStart = j,
      nextStart = j,
      nextLeft = nextEnd - nextStart + 1, // 新列表中剩余的节点长度
      source = new Array(nextLeft).fill(-1) // 创建数组，填满-1
  }
}

那么这个source数组，是要做什么的呢？他就是来做新旧节点的对应关系的，我们将新节点在旧列表的位置存储在该数组中，我们在根据source计算出它的最长递增子序列用于移动 DOM 节点。为此，我们先建立一个对象存储当前新列表中的节点与index的关系，再去旧列表中去找位置。

在找节点时要注意，如果旧节点在新列表中没有的话，直接删除就好。除此之外，我们还需要一个数量表示记录我们已经patch过的节点，如果数量已经与新列表剩余的节点数量一样，那么剩下的旧节点我们就直接删除了就可以了。

function vue3Diff(prevChildren, nextChildren, parent) {
  //...
  outer: {
    // ...
  }

  // 边界情况的判断
  if (j > prevEnd && j <= nextEnd) {
    // ...
  } else if (j > nextEnd && j <= prevEnd) {
    // ...
  } else {
    let prevStart = j,
      nextStart = j,
      nextLeft = nextEnd - nextStart + 1, // 新列表中剩余的节点长度
      source = new Array(nextLeft).fill(-1), // 创建数组，填满-1
      nextIndexMap = {}, // 新列表节点与index的映射
      patched = 0 // 已更新过的节点的数量

    // 保存映射关系
    for (let i = nextStart; i <= nextEnd; i++) {
      let key = nextChildren[i].key
      nextIndexMap[key] = i
    }

    // 去旧列表找位置
    for (let i = prevStart; i <= prevEnd; i++) {
      let prevNode = prevChildren[i],
        prevKey = prevNode.key,
        nextIndex = nextIndexMap[prevKey]
      // 新列表中没有该节点 或者 已经更新了全部的新节点，直接删除旧节点
      if (nextIndex === undefind || patched >= nextLeft) {
        parent.removeChild(prevNode.el)
        continue
      }
      // 找到对应的节点
      let nextNode = nextChildren[nextIndex]
      patch(prevNode, nextNode, parent)
      // 给source赋值
      source[nextIndex - nextStart] = i
      patched++
    }
  }
}

找到位置后，我们观察这个重新赋值后的source，我们可以看出，如果是全新的节点的话，其在source数组中对应的值就是初始的-1，通过这一步我们可以区分出来哪个为全新的节点，哪个是可复用的。

其次，我们要判断是否需要移动。那么如何判断移动呢？很简单，和React一样我们用递增法，如果我们找到的index是一直递增的，说明不需要移动任何节点。我们通过设置一个变量来保存是否需要移动的状态。

function vue3Diff(prevChildren, nextChildren, parent) {
  //...
  outer: {
    // ...
  }

  // 边界情况的判断
  if (j > prevEnd && j <= nextEnd) {
    // ...
  } else if (j > nextEnd && j <= prevEnd) {
    // ...
  } else {
    let prevStart = j,
      nextStart = j,
      nextLeft = nextEnd - nextStart + 1, // 新列表中剩余的节点长度
      source = new Array(nextLeft).fill(-1), // 创建数组，填满-1
      nextIndexMap = {}, // 新列表节点与index的映射
      patched = 0,
      move = false, // 是否移动
      lastIndex = 0 // 记录上一次的位置

    // 保存映射关系
    for (let i = nextStart; i <= nextEnd; i++) {
      let key = nextChildren[i].key
      nextIndexMap[key] = i
    }

    // 去旧列表找位置
    for (let i = prevStart; i <= prevEnd; i++) {
      let prevNode = prevChildren[i],
        prevKey = prevNode.key,
        nextIndex = nextIndexMap[prevKey]
      // 新列表中没有该节点 或者 已经更新了全部的新节点，直接删除旧节点
      if (nextIndex === undefind || patched >= nextLeft) {
        parent.removeChild(prevNode.el)
        continue
      }
      // 找到对应的节点
      let nextNode = nextChildren[nextIndex]
      patch(prevNode, nextNode, parent)
      // 给source赋值
      source[nextIndex - nextStart] = i
      patched++

      // 递增方法，判断是否需要移动
      if (nextIndex < lastIndex) {
        move = false
      } else {
        lastIndex = nextIndex
      }
    }

    if (move) {
      // 需要移动
    } else {
      //不需要移动
    }
  }
}

3. DOM 如何移动

判断完是否需要移动后，我们就需要考虑如何移动了。一旦需要进行 DOM 移动，我们首先要做的就是找到source的最长递增子序列。

function vue3Diff(prevChildren, nextChildren, parent) {
  //...
  if (move) {
    const seq = lis(source) // [0, 1]
    // 需要移动
  } else {
    //不需要移动
  }
}

什么是最长递增子序列：给定一个数值序列，找到它的一个子序列，并且子序列中的值是递增的，子序列中的元素在原序列中不一定连续。

例如给定数值序列为：[ 0, 8, 4, 12 ]。

那么它的最长递增子序列就是：[0, 8, 12]。

当然答案可能有多种情况，例如：[0, 4, 12] 也是可以的。

我们在下一节单独讲解最长递增子序列

上面的代码中，我们调用lis 函数求出数组source的最长递增子序列为[ 0, 1 ]。我们知道 source 数组的值为 [2, 3, 1, -1]，很显然最长递增子序列应该是[ 2, 3 ]，但为什么计算出的结果是[ 0, 1 ]呢？其实[ 0, 1 ]代表的是最长递增子序列中的各个元素在source数组中的位置索引，如下图所示：

我们根据source，对新列表进行重新编号，并找出了最长递增子序列。

我们从后向前进行遍历source每一项。此时会出现三种情况：

1. 当前的值为-1，这说明该节点是全新的节点，又由于我们是从后向前遍历，我们直接创建好 DOM 节点插入到队尾就可以了。

2. 当前的索引为最长递增子序列中的值，也就是i === seq[j]，这说说明该节点不需要移动

3. 当前的索引不是最长递增子序列中的值，那么说明该 DOM 节点需要移动，这里也很好理解，我们也是直接将 DOM 节点插入到队尾就可以了，因为队尾是排好序的。

function vue3Diff(prevChildren, nextChildren, parent) {
  //...
  if (move) {
   // 需要移动
	const seq = lis(source); // [0, 1]
    let j = seq.length - 1;  // 最长子序列的指针
    // 从后向前遍历
    for (let i = nextLeft - 1；i >= 0; i--) {
      let pos = nextStart + i, // 对应新列表的index
        nextNode = nextChildren[pos],	// 找到vnode
      	nextPos = pos + 1，    // 下一个节点的位置，用于移动DOM
        refNode = nextPos >= nextChildren.length ? null : nextChildren[nextPos].el, //DOM节点
        cur = source[i];  // 当前source的值，用来判断节点是否需要移动

      if (cur === -1) {
        // 情况1，该节点是全新节点
      	mount(nextNode, parent, refNode)
      } else if (cur === seq[j]) {
        // 情况2，是递增子序列，该节点不需要移动
        // 让j指向下一个
        j--
      } else {
        // 情况3，不是递增子序列，该节点需要移动
        parent.insetBefore(nextNode.el, refNode)
      }
    }

  } else {
  //不需要移动

  }
}

说完了需要移动的情况，再说说不需要移动的情况。如果不需要移动的话，我们只需要判断是否有全新的节点给他添加进去就可以了。具体代码如下：

function vue3Diff(prevChildren, nextChildren, parent) {
  //...
  if (move) {
	const seq = lis(source); // [0, 1]
    let j = seq.length - 1;  // 最长子序列的指针
    // 从后向前遍历
    for (let i = nextLeft - 1；i >= 0; i--) {
      let pos = nextStart + i, // 对应新列表的index
        nextNode = nextChildren[pos],	// 找到vnode
      	nextPos = pos + 1，    // 下一个节点的位置，用于移动DOM
        refNode = nextPos >= nextChildren.length ? null : nextChildren[nextPos].el, //DOM节点
        cur = source[i];  // 当前source的值，用来判断节点是否需要移动

      if (cur === -1) {
        // 情况1，该节点是全新节点
      	mount(nextNode, parent, refNode)
      } else if (cur === seq[j]) {
        // 情况2，是递增子序列，该节点不需要移动
        // 让j指向下一个
        j--
      } else {
        // 情况3，不是递增子序列，该节点需要移动
        parent.insetBefore(nextNode.el, refNode)
      }
    }
  } else {
    //不需要移动
    for (let i = nextLeft - 1；i >= 0; i--) {
      let cur = source[i];  // 当前source的值，用来判断节点是否需要移动

      if (cur === -1) {
       let pos = nextStart + i, // 对应新列表的index
          nextNode = nextChildren[pos],	// 找到vnode
          nextPos = pos + 1，    // 下一个节点的位置，用于移动DOM
          refNode = nextPos >= nextChildren.length ? null : nextChildren[nextPos].el, //DOM节点
      	mount(nextNode, parent, refNode)
      }
    }
  }
}

至此vue3.0的 diff 完成。

4. 最长递增子序列

leetcode 有原题，官方解析很清晰，看不懂我讲的可以去看看官方解析。

我们以该数组为例

;[10, 9, 2, 5, 3, 8, 7, 13]

我们可以使用动态规划的思想考虑这个问题。动态规划的思想是将一个大的问题分解成多个小的子问题，并尝试得到这些子问题的最优解，子问题的最优解有可能会在更大的问题中被利用，这样通过小问题的最优解最终求得大问题的最优解。

我们先假设只有一个值的数组[13]，那么该数组的最长递增子序列就是[13]自己本身，其长度为1。那么我们认为每一项的递增序列的长度值均为 1

那么我们这次给数组增加一个值[7, 13], 由于7 < 13，所以该数组的最长递增子序列是[7, 13]，那么该长度为2。那么我们是否可以认为，当[7]小于[13]时，以[7]为头的递增序列的长度是，[7]的长度和[13]的长度的和，即1 + 1 = 2。

ok，我们基于这种思想来给计算一下该数组。我们先将每个值的初始赋值为1

首先 7 < 13 那么7对应的长度就是13的长度再加 1，1 + 1 = 2

继续，我们对比8。我们首先和7比，发现不满足递增，但是没关系我们还可以继续和13比，8 < 13满足递增，那么8的长度也是13的长度在加一，长度为2

我们再对比3，我们先让其与8进行对比，3 < 8，那么3的长度是8的长度加一，此时3的长度为3。但是还没结束，我们还需要让3与7对比。同样3 < 7，此时我们需要在计算出一个长度是7的长度加一同样是3，我们对比两个长度，如果原本的长度没有本次计算出的长度值大的话，我们进行替换，反之则我们保留原本的值。由于3 === 3，我们选择不替换。最后，我们让3与13进行对比，同样的3 < 13，此时计算出的长度为2，比原本的长度3要小，我们选择保留原本的值。

之后的计算依次类推，最后的结果是这样的

我们从中取最大的值4，该值代表的最长递增子序列的个数。代码如下：

function lis(arr) {
  let len = arr.length,
    dp = new Array(len).fill(1) // 用于保存长度
  for (let i = len - 1; i >= 0; i--) {
    let cur = arr[i]
    for (let j = i + 1; j < len; j++) {
      let next = arr[j]
      // 如果是递增 取更大的长度值
      if (cur < next) dp[i] = Math.max(dp[j] + 1, dp[i])
    }
  }
  return Math.max(...dp)
}

至此为止，我们讲完了基础的最长递增子序列。然而在vue3.0中，我们需要的是最长递增子序列在原本数组中的索引。所以我们还需要在创建一个数组用于保存每个值的最长子序列所对应在数组中的index。具体代码如下：

function lis(arr) {
  let len = arr.length,
    res = [],
    dp = new Array(len).fill(1)
  // 存默认index
  for (let i = 0; i < len; i++) {
    res.push([i])
  }
  for (let i = len - 1; i >= 0; i--) {
    let cur = arr[i],
      nextIndex = undefined
    // 如果为-1 直接跳过，因为-1代表的是新节点，不需要进行排序
    if (cur === -1) continue
    for (let j = i + 1; j < len; j++) {
      let next = arr[j]
      // 满足递增条件
      if (cur < next) {
        let max = dp[j] + 1
        // 当前长度是否比原本的长度要大
        if (max > dp[i]) {
          dp[i] = max
          nextIndex = j
        }
      }
    }
    // 记录满足条件的值，对应在数组中的index
    if (nextIndex !== undefined) res[i].push(...res[nextIndex])
  }
  let index = dp.reduce((prev, cur, i, arr) => (cur > arr[prev] ? i : prev), dp.length - 1)
  // 返回最长的递增子序列的index
  return result[index]
}