列表实现：LinkedList与ArrayList和TreeList相比真的表现得如此糟糕吗？

collections java arraylist linked-list treelist

2022-09-01 19:00:00

摘自 Apache TreeList 文档：

以下相对性能统计信息表示此类：

             get  add  insert  iterate  remove
 TreeList       3    5       1       2       1
 ArrayList      1    1      40       1      40
 LinkedList  5800    1     350       2     325

它接着说：

LinkedList很少是实现的好选择。几乎总是一个很好的替代品，尽管它确实使用了更多的内存。TreeList

我的问题是：

什么是、和时间粉碎？首先，我们是否应该期望现实世界的插入和移除案例非常有利？ArrayListaddinsertremoveLinkedListArrayList
这仅仅是把钉子放在可敬者的棺材里吗？TreeListLinkedList

我很想得出结论，他们已经摊销或忽略了的成长痛苦，并且没有考虑到已经找到的物品的插入和拔出时间。ArrayListLinkedList

答案 1

这里的关键是三个 List 实现中插入/删除操作的复杂性。对于任意索引，ArrayList 具有 O（n）个插入/删除时间，但如果操作位于列表的末尾，则为 O（1）。ArrayList 还具有对任何位置的 O（1）访问的便利性。LinkedList类似地是O（n），但是对于列表两端的操作（开始和结束）和O（n）访问任意位置是O（1）。TreeList 对任何位置的所有操作都具有 O（logn）复杂性。

这清楚地表明，对于足够大的列表，就任意位置的插入/删除而言，TreeList更快。但是AFAIK，TreeLists是作为二叉搜索树实现的，并且与它的O（logn）操作相关联的常量比ArrayLists的类似操作要大得多，ArrayLists只是围绕数组的包装器。这使得 TreeList 对于小列表来说实际上更慢。此外，如果您所做的只是将元素附加到列表中，则ArrayList/LinkedList的O（1）性能显然更快。此外，插入/删除的次数通常比访问次数少得多，这往往会使 ArrayList 在许多情况下总体上更快。LinkedList在列表两端的恒定时间插入/删除使得实现队列，堆栈和Deques等数据结构的速度要快得多。

归根结底，这完全取决于您需要列表的确切用途。没有一个放之四海而皆准的解决方案。您必须选择最适合您工作的实现。

答案 2

这是由于这些集合背后的数据结构。TreeList是一棵树，它允许相对快速的读取，插入，删除（所有O（log n））。ArrayList 使用数组来存储数据，因此在插入或删除时，数组中的每个项目都必须向上或向下移动（最坏情况是 O（n）。数组也具有固定大小，因此，如果它溢出当前数组的容量，则必须创建一个新的、更大的数组（通常是上一个数组大小的两倍，以使调整大小保持在最低限度）。链接列表已使用...链表。链接列表通常具有对列表中第一个（有时是最后一个）元素的引用。然后，列表中的每个元素都与列表中的下一个元素（对于单链表）或下一个和上一个元素（对于双链表）具有折射。因此，要访问特定元素，必须遍历它之前的每个元素才能到达那里（O（n）最坏情况）。插入或删除特定元素时，必须找到要插入或删除元素的位置，这需要时间（O（n）最坏情况）。然而，简单地在开始或结束中添加另一个元素的成本非常低（O（1））。

有关于数据结构的整本书，何时使用它们，我建议阅读更基本的书籍。