插入在ARAYLIST中间与LIKEDLIST（重复）

Question

在Java上下文中说话。如果我想在ArrayList或link edList中间插入，我被告知Arraylist将执行得很糟糕。

我理解这是因为，我们需要移动所有元素，然后进行插入。其顺序应为n/2，即O（n）。

但是linkedList不也是这样吗。对于链表，我们需要遍历到找到中间位置，然后进行指针操作。在这种情况下，也需要O（n）时间。不是吗？

谢啦

Answer 1

我认为，在分析复杂性时，您需要考虑您正在使用的度量。在ArrayList中，您的度量是shuffling，这只是赋值。但这是一个相当复杂的操作。

另一方面，你使用的是一个链接列表，你只是在寻找参考。实际上，您只执行一次插入。因此，虽然算法的复杂度会相似，但在O（n）时间执行的实际过程是不同的。对于ArrayList，它执行大量内存操作。对于链接列表，它只是在读取。

对于那些说他不了解LinkedList的人

LinkedList的开头只有一个指针，结尾只有一个指针。它不会自动知道你要删除的节点后面的节点（除非它是一个双链接列表），所以你需要遍历列表，从创建临时指针开始，直到你到达你要删除的节点之前，我相信OP正在讨论这个。

Answer 2

这里的原因是链表中的元素没有实际的移动。链表由节点组成，每个节点都包含一个元素和指向下一个节点的指针。在列表中插入元素只需要几件事：

1. 创建一个新节点来保存元素
2. 将上一个节点的下一个指针设置为新节点
3. 将新节点的下一个指针设置为列表中的下一个元素

如果你曾经做过一系列的回形针，你可以把每一个回形针看作是它的链条的开始，以及它后面所有的回形针。要把一个新的回形针插入链条，你只需要在新的回形针要去的地方断开回形针，然后插入新的回形针。一个LinkedList就像一个回形针链。

一个ArrayList有点像一个碉堡或一个mancala板，每个隔间只能容纳一件物品。如果你想在中间插入一个新的元素（并且保持所有元素的顺序相同），那么你必须在那个位置之后移动所有的东西。

链表中给定节点之后的插入是恒定的时间，只要你已经有了对该节点的引用（Java中有一个ListIterator），到达该位置通常需要与节点位置成线性的时间。也就是说，到达_n_th节点需要n个步骤。在数组列表（或数组，或任何基于连续内存的结构，真的）中，列表中_n_th元素的地址只是（第一个元素的地址）n×（元素的大小），这只是一点点算术，我们的计算设备支持快速访问任意内存地址。