在ArrayList和LinkedList中间插入元素
在ArrayList和LinkedList中间插入元素
这个问题在这里已经有答案了:
在Java的上下文中谈论。如果我想在 ArrayList 或 linkedList 的中间插入元素，有人告诉我 ArrayList 的性能会非常糟糕。
我知道这是因为我们需要移动所有元素，然后再进行插入。这应该是n/2的顺序，即O(n)。
但是对于 linkedList，难道不是一样吗？对于链表，我们需要遍历直到找到中间点，然后进行指针操作。在这种情况下，也需要O(n)的时间，不是吗？
谢谢
我认为，在分析复杂度时，你需要考虑你使用的度量标准。在 ArrayList 中，你的度量标准是 移动元素，这只是赋值操作。但这是一个相当复杂的操作。
另一方面，你使用了一个 LinkedList，你只是去到了这个引用。实际上，你只执行了一次插入操作。因此，虽然算法复杂度最终会相似，但实际上在 O(n) 时间内执行的进程是不同的。在 ArrayList 的情况下，它执行了许多内存操作。在 LinkedList 的情况下，它只是读取。
对于那些说他不理解 LinkedList 的人
LinkedList 只有一个指向开头的指针和一个指向结尾的指针。除非它是双向链表，否则它不会自动知道你要删除的节点后面的节点，因此你需要通过创建一个临时指针从开头遍历列表，直到你到达要删除的节点之前的节点，我认为这就是 OP 正在讨论的问题。
原因在于链表中没有实际的元素移位。链表是由节点构成的，每个节点包含一个元素和指向下一个节点的指针。要将一个元素插入列表中，只需要几个步骤：
- 创建一个新的节点来保存元素；
- 将上一个节点的下一个指针设置为新节点；
- 将新节点的下一个指针设置为列表中的下一个元素。
如果你曾经制作过一个纸夹链，你可以将每个纸夹视为它及其后面的所有纸夹的开头。要在链中插入新的纸夹，你只需要在新纸夹将插入的位置处断开链，并插入新纸夹。链表就像一个纸夹链。
ArrayList 类似于一个药盒或曼卡拉棋盘，每个隔间只能容纳一个物品。如果你想在中间插入一个新的元素（并保持所有元素的顺序），你将不得不移动那个位置之后的所有元素。
在链表中给定节点后的插入是常数时间，只要你已经有了对该节点的引用（在 Java 中使用 ListIterator），而到达该位置通常需要与节点位置成线性的时间。也就是说，要到达第 n 个节点需要 n 步。在一个数组列表（或数组，或任何基于连续内存的结构）中，列表中第 n 个元素的地址只是（第一个元素的地址）+n×（元素大小），这是一种微不足道的算术运算，我们的计算设备支持快速访问任意的内存地址。