完全持久链表

Question

为什么没有任何实现（在 C、C++、Java 甚至 Python 中）完全持久（不一定是功能性）的链表，其修改次数具有恒定的时间/空间开销？

我想到的数据结构是本文中描述的： http://www.cs.cmu.edu/~sleator/papers/Persistence.htm

经过在谷歌上进行长时间搜索后，我什至无法找到具有上述开销的部分持久链表实现。

PS：我所说的持久性的定义是在以下维基百科页面中描述的： http: //en.wikipedia.org/wiki/Persistent_data_struct

编辑（问题被搁置后）：

我认为提到的原因不适用于我的问题。我并不是完全要求在不同的可用图书馆之间进行推荐，因此不能有“固执己见的答案和垃圾邮件”。我的问题是令人惊讶的是，理论上应该很棒的数据结构却没有被任何已知的语言实现。因此，在我自己实现它之前，我问了这个问题，看看是否有这样的答案：“这很正常，数据结构 X 主导了您正在寻找的数据结构，这就是为什么尽管它很简单，但它尚未实现”。另一个答案可能是“它没有你想象的那么好，因为有一个很大的隐藏常量”或者“它与当今缓存的构建方式做得不太好”......如果我的问题不够清楚，我很抱歉。我改变了我的问题，使我的要求现在更加明确。

Answer 1

您尝试过函数式 Java 库吗？它有一些持久的数据结构：

http://www.functionjava.org/features.html