Как метод add (index, element) работает за кулисами, используя LinkedList?

Question

При добавлении элемента по определенному индексу с использованием метода add (index, element) в ArrayList он помещает элемент в этот индекс, в то время как все остальные элементы изменяютсяих индексы на 1 (они перемещаются в памяти).Вот почему ArrayList имеет сложность O (n) при добавлении элемента в определенной позиции.

В случае двукратного LinkedList я знаю, что элементыиметь указатели на предыдущий элемент, а также на следующий.

Мой вопрос: при использовании метода add (index, element) , связанного с LinkedList ,что на самом деле произойдет за кулисами?Я знаю, что при использовании LinkedList остальные элементы не перемещаются в памяти, так почему же они все еще могут быть размещены по определенному индексу, не перемещаясь в памяти?

Answer 1

Добавление нового элемента в связанный список по указанному индексу требует перехода по списку (с головы или хвоста), а затем сращивания в новом элементе.Исходный код для LinkedList#add(int index, E element) показывает столько же:

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++;
}