在 Java 的上下文中交谈。如果我想在 anArrayList或 a中间插入，linkedList有人告诉我这Arraylist会非常糟糕。
我知道这是因为，我们需要移动所有元素然后进行插入。这应该是 n/2 的数量级，即 O(n)。
但是对于linkedList. 对于链表，我们需要遍历直到找到中间，然后进行指针操作。在这种情况下，也需要 O(n) 时间。不会吧？
谢谢
问问题
9882 次
2 回答
7
这里的原因是链表中的元素没有实际移动。链表由节点构成，每个节点都包含一个元素和指向下一个节点的指针。将元素插入列表只需要几件事：
- 创建一个新节点来保存元素；
- 将前一个节点的next指针设置为新节点；
- 将新节点的next指针设置为列表中的下一个元素。
如果您曾经制作过回形针链，您可以将每个回形针视为它链的开头以及后面的所有回形针。要将新的回形针插入链条中，您只需在新回形针所在的位置断开回形针，然后插入新回形针即可。ALinkedList就像一个回形针链。
AnArrayList有点像药盒或曼卡拉板，每个隔间只能容纳一件物品。如果您想在中间插入一个新元素（并使所有元素保持相同的顺序），您将不得不在该位置之后移动所有内容。
在链表中给定节点之后的插入是恒定时间，只要您已经拥有对该节点的引用（ListIterator在 Java 中使用 a ），并且到达该位置通常需要与节点位置成线性关系的时间。也就是说，要到达第_n_th 个节点需要n步。在数组列表（或数组，或任何基于连续内存的结构，实际上）中，列表中 _n_th 元素的地址只是(address of 1st element)+n×(size of element)，一个微不足道的算术位，并且我们的计算设备支持快速访问任意内存地址。
于 2013-10-09T15:17:13.337 回答
0
我认为，在分析复杂性时，您需要考虑您正在使用的指标。在 中ArrayList，您的指标是shuffling，这只是分配。但这是一个相当复杂的操作。
另一方面，您正在使用 a LinkedList，而您只是在寻找参考。实际上，您只执行 1 次插入。因此，虽然算法复杂性最终会相似，但当时正在执行的实际过程O(n)是不同的。在 的情况下ArrayList，它正在执行大量的内存操作。在 a 的情况下LinkedList，它只是读取。
对于那些说他不懂 LinkedLists 的人
LinkedList 仅在开头有一个指针，在结尾有一个指针。它不会自动知道要删除的节点后面的节点（除非它是双向链表），因此您需要遍历列表，从一开始就创建一个临时指针，直到您到达您之前的节点想删除，我相信这是OP正在讨论的。
于 2013-10-09T15:21:02.017 回答