插入ArrayList vs LinkedList中间
这个问题在这里已经有了答案：
这里的原因是链接列表中元素没有实际移动。 链表由节点构成，每个节点都包含一个元素和一个指向下一个节点的指针。 要将元素插入列表只需要几件事情：
如果您制作了一系列回形针，您可以将每个回形针视为其链条的开始，以及之后的所有回形针。 要将一个新的回形针固定在链条上，只需要在新回形针的位置断开回形针，然后插入新回形针。 LinkedList就像一个回形针链。
一个ArrayList就像一个碉堡或一个mancala板，其中每个隔间只能容纳一个物品。 如果你想在中间插入一个新的元素（并且保持所有元素的顺序相同），那么你将不得不在这个点之后移动所有元素。
只要已经有一个对该节点的引用（在Java中有一个ListIterator ），链接列表中的给定节点之后的插入是恒定时间，并且到达该位置通常需要时间线性的节点位置。 也就是说，要到达第n个节点需要n个步骤。 在一个数组列表（或数组，或基于连续内存的任何结构中），列表中_n_th元素的地址就是（第一个元素的地址）+ n×（元素的大小），算术平凡位，我们的压缩设备支持快速访问任意内存地址。
我认为，在分析复杂性时，您需要考虑您正在使用的指标。 在ArrayList ，您的度量标准是shuffling ，这只是分配。 但这是相当复杂的操作。
另一方面，你正在使用一个LinkedList ，你只是在寻找参考。 事实上，你只执行1次插入。 因此，尽管算法复杂性会相似，但在O(n)时间执行的实际进程是不同的。 在ArrayList的情况下，它正在执行大量的内存操作。 在LinkedList的情况下，它只能读取。
对于那些说他不懂LinkedLists的人
LinkedList只在开始时指向一个指针，在末尾指向一个指针。 它不会自动知道要删除的节点后面的节点（除非它是一个双向链表），因此您需要遍历列表，从一开始就创建一个临时指针，直到您到达之前的节点想要删除，我相信这是OP正在讨论的。
链接地址: http://www.djcxy.com/p/19963.html