This question already has answers here:
When to use LinkedList over ArrayList in Java?
(33个答案)
6年前关闭。
在Java上下文中交谈。如果我想在
我知道这是因为,我们需要移动所有元素,然后进行插入。这应该是n / 2的量级,即O(n)。
但是
谢谢 创建一个新节点来保存元素; 将上一个节点的下一个指针设置为新节点; 将新节点的下一个指针设置为列表中的下一个元素。
如果您曾经制作过一个回形针链,则可以将每个回形针视为其链和其后所有回形针的起点。要将新的回形针插入链中,只需在要去的新回形针的位置断开回形针,然后插入新的回形针即可。
只要您已经有对该节点的引用(在Java中为
(33个答案)
6年前关闭。
在Java上下文中交谈。如果我想在
ArrayList
或linkedList
的中间插入,有人告诉我Arraylist
会表现出色。我知道这是因为,我们需要移动所有元素,然后进行插入。这应该是n / 2的量级,即O(n)。
但是
linkedList
是不一样的。对于链接列表,我们需要遍历直到找到中间的时间,然后进行指针操作。在这种情况下,也需要O(n)时间。不是吗谢谢
最佳答案
原因是链接列表中没有实际的元素移动。链表是由节点构成的,每个节点包含一个元素和一个指向下一个节点的指针。将元素插入列表只需几件事:
如果您曾经制作过一个回形针链,则可以将每个回形针视为其链和其后所有回形针的起点。要将新的回形针插入链中,只需在要去的新回形针的位置断开回形针,然后插入新的回形针即可。
LinkedList
就像一个回形针链。ArrayList
有点像pillbox或mancala board,其中每个隔间只能容纳一个物品。如果要在中间插入一个新元素(并使所有元素保持相同的顺序),则必须将所有内容移到该位置之后。只要您已经有对该节点的引用(在Java中为
ListIterator
),则在链表中给定节点之后的插入是固定时间,并且到达该位置通常需要时间在该节点的位置线性。也就是说,要到达第_n_个节点需要n步。实际上,在数组列表(或数组或任何基于连续内存的结构)中,列表中第_n_th个元素的地址正好是(第一个元素的地址)+ n×(元素的大小),算术的琐碎位,并且我们的计算设备支持快速访问任意内存地址。