LinkedList的O（1）的add（int，E）复杂性如何？

从链接列表标签维基摘录：

链表是一种数据结构，其中元素包含对下一个（以及可选的上一个）元素的引用。链表提供 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;
}

即使使用半尺寸优化，这里的循环（一个或另一个）在我看来也是一个死的赠品，即这种方法（因此）在O（n）时间的最小最坏情况下运行，当然不是恒定时间。foradd(int, E)

我错过了什么？我是否误解了 big-O 符号？