完整的代码：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。下面来走一下流程：
li(a)和li(b)，key不同，只patch，不移动
li(d)和li©，key不同，只patch，不移动
li(a)和li©，key不同，只patch，不移动
li(d)和li(d)，key相同，先patch，需要移动移动，移动的方法就是把prev的li(d)移动到li(a)的前面。然后移动指针，因为prev的最后一个做了移动，所以把prev的指向后面的指针往前移动一个，因为next的第一个vnode已经找到了对应的dom，所以next的前面的指针往后移动一个。
现在比对的图变成了下面这样：
这个时候的真实DOM：
继续比对
li(a)和li(b)，key不同，只patch，不移动。
li©和li©，相同相同，先patch，因为next的最后一个元素也刚好是prev的最后一个，所以不移动，prev和next都往前移动指针。
这个时候真实DOM：
现在最新的比对图：
继续比对
li(a)和li(b)，key不同，只patch，不移动。
li(b)和li(a)，key不同，只patch，不移动。
li(a) 和li (a)，key相同，patch，把prev的li(a)移动到next的后面指针的元素的后面。
真实的DOM变成了这样：