LinkedList的Node含item、next、prev三个字段，无哨兵节点；add(E)等价于addLast(E)，时间复杂度O(1)；add(int,E)需O(n)查找位置，故频繁中间增删性能远低于ArrayList。
LinkedList 的 Node 结构长什么样
Java 的 LinkedList 底层是双向链表，每个节点由内部静态类 Node 表示，它包含三个字段：item（存储元素）、next（指向后继节点）、prev（指向前驱节点）。没有额外的“头结点”或“哨兵节点”，但 first 和 last 两个引用分别指向链表首尾。
这意味着：空链表时 first == null && last == null；只有一个元素时 first == last，且它的 next == null、prev == null。
add() 和 addLast() 的实际行为差异
add(E e) 是 List 接口定义的方法，在 LinkedList 中它等价于 addLast(e) —— 即总是追加到尾部。这不是约定俗成，而是源码里直接调用的：
public boolean add(E e) {
linkLast(e);
return true;
}而 addFirst(E e) 则调用 linkFirst(e)，会修改 first 引用并调整新节点的 next 指针。两者时间复杂度都是 O(1)，但如果你误以为 add() 是随机位置插入（像 ArrayList.add(int, E) 那样），就会出错。
立即学习“Java免费学习笔记（深入）”；
-
add(int index, E element)才是按索引插入，它会先调用node(int index)查找目标位置 —— 这个查找是 O(n) 的，从头或尾开始遍历取决于index更靠近哪一端 - 频繁在中间位置
add(int, E)或remove(int)，性能远不如ArrayList
为什么 get(int index) 比 ArrayList 慢得多
LinkedList.get(int index) 必须从 first 或 last 出发逐个跳转，无法像数组那样通过下标直接计算地址。源码中 node(int index) 会判断：if (index > 1)) 就从前向后找，否则从后向前找 —— 这只是把最坏情况从 n 降到 n/2，仍是 O(n)。
常见误用场景：
- 写
for (int i = 0; i 遍历LinkedList - 用
list.get(list.size() - 1)取最后一个元素（应改用list.getLast()）
这些操作本可以是 O(1)，却因用了 get() 变成 O(n)。
remove(Object o) 的遍历逻辑和 null 处理
remove(Object o) 会从头开始遍历，对每个节点的 item 调用 equals()。特别注意：当 o == null 时，它匹配的是 item == null 的节点，而不是跳过 null —— 这符合 Collection.remove() 规范。
源码关键片段：
for (Nodex = first; x != null; x = x.next) { if (o == null ? x.item == null : o.equals(x.item)) { unlink(x); return true; } }
这里容易踩的坑：
- 如果链表里有多个相同元素，只删第一个匹配项
- 如果元素类型没重写
equals()，默认用==比较引用，可能删不掉预期对象 -
removeFirst()和removeLast()是 O(1)，但remove(Object)是 O(n)，别混淆
双向链表的优势（O(1) 插入/删除首尾）和劣势（O(n) 随机访问）都源于同一个设计：每个节点只存前后引用，没有索引映射。用错场景时，性能落差比想象中更剧烈。
