Изсвязанный список отрывок тега вики:

Связанный список - это структура данных, в которой элементы содержат ссылки на следующий (и, возможно, предыдущий) элемент. Предложение связанных списковO (1) вставка и удаление в любом положении, O (1) список конкатенации, и O (1) доступ в передней (и, возможно, задней) позиции, а также O (1) доступ к следующему элементу. Произвольный доступ имеет сложность O (N) и обычно не реализуется.

(акцент мой)

Я был удивлен, прочитав это - как можно списоквставить по случайному индексу с меньшей сложностью, чем просточтение этот индекс?

Итак, я посмотрел наисходный код дляjava.util.LinkedList,add(int, E) метод является:

public void add(int index, E element) {
    addBefore(element, (index==size ? header : entry(index)));
}

addBefore(E, Entry<E> метод это просто переназначение указателя, но есть такжеentry(int) метод:

if (index < 0 || index >= size)
        throw new IndexOutOfBoundsException("Index: "+index+
                                            ", Size: "+size);
    Entry<E> e = header;
    if (index < (size >> 1)) {
        for (int i = 0; i <= index; i++)
            e = e.next;
    } else {
        for (int i = size; i > index; i--)
            e = e.previous;
    }
    return e;
}

Даже с оптимизацией половинного размера,for цикл здесь (один или другой) кажется мне мертвой раздачей, что этот метод (и, следовательно,add(int, E)) работает в минимальном наихудшем случае O (n) времени и, конечно, не постоянное время.

Что мне не хватает? Я неправильно понимаю обозначение big-O?