与ArrayList相比，我们为什么不把线性搜索成本作为链表插入操作的先决条件瓶颈呢？

Question

我问这个问题已经有一段时间了，但我对答案不满意，因为这些区别似乎是武断的，更像是一种盲目接受而非批判性评估的传统智慧。

在ArrayList中，它说插入成本（对于单个元素）是线性的。如果我们在索引p处插入0

在LinkedList中，据说插入成本（对于单个元素）是恒定的。例如，如果我们已经有一个节点，并且我们想在它之后插入，我们会重新排列一些指针，并且很快就完成了。但是首先得到这个节点，除了首先进行线性搜索之外，我看不出还能怎么做（假设这不是像列表开头的前置或结尾的附加这样的琐碎情况）。

然而，在LinkedList的例子中，我们没有计算初始搜索时间。对我来说，这很困惑，因为这有点像说“冰淇淋是免费的...在你付钱之后。”就像，嗯，当然是...但是这跳过了付钱的困难部分。当然，如果你已经有了你想要的节点，在LinkedList中插入将是恒定的时间，但是首先获得那个节点可能需要一些额外的时间！我可以很容易地说，在ArrayList中插入是恒定的时间...在我移动剩余的n-p元素之后。

所以我不明白为什么这个区别只针对其中一个而不是另一个。你可能会说，对于LinkedList，插入被认为是常数，因为在前面或后面插入时，不需要线性时间运算，而在ArrayList中，插入需要在位置p之后复制后缀数组，但我可以很容易地反驳这一点，如果我们在ArrayList的后面插入，它是固定时间摊销的，在大多数情况下不需要额外的拷贝，除非我们达到容量。

换句话说，对于LinkedList，我们将线性内容与常量内容分开，但对于ArrayList，我们不将它们分开，即使在这两种情况下，线性操作可能不被调用或不被调用。

那么，为什么我们认为它们对于LinkedList而不是ArrayList是分开的呢？或者它们只是在LinkedList绝大多数用于头/尾追加和前缀而不是中间元素的上下文中定义的？

Answer 1

如果您使用的是LinkedList，那么很可能不会将其用于随机访问插入。LinkedList为push（在开头插入）或add（因为它有一个对最终元素IIRC的引用）提供了固定的时间。你的猜测是正确的，随机索引的插入（例如插入排序）将需要线性时间，而不是常数。

相比之下，ArrayList在最坏情况下是线性的。大多数情况下，它只是执行阵列复制来移动索引（这是一种低级别的移动，是恒定时间）。只有在需要调整背衬阵列的大小时，才需要线性时间。

Answer 2

这基本上是List和LinkedList的Java接口的限制，而不是链表的基本限制。也就是说，Java没有“指向列表节点的指针”的方便概念。

每种类型的列表都有一些不同的概念，这些概念与指向特定项目的想法密切相关：

• 对列表中特定项目的"引用"的想法
• 列表中某项的整数位置
• 可能在列表中的项的值（可能多次）

最普遍的概念是第一个，通常被封装在迭代器的概念中。碰巧，为数组支持的列表实现迭代器的简单方法是简单地包装一个整数，该整数表示该项在列表中的位置。因此，仅对于数组列表，引用项的第一种和第二种方式是非常紧密的。

然而，对于其他列表类型，甚至对于大多数其他容器类型（树、哈希等），情况并非如此。对项目的一般引用通常类似于指向一个项目周围的包装结构的指针（例如，HashMap.Entry或LinkedList.Entry）。对于这些结构，访问第n个元素的想法是不必要的，甚至是不可能的（例如，无序的集合，如集合和许多哈希映射）。

也许不幸的是，Java将通过索引获取项目的想法变成了一级操作。直接对List对象执行的许多操作都是根据列表索引来实现的：remove（int-index），add（int-index，…），get（int index），等等。所以很自然地认为这些操作是最基本的操作。

对于LinkedList来说，使用指向一个节点的指针来引用一个对象是更基本的方法。您可以传递指针，而不是传递列表索引。插入一个元素后，您会得到一个指向该元素的指针。

在C语言中，这个概念体现在迭代器的概念中，这是引用集合中的项（包括列表）的第一种类方法。那么这样的“指针”存在于Java中吗？当然存在——它是Iterator对象！通常您认为Iterator是用于迭代的，但您也可以认为它指向特定的对象。

所以关键的观察是：给定一个指向对象的指针（迭代器），可以在固定时间内从链表中删除和添加，但从类似数组的列表中，这通常需要线性时间。在删除对象之前，没有搜索对象的内在需求：在很多情况下，您可以维护或输入这样的引用，或者处理整个列表，而在这里，链表的持续时间删除确实会改变算法的复杂性。

当然，如果需要删除包含值“foo”的第一个条目，这意味着搜索和删除操作。基于数组的列表和链表都是用于搜索的O（n），因此它们在这里没有变化，但您可以有意义地将搜索和删除操作分开。

因此，原则上，您可以传递迭代器对象，而不是列出索引或对象值——至少在您的用例支持的情况下。然而，在顶部，我说“Java没有指向列表节点的指针的方便概念”。为什么？

嗯，因为实际上使用Iterator是非常不方便的。首先，首先要给对象一个Iterator是很困难的：例如，与C不同，add（）方法不返回Iterator-所以要获得一个指向刚刚添加的项的指针，您需要继续遍历列表，或者使用listIterator（int index）调用，这对于链表来说是低效的。许多方法（例如，subList（））只支持接受索引的版本，而不支持Iterator-即使这样的方法可以得到有效的支持。

再加上修改列表时迭代器失效的限制，它们实际上对于引用元素变得非常无用，除了在不可变列表中。

因此，Java对列表元素指针的支持是半心半意的，所以很难利用链表提供的固定时间操作，除非是在列表前面添加或在迭代过程中删除项目。

它也不局限于列表，ConcurrentQueue也是一个链接结构，支持固定时间删除，但您无法从Java可靠地使用这种功能。