我有这个问题已经有一段时间了，但我对答案不满意，因为这些区别似乎是武断的，更像是盲目接受而不是批判性评估的传统智慧。
在 ArrayList 中，据说插入成本(对于单个元素(是线性的。如果我们在索引 p 处插入 0 <= p <n，其中>
在LinkedList中，据说插入成本(对于单个元素(是恒定的。例如，如果我们已经有一个节点并且我们想在它之后插入，我们重新排列一些指针，它很快就完成了。但是首先获得这个节点，除了首先进行线性搜索之外，我看不出如何完成它(假设这不是一个微不足道的情况，例如在列表开头预置或在末尾附加(。
然而，在LinkedList的情况下，我们不计算初始搜索时间。对我来说，这很令人困惑，因为这有点像说"冰淇淋是免费的......等你付钱之后。就像，嗯，当然是...但这有点跳过了支付它的困难部分。当然，如果您已经拥有所需的节点，则插入 LinkedList 将是恒定时间，但是首先获取该节点可能需要一些额外的时间！我可以很容易地说插入数组列表是恒定的时间......在我移动剩余的 n-p 元素之后。
所以我不明白为什么对一个而不是另一个进行这种区分。您可能会争辩说，插入对于 LinkedList 来说是常量，因为您在不需要线性时间运算的前面或后面插入，而在 ArrayList 中，插入需要复制位置 p 之后的后缀数组，但我可以很容易地反驳这一点，如果我们在 ArrayList 的后面插入， 它是摊销恒定时间，在大多数情况下不需要额外的复制，除非我们达到容量。
换句话说，我们将线性内容与 LinkedList 的常量内容分开，但我们不会为 ArrayList 将它们分开，即使在这两种情况下，线性操作可能不会被调用或不被调用。
那么，为什么我们认为它们对于LinkedList而不是ArrayList是分开的呢？或者它们只是在 LinkedList 绝大多数用于头/尾附加和前置而不是中间元素的上下文中定义的？
基本上是Java接口对List和LinkedList的限制，而不是链表的基本限制。也就是说，在Java中没有"指向列表节点的指针"的方便概念。
每种类型的列表都有几个不同的概念，这些概念与指向特定项目的想法松散相关：
- 对列表中特定项的"引用"的想法
- 列表中项的整数位置 可能
- 位于列表中的项的值(可能多次(
最一般的概念是第一个概念，通常封装在迭代器的概念中。碰巧的是，为数组支持的列表实现迭代器的简单方法是简单地包装一个整数，该整数引用项在列表中的位置。因此，仅对于数组列表，引用项目的第一和第二种方式非常严格。
但是，对于其他列表类型，甚至对于大多数其他容器类型(树、哈希等(，情况并非如此。对项目的泛型引用通常类似于指向一个项目周围的包装结构的指针(例如，HashMap.Entry 或 LinkedList.Entry (。对于这些结构，访问第 n 个元素的想法不是必需的，甚至是不可能的(例如，像集合和许多哈希映射这样的无序集合(。
也许不幸的是，Java使通过索引获取项目的想法成为一流的操作。许多直接在List对象上的操作都是根据列表索引实现的：remove(int index)、add(int index, ...)、get(int index)等。因此，将这些操作视为基本操作是很自然的。
对于LinkedList来说，使用指向节点的指针来引用对象更为基本。与其传递列表索引，不如传递指针。插入元素后，您将获得指向该元素的指针。
C++这个概念体现在iterator的概念中，这是引用集合中项目(包括列表(的第一类方式。那么Java中是否存在这样的"指针"呢？它确实如此 - 这是Iterator对象！通常，您认为Iterator用于迭代，但您也可以将其视为指向特定对象。
因此，关键的观察结果是：给定一个指向对象的指针(迭代器(，您可以在恒定时间内从链表中删除和添加，但是从类似数组的列表中，这通常需要线性时间。在删除对象之前没有搜索对象的固有需求：在很多情况下，您可以维护或将这样的引用作为输入，或者您正在处理整个列表，在这里，链表的恒定时间删除确实改变了算法的复杂性。
当然，如果您需要执行诸如删除之类的操作，则删除包含值"foo"的第一个条目，该值意味着搜索和删除操作。基于数组的列表和链表都O(n)用于搜索，因此它们在这里不会有所不同 - 但您可以有意义地分离搜索和删除操作。
因此，原则上，您可以传递Iterator对象，而不是列出索引或对象值 - 至少如果您的用例支持它。但是，在顶部我说"Java没有指向列表节点的指针的方便概念"。为什么？
因为实际使用Iterator实际上非常不方便。首先，首先很难获得对象的Iterator：例如，与C++不同，add()方法不返回迭代器 - 因此要获取指向您刚刚添加的项的指针，您需要继续迭代列表或使用listIterator(int index)调用， 这对于链表来说本质上是低效的。许多方法(例如，subList()(仅支持接受索引的版本，但不支持迭代器 - 即使可以有效地支持这种方法。
再加上修改列表时迭代器失效的限制，除了在不可变列表中之外，它们实际上对于引用元素变得毫无用处。
因此，Java对指向列表元素的指针的支持是相当半心半意的，因此很难利用链表提供的恒定时间操作，除非在列表前面添加或在迭代期间删除项目。
它也不仅限于列表 - ConcurrentQueue也是一个支持常量时间删除的链接结构，但你不能可靠地使用 Java 中的这种能力。
如果您使用的是 LinkedList，那么您可能不会将其用于随机访问插入。 LinkedList为推送(在开头插入(或添加(因为它对最终元素IIRC有引用(提供了恒定的时间。 您的怀疑是正确的，即插入到随机索引(例如插入排序(将花费线性时间 - 而不是恒定时间。
相比之下，ArrayList是最坏情况线性的。 大多数情况下，它只是执行数组复制来移动索引(这是一种恒定时间的低级偏移(。 仅当您需要调整后备阵列的大小时，才会需要线性时间。