如何利用LinkedList双向链表处理频繁的插入删除操作-java教程-PHP中文网

linkedlist适合频繁插入删除是因为其双向链表结构支持o(1)的头尾及迭代器定位操作，但随机访问get(i)会退化为o(n)，且内存开销大、非线程安全。

如何利用linkedlist双向链表处理频繁的插入删除操作

为什么 LinkedList 适合频繁插入删除，但别盲目用

因为 LinkedList 在 Java 中是真正的双向链表实现，节点自带 prev 和 next 引用，所以在已知位置（比如通过迭代器或已有节点）做插入/删除时，时间复杂度是 O(1)。但前提是——你得避免触发从头遍历。

常见误用：用 get(int index) 随机访问再删，这会让性能掉到 O(n)，比 ArrayList 还慢。它不是“所有操作都快”，只是“在链表语义下、按引用操作时快”。

适合场景：addFirst()、addLast()、removeFirst()、removeLast()、用 ListIterator 在遍历时 add() 或 remove()
不适合场景：按索引反复 get(i) 后修改；大量随机读 + 少量删；内存敏感环境（每个元素多两个引用字段）
注意：LinkedList 不是线程安全的，多线程下要加锁或换 CopyOnWriteArrayList（但后者写操作更重）

用 ListIterator 替代 for 循环做边遍历边删除

这是最常被忽略的高效用法。普通 for 循环里调 remove(i) 会引发数组搬移（ArrayList）或从头找第 i 个节点（LinkedList），而 ListIterator 持有当前节点引用，remove() 直接断链。

LinkedList<string> list = new LinkedList(Arrays.asList("a", "b", "c", "d"));
ListIterator<string> iter = list.listIterator();
while (iter.hasNext()) {
    String s = iter.next();
    if ("c".equals(s)) {
        iter.remove(); // O(1)，不是 list.remove(s)
    }
}</string></string>

iter.remove() 只能紧跟在 next() 或 previous() 后调用，否则抛 IllegalStateException
不要混用 list.remove(x) 和 iter.remove()，后者不检查值相等，只删上一次遍历定位的节点
如果需要从后往前删，用 list.listIterator(list.size()) 初始化迭代器

addFirst / addLast 比 add(index, e) 快得多

addFirst(e) 和 addLast(e) 是 LinkedList 的原生优势操作，直接改头/尾指针，零遍历。而 add(0, e) 或 add(size(), e) 虽然逻辑等价，但底层仍走统一的 add(int, E) 方法，会先调 node(int) 查位置——哪怕查的是头或尾，也要做 if (index 判断，再决定从头还是从尾遍历。

明确要插头尾时，无条件用 addFirst() / addLast()，别图省事写 add(0, x)
push(e) 等价于 addFirst(e)，pop() 等价于 removeFirst()，适合当栈用
offerFirst(e) 和 offerLast(e) 是 Deque 接口方法，和上面一样快，且失败时返回 false（而非抛异常），适合容错场景