更新一行，不必销毁旧版本

订单编辑器当前保存数量列表二、三。一次操作在头部增加一，另一次操作在同一个旧版本头部增加零。两个新版本分别是一二三、零二三，旧版本仍应是二三。如果每次都复制整个数组，这个行为容易实现，但头插也要搬运所有旧引用。不可变链表可以只新建首节点，让三个版本共享同一段旧尾部。

这里的“持久化”指更新之后旧版本仍可使用，不表示已经写入数据库或磁盘。结构共享是实现这种多版本行为的一种方法，不是定义本身。完整复制也可以保留旧版本，只是成本不同；共享若涉及可变节点，则可能破坏历史。

本章承接 Scala 10“List 的头插为何能够共享旧尾部”。旧段落使用 prepended.tail eq old 观察身份共享，并提醒可变元素仍然泄漏。本章在 Java 21 手写节点构造与路径复制，让共享关系直接对应可阅读的源码，同时与复制 ArrayList 对照。

空节点与非空节点

sealed interface PList<A> permits Nil, Cons {}
record Nil<A>() implements PList<A> {}
record Cons<A>(A head, PList<A> tail) implements PList<A> {
    Cons {
        Objects.requireNonNull(head);
        Objects.requireNonNull(tail);
    }
}

列表只有两种形状：空列表，或一个元素连着余下列表。sealed 限定实现集合，record 保存头尾字段。这里不展开完整和类型教学，只用结构表达递归数据。构造器拒绝空头与空尾引用，空列表必须由 Nil 明确表示，避免把 null 同时当成元素和结束标志。

PList 的泛型 A 仍可指向可变对象，所以节点结构稳定不等于深层不可变。实验主线使用 Integer，其值稳定，能代表数量历史；反例使用 int 数组，故意保留元素修改通道。类型参数不会自动为所有可能的 A 添加不可变保证。

遍历从当前节点开始，只要是 Cons，就取得 head 并转向 tail，遇到 Nil 停止。实验的 values 使用局部 ArrayList 收集内容，最后返回 List.copyOf，便于做值断言。这个辅助方法会物化全部元素，不能被当作常数成本的“查看”操作。

头插只创建一个节点

prepend(x, old) 的实现是 new Cons<>(x, old)。没有修改 old，也没有递归遍历它。新节点保存 x 和旧列表引用；因此新版本的 tail 与 old 必然是同一个对象。实验对头插一与头插零两个分支都做引用相同检查。

a ─→ [1 | ·] ─┐
               ├─→ [2 | ·] ─→ [3 | ·] ─→ Nil
b ─→ [0 | ·] ─┘       ↑
                     old

这张图展示三个根、四个非空节点，而不是为三份列表各分配一套节点。新版本整体值不同，共享部分身份相同。值相等断言检查序列内容，== 在这里专门检查引用共享，两种观察分别承担任务。

不能据此要求所有不可变集合操作都返回共享对象。某个库可以为了实现或小集合特化选择复制，只要符合值契约仍然正确。本实验的身份结论来自这一个明确的构造器。Scala 官方的不可变集合说明提供 List 与其他集合的操作代价背景，Java 教学实现的具体共享仍由自身断言确认。

在数据规模 n 上，当前头插工作与 n 无关，新增一个 Cons；顺序读取所有元素需要沿尾指针前进 n 次。这是操作计数的结构分析，没有测量对象头大小、缓存命中或纳秒时间。Java 对象布局与实际分配成本不能从箭头图精确推出。

中间更新复制通向修改点的路径

将一二三的第二项改成九，不能直接改原先保存二的节点，否则旧版本也会变。一种实现新建保存九的节点，让它继续指向旧的三；再新建保存一的前缀节点，让它指向九。未受影响的三及其尾部继续共享。

static <A> PList<A> updated(PList<A> xs, int index, A value) {
    if (index < 0 || !(xs instanceof Cons<A> c))
        throw new IndexOutOfBoundsException(index);
    return index == 0
            ? new Cons<>(value, c.tail())
            : new Cons<>(c.head(), updated(c.tail(), index - 1, value));
}

实验同时断言新值 [1,9,3]、旧值 [1,2,3]，并检查两个版本位于索引二的后缀引用相同。只检查最终值不能证明共享；只检查共享又不能证明目标更新正确，所以这几项应并存。

更新索引 k 时，当前实现访问从零到 k 的节点，并新建同样长的前缀，包括替换节点。时间与新增节点数都是 O(k+1)，最坏达到 O(n)。递归实现还使用与路径长度相应的调用栈，本章只用小列表，没有把它宣称为任意长输入的安全实现。

索引越界必须显式失败。对两项列表更新索引二，递归最终到达 Nil，实验要求抛 IndexOutOfBoundsException。非法负索引也应拒绝。若直接返回原列表，会使调用方误以为更新成功；若自动补空节点，则是另一个数据模型，不能作为默认修补。

与复制 ArrayList 的同值对照

对同一旧序列执行 new ArrayList<>(values(old))，再 set 目标位置，可以得到与路径复制相同的新值。实验断言两者都为一九三，并再次检查原列表第二项还是二。这个对照锁住行为，让成本讨论不会混入不同结果。

数组复制需要复制全部 n 个元素引用，之后按索引替换是常数操作。链表靠近头部的更新可能只复制很短前缀，但按索引访问要走过此前节点。频繁随机访问和中间修改的工作负载，不一定适合链表；持久向量等结构通过树形布局提供另一种折中，不能由本实验推导链表普遍更快。

本例为比较方便，先用 values 将链表转成列表，这一步本身有线性成本。实际选择存储结构时不应反复在两个表示之间转换，再把转换时间全算给某个算法。基准必须固定输入表示、是否保留历史及结果需求，本章没有开展这样的时间测量。

如果只需要一次构建后一次顺序读取，局部可变 ArrayList 加最后冻结可能更简单。若不断在头部增加元素并保留旧版本，共享链表的结构更贴近需求。选择依据是访问、更新、保留的实际比例，而不是“不可变”这个统一标签。

历史根决定保留空间

从空列表开始，连续头插 n 次并保留每次的根，所有版本可以共享后缀。非空节点总数为 n，另外有 n 个左右的根引用；如果每次都完整复制当前长度，保存全部版本的引用总量会按一加二直到 n 增长。这个差异来自明确的版本构造方式，不是对所有持久结构的通用空间保证。

若每次修改的都是末尾元素，每次路径复制都可能覆盖全部前缀，保留很多版本仍会占用大量节点。结构共享只能复用未变部分，不能把真正不同的历史状态变成零成本。业务应决定保留最近多少次编辑、何时压缩历史，以及是否需要全量审计。

一个旧根即使只用于撤销，也会保持它可达的节点和元素。删除某个根不等于立即回收，其他版本可能还共享相同后缀，调用方也可能保存单个元素引用。这里用可达关系解释保留，没有把 GC 时机或实际释放量写成测量结果。

共享还改变了错误的影响范围。只要节点和元素都稳定，多版本读取可以放心复用；如果某个元素泄漏了修改入口，变化可能同时出现在多个历史版本。实验中的 int 数组从二改九后，旧列表读取到九，新列表的共享尾部也指向它，证明节点不可变没有冻结数组内容。

构造不变量与领域不变量

Cons 保证头尾引用非空，Nil 表示结束。这些是结构不变量，足以让遍历区分结束与节点。数量是否非负、订单行是否重复、价格是否匹配商品，则是领域不变量，当前节点结构并不检查。把非法数字装进不可变链表，只会稳定地保存错误数据。

也不能把“旧版本可读”与“并发更新不会丢失”混淆。两个线程可以各自从同一个旧根生成新根，但如果最后都写入同一个共享变量，仍需要比较交换、锁或其他更新协议决定哪个版本成为当前值。共享稳定节点解决读数据的问题，不自动解决根引用的竞争。

序列化到磁盘是另一个层次。当前对象图共享关系未必会按相同方式保存或恢复，进程重启后对象身份也不同。业务历史通常应按值与版本标识验证，不能把当前内存中的 == 检查变成跨进程协议。

结构成本与操作接口应一起选择

链表的共享优势集中在前缀操作。读取头部、取得尾部和头插只接触固定数量的节点；求长度却必须遍历，除非结构额外保存并维护长度字段。若接口经常询问长度再按索引读取，每个看似简单的方法都可能重新扫描列表。调用方应了解这些操作的组合成本，而不是把所有 List 接口都当成数组使用。当前 values 明确做一次完整遍历，测试没有在内层循环重复调用它。

路径复制也可以在不改变值契约的情况下优化。更新某个位置为原来的相等值时，当前实现仍创建新前缀；一个库可以选择直接复用旧根。但这种优化需要决定用值相等还是身份相同判断，并确保相等比较本身没有不受控成本或副作用。本章没有实现这一优化，因此测试只要求旧值保留和后缀共享，不要求无变化更新一定返回原对象。把实现自由误写成公共保证，会给以后替换存储结构增加不必要限制。

撤销编辑可以只保存旧根，再把当前根切回去；这使撤销本身不必逆向重放每个字段修改。不过如果编辑同时写数据库、扣库存或发送通知，切回内存根并不能撤销这些外部动作。持久数据结构保存状态版本，事务或补偿协议处理外部作用，两者不能互相代替。这里的订单数量列表只有内存值变化，所以历史断言可以直接读取旧根验证。

对实际应用，先列出最频繁的操作往往比先选择“函数式集合”更有用。追加日志可能适合分块结构，频繁头插适合链表，随机索引常需要向量或数组布局。所有这些选择都可以保留旧版本，但共享粒度、访问路径和保留开销不同。当前实验用最小链表展示路径复制机制，不能把它当成通用集合库的替代，也没有宣称手写结构优于经过测试的标准实现。

自测与修改练习

手算：old 为二三，a 是在 old 前加一，b 是在 old 前加零。a.tail 与 b.tail 是否相同？是，都指向 old。把 a 的索引一改九后，新版本还与 b 共享哪些内容？仍可以共享从三开始的后缀，但不再共享包含二的节点。

类型题：PList<int[]> 与 PList<Integer> 都具有稳定头尾字段，哪一个能直接当作数量历史？后者更符合当前值契约；前者的数组元素可被修改。若必须使用数组，应另外规定复制或所有权，泛型参数本身没有限制可变性。

修改练习以 exercise-reverse-preserves-input 为基线。现有循环对一二三不断头插到新累加列表，得到三二一，并断言原序列不变。增加空列表和单元素，再实现 append：递归复制整个前缀并在尾部增加元素，验证结果顺序，同时手算长度 n 时新增多少个 Cons。不要用 append 的结果正确来宣称其成本等同头插。

源码 Main.java的统一入口：

1	`node examples/functional-programming/run.mjs 09`

result.json保存 Java 21 编译与九项显式检查，覆盖共享尾部、历史值、路径复制、未变后缀、ArrayList 同值、可变元素反例、越界、反转及空列表。没有进行堆分析、并发根更新或大深度栈测试，相关成本只在当前结构与操作范围内成立。