Нафталинс большой анализ O для LinkedList в Java

Question

Я читаю знаменитую книгу Нафталина "Коллекции и обобщения Java", и в таблице 15.1 сказано, что большая сложность удаления LinkedList - это O (1), что имеет смысл, если есть ссылка на предыдущий узел. Все, что нужно сделать, это отсоединить узел, который нужно удалить. Когда я проверяю реальную реализацию, я вижу цикл for:

public boolean remove(Object o) {
    if (o == null) {
        for (Node<E> x = first; x != null; x = x.next) {
            if (x.item == null) {
                unlink(x);
                return true;
            }
        }
    } else {
        for (Node<E> x = first; x != null; x = x.next) {
            if (o.equals(x.item)) {
                unlink(x);
                return true;
            }
        }
    }
    return false;
}

Похоже, что он ищет весь список, пока элемент не будет найден. Вот почему, похоже, сложность O (N). Я что-то здесь упускаю?

Answer 1

Nop. Вы правы, в данном случае сложность составляет O(n).

У меня нет книги, но я могу предположить, что она говорит о каком-то особом случае или о методе итератора remove.