java的linkedlist底层是无头双向非循环链表，头尾增删通过first/last指针直接修改前后引用，时间复杂度为o(1)；中间操作需先遍历定位，整体为o(n)。
Java 的 LinkedList 底层是无头双向非循环链表，增删节点的核心在于**直接操作前后指针（prev 和 next）**，不涉及数组移动，所以头尾操作时间复杂度为 O(1)。关键不是“找位置”，而是“改引用”。
头插与尾插：一步到位，无需遍历
头插和尾插利用 first 和 last 两个成员变量，直接在链表两端建立连接：
-
头插（
addFirst或push）：新建节点，其next指向原first，prev设为null；再把原first的prev指向新节点；最后更新first = 新节点 -
尾插（
addLast或add）：新建节点，其prev指向原last，next设为null；再把原last的next指向新节点；最后更新last = 新节点
中间插入：先定位前驱，再四连改引
在指定索引位置（如 add(int index, E element)）插入时，需先找到待插入位置的前驱节点（即第 index-1 个节点）。定位后执行四步引用修改：
- 设前驱为
pred，后继为pred.next（可能为null） - 新建节点
newNode，其prev = pred，next = succ pred.next = newNode- 若
succ != null，则succ.prev = newNode；否则说明插在末尾，last = newNode
删除节点：跳过目标，前后直连
无论头删、尾删还是中间删，本质都是让目标节点的前驱和后继“握手”，使其从逻辑链中脱离：
-
头删（
removeFirst）：取first.item作返回值；令first = first.next；若新first非空，则置first.prev = null；否则last = null -
尾删（
removeLast）：取last.item；令last = last.prev；若新last非空，则置last.next = null；否则first = null -
中间删（如
remove(int index)）：先定位到待删节点x；记其prev为pred，next为next；然后pred.next = next，next.prev = pred（注意判空）；最后将x.item/x.prev/x.next置null，协助 GC
为什么中间增删不是 O(1)？
因为 LinkedList 的 public API 是以索引为中心的（比如 add(int, E)），而查找第 i 个节点必须从 first 或 last 出发遍历，平均耗时 O(n/2) ≈ O(n)。这和 C++ std::list 以迭代器为中心、拿到迭代器就能 O(1) 增删有本质区别。真正高效的是已知节点引用或明确操作首尾的场景。
Java免费学习笔记：立即使用
解锁 Java 大师之旅：从入门到精通的终极指南
