Java ConcurrentLinkedQueue 是否具有恒定的删除时间性能?

Question

>http://docs.oracle.com/javase/7/docs/api/java/util/concurrent/ConcurrentLinkedQueue.html#remove（java.lang.Object）

我知道这个数据结构对排队和取消排队具有恒定的时间性能，但它对 remove（Object o） 是否具有恒定的时间性能？

Answer 1

我认为查看ConcurrentLinkedQueue的源代码可以给出明确的答案。

public boolean remove(Object o) {
    if (o == null) return false;
    Node<E> pred = null;
    for (Node<E> p = first(); p != null; p = succ(p)) {
        E item = p.item;
        if (item != null &&
            o.equals(item) &&
            p.casItem(item, null)) {
            Node<E> next = succ(p);
            if (pred != null && next != null)
                pred.casNext(p, next);
            return true;
        }
        pred = p;
    }
    return false;
}

如您所见，在找到删除节点之前，通过队列节点进行迭代，检查每个节点。有了这个，我们可以说删除性能线性取决于队列大小。因此，与 enqueue 和 dequeue 相比，ConcurrentLinkedQueue remove（Object） 方法没有恒定的时间性能，而是依赖于队列大小。