This question already has answers here:
When to use LinkedList over ArrayList in Java?

(33个答案)


6年前关闭。




在Java上下文中交谈。如果我想在ArrayListlinkedList的中间插入,有人告诉我Arraylist会表现出色。

我知道这是因为,我们需要移动所有元素,然后进行插入。这应该是n / 2的量级,即O(n)。

但是linkedList是不一样的。对于链接列表,我们需要遍历直到找到中间的时间,然后进行指针操作。在这种情况下,也需要O(n)时间。不是吗

谢谢

最佳答案

原因是链接列表中没有实际的元素移动。链表是由节点构成的,每个节点包含一个元素和一个指向下一个节点的指针。将元素插入列表只需几件事:

  • 创建一个新节点来保存元素;
  • 将上一个节点的下一个指针设置为新节点;
  • 将新节点的下一个指针设置为列表中的下一个元素。

  • 如果您曾经制作过一个回形针链,则可以将每个回形针视为其链和其后所有回形针的起点。要将新的回形针插入链中,只需在要去的新回形针的位置断开回形针,然后插入新的回形针即可。 LinkedList就像一个回形针链。
    ArrayList有点像pillboxmancala board,其中每个隔间只能容纳一个物品。如果要在中间插入一个新元素(并使所有元素保持相同的顺序),则必须将所有内容移到该位置之后。

    只要您已经有对该节点的引用(在Java中为ListIterator),则在链表中给定节点之后的插入是固定时间,并且到达该位置通常需要时间在该节点的位置线性。也就是说,要到达第_n_个节点需要n步。实际上,在数组列表(或数组或任何基于连续内存的结构)中,列表中第_n_th个元素的地址正好是(第一个元素的地址)+ n×(元素的大小),算术的琐碎位,并且我们的计算设备支持快速访问任意内存地址。

    07-24 09:39
    查看更多