Naftalins对Java中LinkedList的大分析

问题描述 投票:0回答:1

我正在阅读着名的Naftalin“Java Collections and Generics”一书,表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)。我在这里错过了什么吗?

java linked-list big-o
1个回答
-1
投票

NOP。对,在这种情况下,复杂性是O(n)

我没有这本书,但可以假设它谈论一些特殊情况或关于迭代器remove方法。