双端diff

采用头尾2头对比的diff过程，vue2的dom diff算法
简单的diff算法，使用了双层for循环，在计算数据量大的情况下，无法应用到项目中。该算法还存在很多缺陷。

10.1双端比较的原理

简单的diff算法问题在于，它对DOM的移动操作不是最优的。

上面节点变动，按照简单diff算法需要移动2次DOM，是不是还可以继续优化，只需要移动一次呢。其实可以只需要把真实DOM节点p-3移动到真实DOM节点p-1前面即可。

可以看到只需一次移动操作就可完成更新，但是简单的diff算法还做不到。接下来实现双端diff算法的原理。

双端diff算法是一种同时对新旧两组子节点的2个端点进行比较的算法。 需要4个索引值，分别指向新旧2组子节点的端点。

用代码来表示4个端点

function patchChildren(n1, n2, container){
  if(typeof n2.children === "string"){
   //...
  }else if(Array.isArray(n2.children)){
    // 封装patchKeyedChildren函数 处理两组子节点
    patchKeyedChildren(n1, n2, children)
  }else{
   //...
  }
}
function patchKeyedChildren(n1, n2, children){
  const oldChildren = n1.children;
  const newChildren =n2.children;
  // 4个索引
  let oldStartIndex = 0;
  let oldEndIndex = oldChildren.length -1;
  let newStartIndex = 0;
  let newEndIndex = newChildren.length -1;
  // 4个索引指向的vnode节点
  let oldStartVnode = oldChildren[oldStartIndex];
  let oldEndVnode = oldChildren[oldEndIndex];
  let newStartVnode = newChildren[newStartIndex];
  let newEndVnode = newChildren[newEndIndex];
}

• oldStartVnode和oldEndVnode是旧的一组子节点的第一个节点和最后一个节点
• newStartVnode和newEndVnode是新的一组子节点的第一个节点和最后一个节点

双端比较中，每一轮都分为4个步骤进行比较。头头、尾尾、头尾、尾头

• 比较旧节点的第一个子节点p-1与新的一组子节点中的第一个子节点p-4，看他们是否相同，由于key不同，因此不可复用。什么都不做，继续下面的操作
• 比较旧节点的最后一个子节点p-4与新的一组子节点的最后一个子节点p-2，两者key不同，不可复用，继续后边操作。
• 比较旧节点的第一个子节点p-1与新的一组子节点中最后一个子节点p-2，两个key不同，不可复用。
• 比较旧节点的最后一个子节点p-4与新的一组子节点的第一个节点p-4，key相同，可以进行DOM复用

可以看到在四步比较过程中，第四步是比较旧的一组子节点的最后一个子节点和新的一组子节点的第一个子节点，发现他们相同。说明节点p-4原本是最后一个子节点，但在新顺序中，它变成了第一个子节点。对应的程序逻辑：将索引oldEndIndex指向的虚拟节点所对应的真实DOM移动到索引oldStartIndex指向的虚拟节点所对应的真实DOM前面。

function patchKeyedChildren(n1, n2, children){
  const oldChildren = n1.children;
  const newChildren =n2.children;
  // 4个索引
  let oldStartIndex = 0;
  let oldEndIndex = oldChildren.length -1;
  let newStartIndex = 0;
  let newEndIndex = newChildren.length -1;
  // 4个索引指向的vnode节点
  let oldStartVnode = oldChildren[oldStartIndex];
  let oldEndVnode = oldChildren[oldEndIndex];
  let newStartVnode = newChildren[newStartIndex];
  let newEndVnode = newChildren[newEndIndex];
  if(oldStartVnode.key === newStartVnode.key){ // 头头
    // 第一步：oldStartVnode 和 newStartVnode比较
  }else if(oldEndVnode.key === newEndVnode.key){ // 尾尾
    // 第二步：oldEndVnode 和 newEndVnode
  }else if(oldStartVnode.key === newEndVnode.key){ //头尾
    // 第三步：oldStartVnode 和 newEndVnode
  }else if(oldEndVnode.key === newStartVnode.key){ // 尾头
    // 第四步：oldEndVnode 和 newStartVnode
    //使用patch函数进行打补丁
    patch(oldEndVnode, newStartVnode, container);
    // 移动DOM操作
    // oldEndVnode.el 移动到 oldStartVnode.el前面
    insert(oldEndVnode.el, container, oldStartVnode.el)
    // 移动DOM完成后，更新索引值，并指向下一个位置
    oldEndVnode = oldChildren[--oldEndIndex];
    newStartVnode = newChildren[++newStartIndex];
  }
}

代码中增加了一系列if…else if…判断用来实现四个索引指向的虚拟节点之间的比较。就拿第四步的比较来说，原来处于尾部的节点，在新的顺序中应该处于头部。于是以头部元素oldStartVnode.el作为锚点，将尾部元素的oldEndVnode.el移动到锚点前。在进行DOM移动之前，仍需要调用patch函数在新旧虚拟节点之间打补丁。
DOM移动后，需要更新对应的索引值，第四步涉及的2个索引为oldEndIndex 和newStartIndex

经过第一遍的对比，执行过第四步的操作。此时新旧两组子节点及真实DOM节点的状态

此时真实DOM节点的顺序为p-4、p-1、p-2、p-3。
开启下一轮的Diff算法更新。因此需要将4个对比的逻辑封装到while循环中,while循环的执行条件是：头部索引值小于等于尾部索引值。

while(oldStartIndex <= oldEndIndex && newStartIndex <= newEndIndex){
  if(oldStartVnode.key === newStartVnode.key){
    // oldStartIndex 和 newStartIndex对比
  }else if(oldEndVnode.key === newEndVnode.key){
    // oldEndIndex 和 newEndIndex对比
    // 旧的尾部p-3 和 新的尾部p-3相同，进入这个判断条件
    // 给oldEndVnode newEndVnode节点进行打补丁操作
    patch(oldEndVnode, newEndVnode, container);
    // 更新索引值
    oldEndVnode = oldChildren[--oldEndIndex];
    newEndVnode = newChildren[--newEndIndex];
  }else if(oldStartVnode.key === newEndVnode.key){
    // oldStartIndex 和 newEndIndex 对比
  }else if(oldEndVnode.key === newStartVnode.key){
    // oldEndIndex 和 newStartIndex 对比
  }
}

真实DOM的顺序没有发生变动，只是对p-3节点进行打补丁操作。
更新完整后，新旧两组子节点与真实DOM的节点状态

接下来进行下一轮的Diff更新

• 头头对比，key不相同，进行下个if判断
• 尾尾对比，key不相同，进行下个if判断

• 头尾对比，p-1的key相同，进入对比。旧节点头部p-1，在新节点中变成了尾部。需要将p-1的真实DOM移动到旧子节点的尾部节点p-2所对应的真实DOM后边。同时更新对应的索引到下一个位置。

  while(oldStartIndex <= oldEndIndex && newStartIndex <= newEndIndex){
  if(oldStartVnode.key === newStartVnode.key){
    // oldStartIndex 和 newStartIndex对比
  }else if(oldEndVnode.key === newEndVnode.key){
    // oldEndIndex 和 newEndIndex对比
  }else if(oldStartVnode.key === newEndVnode.key){
    // oldStartIndex 和 newEndIndex 对比
    // 旧的头部p-1 和 新的尾部p-1相同，进入这个判断条件
    // oldStartVnode newEndVnode节点进行打补丁操作
    patch(oldStartVnode, newEndVnode, container);
    // 将旧头部节点对于的dom oldStartVnode.el 移动到旧尾部节点对应的DOM节点后边
    insert(oldStartVnode.el, container, oldEndVnode.el.nextSibling);
    // 更新索引值
    oldStartVnode = oldChildren[++oldEndIndex];
    newEndVnode = newChildren[--newEndIndex];
  }else if(oldEndVnode.key === newStartVnode.key){
    // oldEndIndex 和 newStartIndex 对比
  }
  }

  移动p-1节点对应的真实DOM，更新索引值。之后的新旧节点和真实DOM的状态如下图
  
  此时，新旧两组子节点的头部索引和尾部索引发生重合，还是满足while的条件，继续进行下轮的diff更新。

• 比较旧的一组子节点中的头部节点p-2与新的一组子节点的头部节点p-2，发现key值相同，可以复用，不用移动DOM，只需patch函数进行打补丁。

  while(oldStartIndex <= oldEndIndex && newStartIndex <= newEndIndex){
  if(oldStartVnode.key === newStartVnode.key){
    // oldStartIndex 和 newStartIndex对比
    // 进入判断条件 p-2节点的对比，调用patch函数，对oldStartVnode和newStartVnode打补丁
    patch(oldStartVnode, newStartVnode, container);
    // 更新相关索引，指向下一个位置
    oldStartVnode  = oldChildren[++oldStartIndex];
    newStartVnode = newChildren[++newStartIndex];
  }else if(oldEndVnode.key === newEndVnode.key){
    // oldEndIndex 和 newEndIndex对比
  }else if(oldStartVnode.key === newEndVnode.key){
    // oldStartIndex 和 newEndIndex 对比
    // 旧的头部p-1 和 新的尾部p-1相同，进入这个判断条件
    // oldStartVnode newEndVnode节点进行打补丁操作
    patch(oldStartVnode, newEndVnode, container);
    // 将旧头部节点对于的dom oldStartVnode.el 移动到旧尾部节点对应的DOM节点后边
    insert(oldStartVnode.el, container, oldEndVnode.el.nextSibling);
    // 更新索引值
    oldStartVnode = oldChildren[++oldEndIndex];
    newEndVnode = newChildren[--newEndIndex];
  }else if(oldEndVnode.key === newStartVnode.key){
    // oldEndIndex 和 newStartIndex 对比
  }
  }

  经过这轮的更新，及索引值的更新，新旧节点和真实DOM节点的状态，如下图
  
  真实DOm节点顺序和新的子节点顺序相同：p-4、p-2、p-1、p-3。这轮更新完后，索引也更新后，发生了oldStartIndex和newStartIndex都小于oldEndIndex和newEndIndex的值，while循环终止，双端diff算法执行完毕
  代码示例

  10.2双端比较的优势

  对比简单diff和双端diff的算法，完成如下图的变动
  
  在简单diff算法中，需要比对vnode并移动DOM各3次，在双端Diff中，只需要一次DOM移动，进行3次patch操作就可以完成。
  可见双端diff对减少DOM移动是非常有利。
  
  继续进行while的判断，diff算法更新
  
  
  完成了所有的diff算法，进行了3次vnode对比，1次DOM移动。

  10.3处理非理想状态

  上面的示例节点处理，正好可以命中while循环的四个if判断，在非理想情况下，如果四个判断都无法命中，接下来该怎么操作？如下图的节点移动
  
  新旧两组节点的顺序

• 旧子节点：p-1、p-2、p-3、p-4

• 新子节点：p-2、p-4、p-1、p-3

进行while循环的diff更新，发现现在的4个if分支都无法满足条件。因此增加额外的处理逻辑

while(oldStartIndex <= oldEndIndex && newStartIndex <= newEndIndex){
  if(oldStartVnode.key === newStartVnode.key){
    // oldStartIndex 和 newStartIndex对比
    // 进入判断条件 p-2节点的对比，调用patch函数，对oldStartVnode和newStartVnode打补丁
    patch(oldStartVnode, newStartVnode, container);
    // 更新相关索引，指向下一个位置
    oldStartVnode  = oldChildren[++oldStartIndex];
    newStartVnode = newChildren[++newStartIndex];
  }else if(oldEndVnode.key === newEndVnode.key){
    // oldEndIndex 和 newEndIndex对比
  }else if(oldStartVnode.key === newEndVnode.key){
    // oldStartIndex 和 newEndIndex 对比
    // 旧的头部p-1 和 新的尾部p-1相同，进入这个判断条件
    // oldStartVnode newEndVnode节点进行打补丁操作
    patch(oldStartVnode, newEndVnode, container);
    // 将旧头部节点对于的dom oldStartVnode.el 移动到旧尾部节点对应的DOM节点后边
    insert(oldStartVnode.el, container, oldEndVnode.el.nextSibling);
    // 更新索引值
    oldStartVnode = oldChildren[++oldEndIndex];
    newEndVnode = newChildren[--newEndIndex];
  }else if(oldEndVnode.key === newStartVnode.key){
    // oldEndIndex 和 newStartIndex 对比
  }else{ // 这里是新增的逻辑判断
   // 遍历旧的子节点，寻找与newStartVnode节点有相同key的节点
    // idxInOld找出新的节点在旧的一组节点中的索引
    const idxInOld = oldChildren.findIndex(
      node => node.key === newStartVnode.key;
    )
  }
}

用新的子节点的头部节点p-2，去旧的一组子节点中查找，找到了可复用的节点，索引位置为1。这意味着节点p-2原本不是头部节点，更新后变成了头部节点，需要移动p-2对应的真实DOM到当前旧的节点的头部p-1所对应的真实DOM之前。代码实现如下：

while(oldStartIndex <= oldEndIndex && newStartIndex <= newEndIndex){
  if(oldStartVnode.key === newStartVnode.key){
    // oldStartIndex 和 newStartIndex对比
    // 进入判断条件 p-2节点的对比，调用patch函数，对oldStartVnode和newStartVnode打补丁
    patch(oldStartVnode, newStartVnode, container);
    // 更新相关索引，指向下一个位置
    oldStartVnode  = oldChildren[++oldStartIndex];
    newStartVnode = newChildren[++newStartIndex];
  }else if(oldEndVnode.key === newEndVnode.key){
    // oldEndIndex 和 newEndIndex对比
  }else if(oldStartVnode.key === newEndVnode.key){
    // oldStartIndex 和 newEndIndex 对比
    // 旧的头部p-1 和 新的尾部p-1相同，进入这个判断条件
    // oldStartVnode newEndVnode节点进行打补丁操作
    patch(oldStartVnode, newEndVnode, container);
    // 将旧头部节点对于的dom oldStartVnode.el 移动到旧尾部节点对应的DOM节点后边
    insert(oldStartVnode.el, container, oldEndVnode.el.nextSibling);
    // 更新索引值
    oldStartVnode = oldChildren[++oldEndIndex];
    newEndVnode = newChildren[--newEndIndex];
  }else if(oldEndVnode.key === newStartVnode.key){
    // oldEndIndex 和 newStartIndex 对比
  }else{ // 这里是新增的逻辑判断
   // 遍历旧的子节点，寻找与newStartVnode节点有相同key的节点
    // idxInOld找出新的节点在旧的一组节点中的索引
    const idxInOld = oldChildren.findIndex(
      node => node.key === newStartVnode.key;
    )
    //如果idxInOld大于0，说明有可复用的节点，需要移动真实DOM节点
    if(idxInOld > 0){
      // idxInOld位置对应的vnode就是需要移动的节点
      const vnodeToMove = oldChildren[idxInOld];
      // 对移动的节点进行patch 打补丁
      patch(vnodeToMove, newStartVnode, container);
      // 将移动的节点对应的DOM【vnodeToMove.el】移动到旧头部节点对应的DOM【oldStartVnode.el】之前
      insert(vnodeToMove.el, container, oldStartVnode.el);
      // 由于idxInOld位置的节点的真实DOM发生了移动，因此该位置设置为undefined
      oldChildren[idxInOld] = undefined;
      //最后更新 newStartIdx的值
      newStartVnode = newChildren[++newStartIdx];
    }
  }
}

代码中先判断idxInOld是否大于0，如果大于0说明找到了可以复用的节点，然后将该节点对应的DOM进行移动。

• patch节点
• 移动节点对应的真实DOM
• 调整idxInOld处节点的值，oldChildren[idxInOld] = undefined
• 更新newStartIdx的索引值

操作之后，新旧节点及真实DOM节点的状态：

真实DOM的顺序为： p-2、p-1、p-3、p-4
继续进行双端Diff算法

继续进行while的判断，可以命中尾头判断，就是oldEndVnode和newStartVnode的key相同。

else if(oldEndVnode.key === newStartVnode.key){ // 尾头
  // 第四步：oldEndVnode 和 newStartVnode
  //使用patch函数进行打补丁
  patch(oldEndVnode, newStartVnode, container);
  // 移动DOM操作
  // oldEndVnode.el 移动到 oldStartVnode.el前面
  insert(oldEndVnode.el, container, oldStartVnode.el)
  // 移动DOM完成后，更新索引值，并指向下一个位置
  oldEndVnode = oldChildren[--oldEndIndex];
  newStartVnode = newChildren[++newStartIndex];
}

操作对比之后，真实DOM节点的顺序：p-2、p-4、p-1、p-3。
然后进行下一轮的Diff对比。对比新旧节点，发现头头节点的key相同，可以复用，不需要移动真实DOM，只用patch对节点进行打补丁。
经过对比p-1节点后，新旧子节点与真实DOM的状态如下图

真实DOM节点的顺序：p-2、p-4、p-1、p-3。接着继续进行下一轮的diff计算。此时旧的头节点值为undefined，说明该节点已经被处理过，直接跳过即可。修改while的逻辑

while(oldStartIndex <= oldEndIndex && newStartIndex <= newEndIndex){
  if(!oldStartVnode){ //处理旧节点开头为undefined
    oldStartVnode = oldChildren[++oldStartIndex];
  }eles if(!oldEndVnode){ //处理旧节点结尾为undefined
    oldEndVnode = oldChildren[--oldEndIndex];
  }else if(oldStartVnode.key === newStartVnode.key){
    // oldStartIndex 和 newStartIndex对比
    // 进入判断条件 p-2节点的对比，调用patch函数，对oldStartVnode和newStartVnode打补丁
    patch(oldStartVnode, newStartVnode, container);
    // 更新相关索引，指向下一个位置
    oldStartVnode  = oldChildren[++oldStartIndex];
    newStartVnode = newChildren[++newStartIndex];
  }else if(oldEndVnode.key === newEndVnode.key){
    // oldEndIndex 和 newEndIndex对比
  }else if(oldStartVnode.key === newEndVnode.key){
    // oldStartIndex 和 newEndIndex 对比
    // 旧的头部p-1 和 新的尾部p-1相同，进入这个判断条件
    // oldStartVnode newEndVnode节点进行打补丁操作
    patch(oldStartVnode, newEndVnode, container);
    // 将旧头部节点对于的dom oldStartVnode.el 移动到旧尾部节点对应的DOM节点后边
    insert(oldStartVnode.el, container, oldEndVnode.el.nextSibling);
    // 更新索引值
    oldStartVnode = oldChildren[++oldEndIndex];
    newEndVnode = newChildren[--newEndIndex];
  }else if(oldEndVnode.key === newStartVnode.key){
    // oldEndIndex 和 newStartIndex 对比
  }else{ // 这里是新增的逻辑判断
   // 遍历旧的子节点，寻找与newStartVnode节点有相同key的节点
    // idxInOld找出新的节点在旧的一组节点中的索引
    const idxInOld = oldChildren.findIndex(
      node => node.key === newStartVnode.key;
    )
    //如果idxInOld大于0，说明有可复用的节点，需要移动真实DOM节点
    if(idxInOld > 0){
      // idxInOld位置对应的vnode就是需要移动的节点
      const vnodeToMove = oldChildren[idxInOld];
      // 对移动的节点进行patch 打补丁
      patch(vnodeToMove, newStartVnode, container);
      // 将移动的节点对应的DOM【vnodeToMove.el】移动到旧头部节点对应的DOM【oldStartVnode.el】之前
      insert(vnodeToMove.el, container, oldStartVnode.el);
      // 由于idxInOld位置的节点的真实DOM发生了移动，因此该位置设置为undefined
      oldChildren[idxInOld] = undefined;
      //最后更新 newStartIdx的值
      newStartVnode = newChildren[++newStartIdx];
    }
  }
}

直接跳过进入下个节点，此时新旧节点和真实DOM节点的状态

现在4个步骤发生重合，接着进行while循环，发现头头节点的key相同，节点可以复用，进行patch打补丁操作。
因为此时新旧节点都属于头部节点，并不需要移动DOM。然后更新指针索引。
新旧节点和真实DOM节点的状态如下

满足了while循环的终止条件，更新完成，最终真实DOM的顺序和新的子节点的顺序一致。
代码示例

10.4添加新元素

接下来处理另外一个特殊情况：

• 旧子节点：p-1、p-2、p-3
• 新子节点：p-4、p-1、p-3、p-2

用新的子节点头部p-4，在旧的子节点中查找，无法找到可复用的节点，说明p-4是新增的节点。
因为p-4是新子节点的头部节点，所以只需将它挂载到当前头部节点之前，当前头部指的是旧的子节点头部所对应的DOM节点p-1。用代码完成操作

while(oldStartIndex <= oldEndIndex && newStartIndex <= newEndIndex){
  if(!oldStartVnode){ //处理旧节点开头为undefined
    oldStartVnode = oldChildren[++oldStartIndex];
  }eles if(!oldEndVnode){ //处理旧节点结尾为undefined
    oldEndVnode = oldChildren[--oldEndIndex];
  }else if(oldStartVnode.key === newStartVnode.key){
    // oldStartIndex 和 newStartIndex对比
    // 进入判断条件 p-2节点的对比，调用patch函数，对oldStartVnode和newStartVnode打补丁
    patch(oldStartVnode, newStartVnode, container);
    // 更新相关索引，指向下一个位置
    oldStartVnode  = oldChildren[++oldStartIndex];
    newStartVnode = newChildren[++newStartIndex];
  }else if(oldEndVnode.key === newEndVnode.key){
    // oldEndIndex 和 newEndIndex对比
  }else if(oldStartVnode.key === newEndVnode.key){
    // oldStartIndex 和 newEndIndex 对比
    // 旧的头部p-1 和 新的尾部p-1相同，进入这个判断条件
    // oldStartVnode newEndVnode节点进行打补丁操作
    patch(oldStartVnode, newEndVnode, container);
    // 将旧头部节点对于的dom oldStartVnode.el 移动到旧尾部节点对应的DOM节点后边
    insert(oldStartVnode.el, container, oldEndVnode.el.nextSibling);
    // 更新索引值
    oldStartVnode = oldChildren[++oldEndIndex];
    newEndVnode = newChildren[--newEndIndex];
  }else if(oldEndVnode.key === newStartVnode.key){
    // oldEndIndex 和 newStartIndex 对比
  }else{ // 这里是新增的逻辑判断
   // 遍历旧的子节点，寻找与newStartVnode节点有相同key的节点
    // idxInOld找出新的节点在旧的一组节点中的索引
    const idxInOld = oldChildren.findIndex(
      node => node.key === newStartVnode.key;
    )
    //如果idxInOld大于0，说明有可复用的节点，需要移动真实DOM节点
    if(idxInOld > 0){
      // idxInOld位置对应的vnode就是需要移动的节点
      const vnodeToMove = oldChildren[idxInOld];
      // 对移动的节点进行patch 打补丁
      patch(vnodeToMove, newStartVnode, container);
      // 将移动的节点对应的DOM【vnodeToMove.el】移动到旧头部节点对应的DOM【oldStartVnode.el】之前
      insert(vnodeToMove.el, container, oldStartVnode.el);
      // 由于idxInOld位置的节点的真实DOM发生了移动，因此该位置设置为undefined
      oldChildren[idxInOld] = undefined;
      //最后更新 newStartIdx的值
      newStartVnode = newChildren[++newStartIdx];
    }
    // ++++++++++新增内容+++++++++++++
    else{ //无法在旧节点找到对应的值
      // 将newStartVnode作为新节点挂载到头部，使用当前头部节点 oldStartVnode.el作为锚点
      patch(null, newStartVnode, container, oldStartVnode.el);
    }
    newStartVnode = newChildren[++newStartIdx]
  }
}

如上代码，当idxInOld>0不成立，说明newStartVnode节点是全新的节点，newStartVnode又是头部节点，应该将其作为新的头部节点进行挂载。
新节点p-4挂载完成后，新旧节点和真实DOM节点的状态

上面的这个例子比较特殊，由于无法命中while中的头头、尾尾、头尾、尾头判断，而进入到了最后的else判断分支，可以将新的开始节点从旧节点中进行查找操作。
如果调整下顺序’：

• 旧子节点：p-1、p-2、p-3
• 新子节点：p-4、p-1、p-2、p-3

按照双端Diff进行更新，进入到尾尾相同的判断分支

继续进行下一轮diff判断，仍然进入尾尾相同的判断分支

继续进行下一轮diff判断，仍然进入尾尾相同的判断分支

此时更新完成后，由于oldEndIndx值小于oldStartIndex的值，无法进行while循环判断。diff停止更新，但是通过观察可以发现节点p-4在整个更新过程中被遗漏，为了修复这个bug，需要在while循环结束后增加if条件语句。
如果oldEndIdx < oldStartIdx && newStartIdx <= newEndIdx成立，说明新的子节点中有遗留的新增节点。

• 索引值位于newStartIdx 和newEndIdx区间的节点都是新增节点。

• 挂载时的锚点仍然使用当前的头部节点oldStartVnode.el

  while(oldStartIndex <= oldEndIndex && newStartIndex <= newEndIndex){
  //...
  }
  if(oldEndIndex< oldStartIndex && newStartIndex <= newEndIndex){
  //如果满足条件，说明新节点有遗留，需要挂载他们
  for(let i=newStartIndex; i<=newEndIndex; i++){
    patch(null, newChildren[i], container, oldStartVnode.el)
  }
  }

  这样就完成了对新增元素的处理。
  代码示例

  10.5移动不存在的元素

  处理过了新增元素，另外还要处理新节点的删除元素。

• 旧子节点：p-1、p-2、p-3

• 新子节点：p-1、p-3

新节点中删除了p-2节点。
执行双端diff更新，进入头头节点相同的分支，

再次执行双端diff更新，进入尾头节点相同的分支

到这里发现变量newStartIndex不小于等于newEndIndex的值，跳出while循环，但是旧的子节点中仍然存在未被处理的节点，应该将其移除。在while循环外，添加if判断分支

while(oldStartIndex <= oldEndIndex && newStartIndex <= newEndIndex){
 //...
}
if(oldEndIndex< oldStartIndex && newStartIndex <= newEndIndex){
  //如果满足条件，说明新节点有遗留，需要挂载他们
  for(let i=newStartIndex; i<=newEndIndex; i++){
    patch(null, newChildren[i], container, oldStartVnode.el)
  }
}else if(newEndIndex < newStartIndex&& oldStartIndex <= oldEndIndex){
 // 移除节点操作
  for(let i=oldStartIndex;i<= oldEndIndex; i++){
    unmount(oldChildren[i])
  }
}

和处理新增节点类似，在while循环外新增if判断分支，使用for循环卸载[oldStartIndex, oldEndIndex]区间不存在的节点。
代码示例