data-structures - 基于节点的数据结构的不变性

Question

如果想提供一个不可变的版本，例如 LinkidList，是否有任何通用的方法，使用链接的节点序列来实现？我知道在 ArrayList 的情况下，您将复制底层数组，但在这种情况下，这对我来说并不那么明显......

Answer 1

不可变列表的表示方式基本上与常规链表相同，只是所有通常会修改列表的操作都返回一个新的。这个新列表不一定需要包含整个先前列表的副本，但可以重复使用其中的元素。

我建议通过以下方式实现以下操作：

• 在前面弹出元素：只需返回指向下一个节点的指针。复杂度：O(1)。
• 将元素推到前面：创建一个指向旧列表的第一个节点的新节点并将其返回。O(1)。
• 将列表 a 与列表 b 连接：复制整个列表 a 并让最终节点中的指针指向列表 b 的开头。请注意，这比可变列表上的相同操作要快。O（长度（a））。
• 在位置 x 插入：将所有内容复制到 x，在副本的后面添加一个带有新元素的节点，并让该节点指向位置 x + 1 处的旧列表。O(x)。
• 删除位置 x 处的元素：实际上与插入相同。牛）。
• 排序：您可以只使用普通的快速排序或合并排序。它并不比在可变列表上快得多或慢得多。唯一的区别是您不能就地排序，但必须排序到副本。O(n*log n)。