Eclipse Collections 不可变List如何实现理想O(1)复杂度的前置追加

首先明确基础性能约束：Eclipse Collections 生态内多数常用的不可变List实现（比如ImmutableArrayList）底层依赖连续数组存储元素，执行前置追加时需要将原有全部元素整体向后位移一位以腾出头部空间，整个过程的耗时和列表长度线性相关，时间复杂度为O(n)，完全达不到O(1)的理想性能要求。

适配O(1)前置的结构选型 #

要实现固定耗时的前置追加，需要选用基于Cons单元设计的不可变列表实现ImmutableConsList。这类结构的每个节点仅存储两部分内容：当前位置的元素值、对下一个节点的引用。
执行前置追加时，实现逻辑完全不触碰原有列表的任何节点：仅新建一个Cons节点，把待追加的元素存进这个新节点，再让新节点的下一个引用直接指向原列表的头部即可。全程没有元素拷贝、没有内存位移，单步操作的耗时完全不随列表长度变化，天然就是O(1)的时间复杂度。

代码示例 #

// 初始化空的Cons型不可变列表
ImmutableList<String> originalEmptyList = Lists.immutable.ofCons();
// 首次前置追加：新建头部节点指向原空列表，O(1)耗时
ImmutableList<String> listWithFirstElement = originalEmptyList.prepend("第一号元素");
// 第二次前置追加：新建头部节点指向上一步得到的列表，依然是O(1)耗时
ImmutableList<String> listWithSecondElement = listWithFirstElement.prepend("第二号元素");
// 最终listWithSecondElement的元素顺序为 [第二号元素, 第一号元素]，原有列表的内容、引用关系不会被任何操作修改

落地注意事项 #

• 这类结构的性能存在明确权衡：ImmutableConsList执行随机索引访问（比如get(index)）时，需要从头节点顺着引用链逐次遍历到目标位置，时间复杂度为O(n)，仅适合频繁头部插入、顺序遍历的场景，不适合需要高频按索引随机访问的业务逻辑
• 多态调用不会改变底层实现的性能：即使将ImmutableConsList实例向上转型为通用的ImmutableList接口类型，调用prepend()时依然会保留原实现的O(1)逻辑；但如果是数组类不可变List实例调用同一个接口的prepend()方法，底层依然会走全量数组拷贝的流程，无法达到目标性能
• 不可变特性全程生效：所有前置追加操作返回的都是全新的列表实例，不会对原有列表造成任何修改，天然适配并发场景下的无锁读取需求

内容的提问来源于stack exchange，提问作者caeus