怎么移动？我们使用key来将新旧vnode做一次映射。

首先我们找到可以复用的vnode，可以做两次遍历，外层遍历next vnode，内层遍历prev vnode

如果next vnode和prev vnode只是位置移动，vnodedata和children没有任何变动，调用patchVnode之后不会有任何dom操作。
接下来只需要把这个key相同的vnode移动到正确的位置即可。我们的问题变成了怎么移动。

首先需要知道两个事情:

• 每一个prev vnode都引用了一个真实dom节点，每个next vnode这个时候都没有真实dom节点。
• 调用patchVnode的时候会把prevVnode引用的真实Dom的引用赋值给nextVnode，就像这样：

还是拿上面的例子，外层遍历next vnode,遍历第一个元素的时候， 第一个vnode是li©，然后去prev vnode里找，在最后一个节点找到了，这里外层是第一个元素，不做任何移动的操作，我们记录一下这个vnode在prevVnode中的索引位置lastIndex，接下来在遍历的时候，如果j<lastIndex，说明原本prevVnode在前面的元素，在nextVnode中变到了后面来了，那么我们就把prevVnode[j]放到nextVnode[i-1]的后面。

这里多说一句，dom操作的api里，只有insertBefore()，没有insertAfter()。也就是说只有把某个dom插入到某个元素前面这个方法，没有插入到某个元素后面这个方法，所以我们只能用insertBefore()。那么思路就变成了，当j<lastIndex的时候，把prevChildren[j]插入到nextVnode[i-1]的真实dom的后面元素的前面。

当j>=lastIndex的时候，说明这个顺序是正确的的，不用移动，然后把lastIndex = j;
也就是说，只把prevVnode中后面的元素往前移动，原本顺序是正确的就不变。
现在我们的diff的代码变成了这样：

同样的问题，如果新旧vnode的元素数量一样，那就已经可以工作了。接下来要做的就是新增节点和删除节点。

首先是新增节点，整个框架中将vnode挂载到真实dom上都调用patch函数，patch里调用createElm来生成真实dom。按照上面的实现，如果nextVnode中有一个节点是prevVnode中没有的，就有问题：

在prevVnode中找不到li(d)，那我们需要调用createElm挂在这个新的节点，因为这里的节点需要超入到li(b)和li©之间，所以需要用insertBefore()。在每次遍历nextVnode的时候用一个变量find=false表示是否能够在prevVnode中找到节点，如果找到了就find=true。如果内层遍历后find是false，那说明这是一个新的节点。

我们的createElm函数需要判断一下第四个参数，如果没有就是用appendChild直接把元素放到父节点的最后，如果有第四个参数，则需要调用insertBefore来插入到正确的位置。

接下来要做的是删除prevVnode多余节点：

在nextVnode中已经没有li(d)了，我们需要在执行完上面所讲的所有流程后在遍历一次prevVnode，然后拿到nextVnode里去找，如果找不到相同key的节点，那就说明这个节点已经被删除了，我们直接用removeChild方法删除Dom。

完整的代码：https://github.com/TingYinHelen/tempo/blob/main/src/platforms/web/patch.js在react-diff分支(目前有可能代码仓库还没有开源，等我实现更完善的时候会开源出来，项目结构可能有变化，看tempo仓库就行)

这里我的代码实现的diff算法很明显看出来时间复杂度是O(n2)。那么这里在算法上依然又可以优化的空间，这里我把nextChildren和prevChildren都设计成了数组的类型，这里可以把nextChildren、prevChildren设计成对象类型，用户传入的key作为对象的key，把vnode作为对象的value，这样就可以只循环nextChildren，然后通过prevChildren[key]的方式找到prevChidren中可复用的dom。这样就可以把时间复杂度降到O(n)。

以上就是react的diff算法的实现。

vue的diff算法

先说一下上面代码的问题，举个例子，下面这个情况：

如果按照react的方法，整个过程会移动2次：
li©是第一个节点，不需要移动，lastIndex=2
li(b), j=1, j<lastIndex, 移动到li©后面 (第1次移动)
li(a), j=0, j<lastIndex, 移动到li(b)后面 (第2次移动)

但是通过肉眼来看，其实只用把li©移动到第一个就行，只需要移动1一次。
于是vue2这么来设计的：

首先找到四个节点vnode：prev的第一个，next的第一个，prev的最后一个，next的最后一个，然后分别把这四个节点作比对：1. 把prev的第一个节点和next的第一个比对；2. 把prev的最后一个和next的最后一个比对；3.prev的第一个和next的最后一个；4. next的第一个和prev的最后一个。如果找到相同key的vnode，就做移动，移动后把前面的指针往后移动，后面的指针往前移动，直到前后的指针重合，如果key不相同就只patch更新vnodedata和children。下面来走一下流程：

1. li(a)和li(b)，key不同，只patch，不移动
2. li(d)和li©，key不同，只patch，不移动
3. li(a)和li©，key不同，只patch，不移动
4. li(d)和li(d)，key相同，先patch，需要移动移动，移动的方法就是把prev的li(d)移动到li(a)的前面。然后移动指针，因为prev的最后一个做了移动，所以把prev的指向后面的指针往前移动一个，因为next的第一个vnode已经找到了对应的dom，所以next的前面的指针往后移动一个。

现在比对的图变成了下面这样：

这个时候的真实DOM：

继续比对

1. li(a)和li(b)，key不同，只patch，不移动。
2. li©和li©，相同相同，先patch，因为next的最后一个元素也刚好是prev的最后一个，所以不移动，prev和next都往前移动指针。

这个时候真实DOM：

现在最新的比对图：

继续比对

1. li(a)和li(b)，key不同，只patch，不移动。
2. li(b)和li(a)，key不同，只patch，不移动。
3. li(a) 和li (a)，key相同，patch，把prev的li(a)移动到next的后面指针的元素的后面。

真实的DOM变成了这样：

比对的图变成这样：

继续比对：
li(b)和li(b)的key相同，patch，都是前指针相同所以不移动，移动指针
这个时候前指针就在后指针后面了，这个比对就结束了。

这就完成了常规的比对，还有不常规的，如下图：

经过1，2，3，4次比对后发现，没有相同的key值能够移动。

这种情况我们没有办法，只有用老办法，用newStartIndex的key拿去依次到prev里的vnode，直到找到相同key值的老的vnode，先patch，然后获取真实dom移动到正确的位置(放到oldStartIndex前面)，然后在prevChildren中把移动过后的vnode设置为undefined，在下次指针移动到这里的时候直接跳过，并且next的start指针向右移动。

function updateChildren (elm, prevChildren, nextChildren) {
  let oldStartIndex = 0;
  let oldEndIndex = prevChildren.length - 1;
  let newStartIndex = 0;
  let newEndIndex = nextChildren.length - 1;

  while (oldStartIndex <= oldEndIndex && newStartIndex <= newEndIndex) {
    let oldStartVnode = prevChildren[oldStartIndex];
    let oldEndVnode = prevChildren[oldEndIndex];
    let newStartVnode = nextChildren[newStartIndex];
    let newEndVnode = nextChildren[newEndIndex];

    if (oldStartVnode === undefined) {
      oldStartVnode = prevChildren[++oldStartIndex];
    }
    if (oldEndVnode === undefined) {
      oldEndVnode = prevChildren[--oldEndIndex];
    }

    if (oldStartVnode.key === newStartVnode.key) {
      patchVnode(newStartVnode, oldStartVnode);
      oldStartIndex++;
      newStartIndex++;
    } else if (oldEndVnode.key === newEndVnode.key) {
      patchVnode(newEndVnode, oldEndVnode);
      oldEndIndex--;
      newEndIndex--;
    } else if (oldStartVnode.key === newEndVnode.key) {
      patchVnode(newEndVnode, oldStartVnode);
      elm.insertBefore(oldStartVnode.elm, oldEndVnode.elm.nextSibling);
      newEndIndex--;
      oldStartIndex++;
    } else if (oldEndVnode.key === newStartVnode.key) {
      patchVnode(newStartVnode, oldEndVnode);
      elm.insertBefore(oldEndVnode.elm, oldStartVnode.elm);
      oldEndIndex--;
      newStartIndex++;
    } else {
      const idxInOld = prevChildren.findIndex(child => child.key === newStartVnode.key);
      if (idxInOld >= 0) {
        elm.insertBefore(prevChildren[idxInOld].elm, oldStartVnode.elm);
        prevChildren[idxInOld] = undefined;
        newStartIndex++;
      }
    }
  }
}

接下来就是新增节点：

这种排列方法，按照上面的方法，经过1，2，3，4比对后找不到相同key，然后然后用newStartIndex到老的vnode中去找，仍然找不着，这个时候说明是一个新节点，把它插入到oldStartIndex前面

最后是删除节点，我把他作为课后作业，同学可以自己实现最后的删除的算法。
完整代码在 https://github.com/TingYinHelen/ tempo的vue分支。
PS.本文部分内容参考自《比对一下react,vue2.x,vue3.x的diff算法》。