add(index, element) 方法如何使用 LinkedList 在幕后工作？

Question

当在 ArrayList 中使用 add(index, element) 方法在某个索引处添加元素时，它会将元素放置在在该索引处，而所有其他元素将其索引更改为 1（它们在内存中移动）。这就是为什么 ArrayList 在某个位置添加元素时复杂度为 O(n) 的原因。

在双重 LinkedList 的情况下，我知道元素有指向前一个元素和下一个元素的指针。

我的问题是，当使用与 LinkedList 相关的 add(index, element) 方法时，实际会发生什么场景？我知道使用 LinkedList 其余元素不会在内存中移动，那么为什么它们仍然可以放置在某个索引处而不在内存中移动？

Answer 1

在指定索引处向链表添加新元素需要在链表中向下遍历（从头或尾），然后在新元素中拼接。 LinkedList#add(int index, E element) 的 source code 揭示了同样多的内容：

public void add(int index, E element) {
    checkPositionIndex(index);

    if (index == size)
        linkLast(element);
    else
        linkBefore(element, node(index));
}

如果索引指向列表中的最后一项，它只是在末尾附加一个新节点。否则，它会调用 linkBefore()，它会做一些拼接工作（我也懒得包含它的源代码）。

这里注意，向链表添加新节点并不一定涉及移动现有链表中的任何内容。相反，它主要涉及在后台移动引用。

Answer 2

add(index, element) 的实现如下所示：

public void add(int index, E element) {
    checkPositionIndex(index);

    if (index == size)
        linkLast(element);
    else
        linkBefore(element, node(index));
}

如果你在LinkedList的尾部添加一个元素，linkLast方法可以在常数时间内执行； LinkedList 总是可以直接访问它的最后一个元素，不需要遍历。

否则，node 方法是昂贵的，因为最多需要遍历列表的一半：

Node<E> node(int index) {
    // assert isElementIndex(index);

    if (index < (size >> 1)) {
        Node<E> x = first;
        for (int i = 0; i < index; i++)
            x = x.next;
        return x;
    } else {
        Node<E> x = last;
        for (int i = size - 1; i > index; i--)
            x = x.prev;
        return x;
    }
}

这些元素不需要在内存中移动，因为它们每个都引用它们在 LinkedList 中的前一个和下一个节点，如下面的 linkBefore:

void linkBefore(E e, Node<E> succ) {
    // assert succ != null;
    final Node<E> pred = succ.prev;
    final Node<E> newNode = new Node<>(pred, e, succ);
    succ.prev = newNode;
    if (pred == null)
        first = newNode;
    else
        pred.next = newNode;
    size++;
    modCount++;
}

add(index, element) 方法如何使用 LinkedList 在幕后工作？

How does add(index, element) method work behind the scenes using LinkedList?

java

doubly-linked-list