java - Java 中的不可变/持久列表

Question

作为一个宠物项目，我试图在 Java 中实现一个不可变的列表数据结构，同时尽可能减少副本；我知道 Google Collections，但这不是我想要的，因为列表操作只会返回旧列表的新副本。

我想出了两种不同的方法来解决这个问题；两者都基于双向链表，如下所示:

[head: element1] <--> [element2] <--> [tail: element3]

所以每个列表都包含元组{head, tail}。

---

首先，让我们检查一下将元素追加或添加到列表 A 的简单情况，从而生成列表 B:

A:                 [head: element1] <--> [element2] <--> [tail: element3]
B: [head: element0] <--> [element1] <--> [element2] <--> [tail: element3]

这是 O(1)。由于对列表的迭代仅发生在头和尾之间，A 不会知道任何有关添加到B 的新元素的信息。

当我们尝试在列表中插入或删除任意元素时，这会变得很有趣。

索引元素方法

每个列表都有一个从 0 开始的唯一顺序 ID。每个元素都有一个 {prev, next} 指针数组，对应于列表 id:

  [element1] <--> [element2] <--> [element3] <--> [element4]
A:   [0] <---------> [0] <---------> [0] <---------> [0]
B:   [0] <---------> [1] <-------------------------> [1]
C:   ...

因此，当从列表 A 中删除 id = 0 的 element3 时，prev 或 next 指针分别, element2 和 element4 的 id = 1 (list B) 被更改以反射(reflect)请求操作的结果； element1 保持不变。当遍历索引为 x 的列表时，为了获得正确的 prev 或 next 指针，max(elementIdCount, x) 用于计算正确的索引(对于 element1 为 0，对于 element2 为 1，如果我们使用id = 1，例如)。

添加或替换元素的方法相同。这也是 O(1)，除非需要调整元素 id 数组的大小时，这种情况应该相对较少发生。

最大的问题当然是垃圾收集——一旦一个元素被添加到列表中，它就永远不会被释放，直到所有对原始列表的修改版本的引用都被释放。这可以通过在每 10 次修改时制作整个列表的副本来补救。

这种列表特别适合这样的代码结构:

while (...)
    list = list.addElement(...);

因为在任何给定时间只保留对列表的一次引用。

迭代器方法

另一种方法是滥用迭代器以使结果列表看起来像预期的修改版本；因此每个修改后的不可变列表都包含对其“源”列表的引用和一个附加元组 {operation, element, position}，如下所示:

A: [head: element1] <--> [element2] <--> [tail: element3]
B: source: A, {add, element_to_add, 1}

B 的迭代器然后调用其源列表迭代器(在本例中为 A 的)，除非它遇到已修改(添加、删除或删除)的元素替换)，在这种情况下，它返回该元素，然后再次使用源迭代器继续。

这里明显的缺点是嵌套迭代器的深度随着列表的每个修改版本而增加。这意味着不时制作原始副本也是必要的。

有人对如何改进有任何建议吗？此外，非常欢迎任何指向 60 年代发明的任何可能有用的数据结构的指针:)

Answer 1

您可以创建一个 head::tail 类列表，并获得易于创建和良好内存占用的好处，然后提供一个 API 来对 skip list 进行分层在需要时获得高效的随机访问。

就中间的有效突变而言，跳跃 ListView 可能有一个边表将突变索引映射到元素，以及一个二进制可搜索数组将原始索引映射到插入和删除后的索引偏移。

所有这些映射都提出了一个问题，即如何为某些高效的定义提供高效的不可变映射。我想出的最好方法是使用 b trees它允许 O(log n) 访问可排序键，并允许 O(log n) 在插入和删除时创建节点。在 k 次修改后，基于 b 树的映射的两个持有者之间共享的节点数约为。 (n - k log n) 这对于不经常更新的 map 在实践中非常好。