Java中LinkedList删除元素复杂度为何是O(n)？有无O(1)删除的API类？

为什么LinkedList的remove(element)是O(n) #

Java的LinkedList确实是双向链表，但remove(Object o)方法的时间复杂度瓶颈不在删除操作本身，而在查找元素对应的节点这一步：

• 调用remove(element)时，JVM需要从头（或尾）开始遍历链表，逐个对比元素直到找到匹配的节点，这个遍历过程是O(n)
• 找到节点后，调整前后节点的prev/next指针确实是O(1)，但整体复杂度由前面的查找步骤主导，所以最终是O(n)

Java API中支持O(1)删除的类 #

如果需要基于元素本身快速删除（O(1)复杂度），可以考虑以下类：

• LinkedHashSet：内部结合了哈希表和双向链表，remove(Object o)方法通过哈希表直接定位元素对应的链表节点，之后调整链表指针的操作是O(1)。注意它是集合，不允许重复元素，且只关注元素本身。
• LinkedHashMap：针对键的删除操作remove(Object key)是O(1)——哈希表快速定位键对应的节点，内部双向链表调整指针耗时可忽略。如果需要存储键值对且要快速删除键，这个类很合适。
• 额外提一句：LinkedList本身有个包级别的remove(Node<E> x)方法是O(1)，但它不是public API，普通代码无法直接调用。

内容的提问来源于stack exchange，提问作者Carl