在Java的上下文中说话。如果我想插入ArrayList或linkedList的中间，有人告诉我Arraylist会表现得很糟糕。
我知道这是因为，我们需要移动所有元素，然后进行插入。这应该是 n/2 的顺序，即 O(n(。
但linkedList不是一样吗.对于链表，我们需要遍历直到找到中间，然后进行指针操作。在这种情况下，也需要 O(n( 时间。不会吧？
谢谢
这里的原因是链表中的元素没有实际移动。链表由节点构建，每个节点都包含一个元素和一个指向下一个节点的指针。 要将元素插入列表只需要做几件事：
- 创建一个新节点来保存元素;
- 将上一个节点的下一个指针设置为新节点;
- 将新节点的下一个指针设置为列表中的下一个元素。
如果你曾经制作过回形针链，你可以把每个回形针看作是它链条的开始，以及它之后的所有回形针。 要将新的回形针插入链条，您只需在新回形针将要去的地方断开回形针，然后插入新回形针。LinkedList就像回形针链。
ArrayList有点像碉堡或曼卡拉板，每个隔间只能容纳一件物品。 如果你想在中间插入一个新的元素(并保持所有元素的顺序相同(，你将不得不在该位置之后移动所有内容。
链表中给定节点之后的插入是恒定时间，只要您已经对该节点进行了引用(在 Java 中带有ListIterator(，并且到达该位置通常需要节点位置的时间线性。 也就是说，要到达_n_th节点需要 n 个步骤。 在数组列表(或数组，或任何基于连续内存的结构，实际上(中_n_th元素的地址只是(第一个元素的地址(+n×(元素的大小(，一个微不足道的算术，我们的计算设备支持快速访问任意内存地址。
我认为，在分析复杂性时，您需要考虑所使用的指标。在ArrayList中，你的度量是shuffling，这只是赋值。但这是一个相当复杂的操作。
另一方面，您正在使用LinkedList，并且您只是在寻找参考。实际上，您只执行 1 次插入。因此，虽然算法的复杂性最终会相似，但O(n)时间执行的实际过程是不同的。在ArrayList的情况下，它正在执行大量的内存操作。在LinkedList的情况下，它只是阅读。
对于那些说他不了解链接列表的人
LinkedList 的开头只有一个指针，末尾只有一个指针。它不会自动知道您要删除的节点背后的节点(除非它是双向链表(，因此您需要遍历列表，从创建临时指针开始，直到您来到要删除的节点之前的节点，我相信 OP 正在讨论的就是这个。