java中linkedlist的add(int index, e element)时间复杂度为o(n)，因其需先通过折半遍历定位前驱节点（o(n)），再执行o(1)指针插入；虽平均步数减半，但大o记号下仍属线性时间。
Java 中 LinkedList 的 add(int index, E element) 方法确实实现了“折半寻址”优化，即根据目标索引 index 与链表长度的一半比较，决定从头（first）还是从尾（last）开始遍历，从而减少平均移动步数。
为什么需要折半寻址？
LinkedList 是双向链表，不支持 O(1) 随机访问。要插入到指定索引位置，必须先找到该位置的前驱节点（因为插入操作需修改前驱和后继的指针）。若每次都从头遍历，最坏情况（插到末尾）需 O(n) 步；折半后，最坏步数降至 ⌈n/2⌉，虽仍是 O(n)，但常数因子减半，对长链表有实际意义。
折半逻辑怎么实现？
源码中关键判断如下（JDK 8+）：
- 计算
index与size/2的大小关系 - 若
index ，从头节点正向遍历 <code>index步 - 否则，从尾节点反向遍历
size - index步（即倒数第size - index个位置）
实际效果与注意事项
该优化只影响查找前驱节点的遍历开销，不影响插入本身的复杂度（仍为 O(1) 指针操作）。但要注意：
- 它不改变
add(index, e)整体时间复杂度 —— 仍是 O(n) - 对小链表（如 size ≤ 4），折半判断开销可能略高于直接遍历，但影响可忽略
- 该策略依赖
size字段（LinkedList维护了准确的元素数量），所以无需遍历计数 - 与
ArrayList不同，LinkedList的随机插入始终比ArrayList的尾部插入快，但比其头部/尾部插入慢（因后者是 O(1) 或摊还 O(1)）
什么时候该避免用 add(index, e)？
如果频繁在中间位置插入，LinkedList 并非最优选择：
- 考虑改用
ArrayDeque（适合头尾操作）或ArrayList（配合批量操作或尾插） - 若必须按序插入且索引动态变化，可借助
ListIterator进行连续插入（避免重复定位） - 极端场景下，自定义跳表或平衡树结构可能更合适，但属于过度设计
Java免费学习笔记：立即使用
解锁 Java 大师之旅：从入门到精通的终极指南
