java - 在java中使用数组实现链表？

Question

我在 robbert laffore 中读到我们也可以使用数组实现链表。但问题是如何？

我确实有以下方法:

1) 使用大小为 2 的数组代替 Link 对象，其中一个数组保存该项目，另一个保存对下一个项目的引用。但我不认为这是一个好方法。

有人可以建议一种更好的方法来使用数组实现链接列表吗？

Answer 1

它被称为ArrayList

与 @trutheality 所说的相反，它们不需要固定容量，并且节点不存储下一项的索引。为了解决典型数组的大小限制，ArrayList 被设计为在达到预定义的最小/最大边界时自动调整大小。

调整内部数组的大小是昂贵的。它包括创建一个新数组并将数据从旧数组移动到新数组。因此，限制所需的调整大小操作的数量是有益的。

一种方法是当列表达到最大容量时将数组大小加倍，并在列表达到 1/4 容量时将其缩小一半。

数组不缩小一半容量的原因是为了避免抖动。颠簸是指数组在容量边界边缘增加/减少大小，导致大量调整大小操作，而内部数据变化很少。

尽管调整大小需要付出一定的代价——因为它只在数据集加倍时发生——但实际的性能成本仅为 O(log n)。因此，插入成本是线性 O(N log N)，而检索成本是常数 O(N)。

ArrayList 有一个主要弱点。如果您从列表中添加/删除任意项目，则必须移动数组内容以适应更改。花费线性 O(N) 时间的操作。

尽管在传统 LinkedList 中更改任意项的成本很便宜(即恒定的 O(1) 时间)，但该操作需要查找链中的位置，这会花费线性 O(N) 时间。除非您要创建一个队列，其中列表的两端都经常发生变化，否则使用 ArrayList 作为列表基础可能是更好的选择。

来源:目前正在学习算法类(class)，并且刚刚完成从头开始实现 ArrayList 和 LinkedList。