1.简单list diff

var move = function(list, from, to) {
    var item = list.splice(from, 1);
    if (from > to)
        list.splice(to, 0, item[0]);
    else
        list.splice(to - 1, 0, item[0]);
};
var diff = function(oldList, newList) {
    var changes = [];
    // 镜像，模拟位置
    var _oldList = oldList.slice();
    // 遍历旧的，找出 删
    oldList.forEach(function(item, i) {
        if (newList.indexOf(item) === -1) {
            changes.push({
                type: 'remove',
                index: i
            });
            _oldList.splice(i, 1);
        }
    });

    // 遍历新的，找出 增/移/改
    newList.forEach(function(item, i) {
        var index = _oldList.indexOf(item);
        if (index === -1) {
            // 增
            changes.push({
                type: 'insert',
                index: i,
                item: item
            });
            _oldList.splice(i, 0, item);
        }
        else {
            // 移
            if (index !== i) {
                var step = {
                    type: 'move',
                    from: index,
                    to: i
                };
                changes.push(step);
                move(_oldList, step.from, step.to);
            }
        }
    });

    return changes;
};

// test
var showSteps = function(changes) {
    changes.forEach(function(change) {
        switch (change.type) {
            case 'insert':
                console.log('insert ' + change.item + ' before ' + oldList[change.index]);
                oldList.splice(change.index, 0, change.item);
                break;
            case 'remove':
                console.log('remove ' + oldList[change.index]);
                oldList.splice(change.index, 1);
                break;
            case 'check':
                console.log('check ' + oldList[change.index] + ' for update');
                break;
            case 'move':
                console.log('move ' + oldList[change.from] + ' to ' + oldList[change.to]);
                move(oldList, change.from, change.to);
                break;
            default:
                cosole.error('not here');
                break;
        }
        console.log(oldList);
    });
};
var oldList = [1, 2, 3, 7, 4];
var newList = [1, 4, 5, 3, 7, 6];
var changes = diff(oldList, newList);
showSteps(changes);

2.优化空间消耗

// 去掉模拟位置的东西，直接计算changes

var diff = function(oldList, newList) {
    var changes = [];
    // 计算change对oldList未比较元素index的影响，是个区间
    // 因为移动我前面的元素到更前面，并不影响我的index
    // move时，只影响<=lastIndex的index
    // 用<=index: delta表示
    var maxLength = Math.max(oldList.length, newList.length);
    var oldIndexChanges = new Array(maxLength).fill(0);
    // 修正前的index
    var _index;

    // 遍历新的，找出 增/移
    newList.forEach(function(item, i) {
        var index = oldList.indexOf(item);
        if (index === -1) {
            // 增
            changes.push({
                type: 'insert',
                index: i,
                item: item
            });
            // insert影响oldList中后面所有元素的index
            oldIndexChanges[maxLength - 1]++;
        }
        else {
            _index = index;
            // 修正old index
            // 从index数到头，求sum delta
            index += oldIndexChanges.reduce(function(acc, delta, idx) {
                if (idx >= index)
                    return acc + delta;
                else
                    return acc;
            });
            // 移
            if (index !== i) {
                var step = {
                    type: 'move',
                    from: index,
                    to: i
                };
                changes.push(step);
                if (index > i) {
                    // move影响oldList中<=from的元素
                    oldIndexChanges[_index]++;
                }
                else {
                    // from 不可能小于 to
                    // 因为是从前往后扫过来的，[0, to-1]位置确定，不会从前面取元素
                    console.error('impossible');
                }
            }
        }
    });

    // 遍历旧的，找出 删
    // 计算总delta
    // 经过insert和move之后，将被删除的元素一定在最后面，受所有index change影响
    var indexDelta = oldIndexChanges.reduce(function(acc, delta) {
        return acc + delta;
    });
    oldList.forEach(function(item, i) {
        if (newList.indexOf(item) === -1) {
            // 修正old index
            i += indexDelta;
            changes.push({
                type: 'remove',
                index: i
            });
        }
    });

    return changes;
};

// test
var move = function(list, from, to) {
    var item = list.splice(from, 1);
    if (from > to)
        list.splice(to, 0, item[0]);
    else
        list.splice(to - 1, 0, item[0]);
};
var showSteps = function(changes) {
    changes.forEach(function(change) {
        switch (change.type) {
            case 'insert':
                console.log('insert ' + change.item + ' before ' + oldList[change.index]);
                oldList.splice(change.index, 0, change.item);
                break;
            case 'remove':
                console.log('remove ' + oldList[change.index]);
                oldList.splice(change.index, 1);
                break;
            case 'check':
                console.log('check ' + oldList[change.index] + ' for update');
                break;
            case 'move':
                console.log('move ' + oldList[change.from] + ' to ' + oldList[change.to]);
                move(oldList, change.from, change.to);
                break;
            default:
                cosole.error('not here');
                break;
        }
        console.log(oldList);
    });
};
var oldList = [1, 2, 3, 7, 4];
var newList = [1, 4, 5, 3, 7, 6];
// var oldList = [1, 3, 7, 8];
// var newList = [8, 3, 7, 1];
var changes = diff(oldList, newList);
showSteps(changes);

3.react list diff

// react原版实现

var diff = function(oldList, newList) {
    var changes = [];
    // 访问过的之前children表最大的index
    var lastIndex = 0;
    // 上一个放好的节点，用来做 增/移
    var lastPlacedNode = null;

    // 遍历新的，找出 增/移
    newList.forEach(function(item, i) {
        var index = oldList.indexOf(item);
        if (index === -1) {
            // 增
            changes.push({
                type: 'insert',
                item: item,
                afterNode: lastPlacedNode
            });
        }
        else {
            // lastIndex滤掉相对位置没变的 移
            if (index < lastIndex) {
                // 移
                var step = {
                    type: 'move',
                    item: item,
                    afterNode: lastPlacedNode
                };
                changes.push(step);
            }
            lastIndex = Math.max(index, lastIndex);
        }
        lastPlacedNode = item;
    });

    // 遍历旧的，找出 删
    oldList.forEach(function(item, i) {
        if (newList.indexOf(item) === -1) {
            changes.push({
                type: 'remove',
                index: i
            });
        }
    });

    return changes;
};

// test
var move = function(list, from, to) {
    var item = list.splice(from, 1);
    if (from > to)
        list.splice(to + 1, 0, item[0]);
    else
        list.splice(to, 0, item[0]);
};
var insertAfter = function(list, item, index) {
    list.splice(index + 1, 0, item);
};
var showSteps = function(changes) {
    // 留一份，针对 移 用来查以前的位置
    var _oldList = oldList.slice();
    // 针对 增 移 和 删，模拟DOM操作需要知道patching中，旧元素的当前index
    // 实际做DOM patch的时候不需要，因为找到元素后DOM API不需要index就能 增 移 删
    var patchingIndex = -1;
    changes.forEach(function(change) {
        switch (change.type) {
            case 'insert':
                console.log('insert ' + change.item + ' after ' + change.afterNode);
                patchingIndex = oldList.indexOf(change.afterNode);
                insertAfter(oldList, change.item, patchingIndex);
                break;
            case 'remove':
                console.log('remove ' + _oldList[change.index]);
                patchingIndex = oldList.indexOf(_oldList[change.index]);
                oldList.splice(patchingIndex, 1);
                break;
            case 'move':
                console.log('move ' + change.item + ' to pos after ' + change.afterNode);
                patchingIndex = oldList.indexOf(change.afterNode);
                move(oldList, oldList.indexOf(change.item), patchingIndex);
                break;
            default:
                cosole.error('not here');
                break;
        }
        console.log(oldList);
    });
};
var oldList = [1, 2, 3, 7, 4];
var newList = [1, 4, 5, 3, 7, 6];
// var oldList = [1, 3, 7, 8];
// var newList = [8, 3, 7, 1];
var changes = diff(oldList, newList);
showSteps(changes);