1
// 旧列表
2
[<li key="a">Alice</li>, <li key="b">Bob</li>, <li key="c">Charlie</li>]
3

4
// 新列表——只是把 Bob 移到了最后
5
[<li key="a">Alice</li>, <li key="c">Charlie</li>, <li key="b">Bob</li>]

1
type OpType int
2

3
const (
4
    Keep OpType = iota
5
    Insert
6
    Delete
7
)
8

9
type Op struct {
10
    Type  OpType
11
    Value string
12
}
13

14
// Diff 比较两个字符串切片，生成变更操作列表
15
func Diff(old, new []string) []Op {
16
    var ops []Op
17
    oi, ni := 0, 0
18
    for oi < len(old) && ni < len(new) {
19
        if old[oi] == new[ni] {
20
            ops = append(ops, Op{Keep, old[oi]})
21
            oi++; ni++
22
        } else if !contains(new[ni:], old[oi]) {
23
            // 旧元素在剩余新列表中不存在，标记删除
24
            ops = append(ops, Op{Delete, old[oi]})
25
            oi++
26
        } else {
27
            // 新元素需要插入
28
            ops = append(ops, Op{Insert, new[ni]})
29
            ni++
30
        }
31
    }
32
    // 处理剩余元素
33
    for ; oi < len(old); oi++ {
34
        ops = append(ops, Op{Delete, old[oi]})
35
    }
36
    for ; ni < len(new); ni++ {
37
        ops = append(ops, Op{Insert, new[ni]})
38
    }
39
    return ops
40
}
41

42
// Patch 将变更操作应用到旧列表，还原新列表
43
func Patch(ops []Op) []string {
44
    var result []string
45
    for _, op := range ops {
46
        if op.Type != Delete {
47
            result = append(result, op.Value)
48
        }
49
    }
50
    return result
51
}

1
type Op<T> =
2
  | { type: 'keep'; value: T }
3
  | { type: 'insert'; value: T }
4
  | { type: 'delete'; value: T };
5

6
// 比较两个列表，生成最小变更集
7
function diff<T>(
8
  oldList: T[],
9
  newList: T[],
10
  eq: (a: T, b: T) => boolean = (a, b) => a === b,
11
): Op<T>[] {
12
  const ops: Op<T>[] = [];
13
  let oi = 0, ni = 0;
14

15
  while (oi < oldList.length && ni < newList.length) {
16
    if (eq(oldList[oi]!, newList[ni]!)) {
17
      ops.push({ type: 'keep', value: oldList[oi]! });
18
      oi++; ni++;
19
    } else if (!newList.slice(ni).some(n => eq(n, oldList[oi]!))) {
20
      ops.push({ type: 'delete', value: oldList[oi]! });
21
      oi++;
22
    } else {
23
      ops.push({ type: 'insert', value: newList[ni]! });
24
      ni++;
25
    }
26
  }
27
  while (oi < oldList.length) ops.push({ type: 'delete', value: oldList[oi++]! });
28
  while (ni < newList.length) ops.push({ type: 'insert', value: newList[ni++]! });
29
  return ops;
30
}
31

32
// 应用补丁重建新列表
33
function patch<T>(oldList: T[], ops: Op<T>[]): T[] {
34
  const result: T[] = [];
35
  for (const op of ops) {
36
    if (op.type === 'keep' || op.type === 'insert') result.push(op.value);
37
  }
38
  return result;
39
}

1
// 基于 key 的 diff——React 的核心思路（简化版）
2
function keyDiff<T>(
3
  oldList: T[],
4
  newList: T[],
5
  getKey: (item: T) => string,
6
): Op<T>[] {
7
  // 建立 key -> 旧索引 的映射
8
  const oldKeyMap = new Map<string, { index: number; value: T }>();
9
  oldList.forEach((item, i) => oldKeyMap.set(getKey(item), { index: i, value: item }));
10

11
  const ops: Op<T>[] = [];
12
  for (const newItem of newList) {
13
    const key = getKey(newItem);
14
    if (oldKeyMap.has(key)) {
15
      const old = oldKeyMap.get(key)!;
16
      // key 相同但位置不同，标记为移动
17
      ops.push({ type: 'keep', value: newItem });
18
      oldKeyMap.delete(key);
19
    } else {
20
      ops.push({ type: 'insert', value: newItem });
21
    }
22
  }
23
  // 旧列表中剩余的 key 对应删除
24
  for (const { value } of oldKeyMap.values()) {
25
    ops.push({ type: 'delete', value });
26
  }
27
  return ops;
28
}