LinkedList的node(int index)方法采用折半遍历而非二分查找，因其是双向链表，不支持O(1)随机访问；它通过比较index与size/2决定从头或尾遍历，将平均步数减半，但时间复杂度仍为O(n)。
LinkedList 的 node(int index) 方法确实实现了折半查找优化，但不是传统意义上的“二分查找”，而是根据索引位置选择从头还是从尾遍历，将平均遍历次数减少约一半。
为什么不能用真正的二分查找？
LinkedList 是链表结构，不支持 O(1) 随机访问。每个节点只有 next 和 prev 引用，无法像数组那样通过下标直接跳转到中间位置。所以它无法做基于比较的二分（比如 arr[mid] vs target），只能优化遍历方向。
折半优化的核心逻辑
该方法会先判断目标索引 index 更靠近头部还是尾部：
- 若
index < size >> 1（即小于长度的一半），则从头（first）开始向后遍历 - 否则从尾（
last）开始向前遍历
这里 size >> 1 等价于 size / 2（整数右移，效率略高），是判断“中点”的关键阈值。
立即学习“Java免费学习笔记（深入）”；
源码关键片段（JDK 8+）
简化后的逻辑如下：
Node<E> node(int index) {
if (index < (size >> 1)) {
Node<E> x = first;
for (int i = 0; i < index; i++)
x = x.next;
return x;
} else {
Node<E> x = last;
for (int i = size - 1; i > index; i--)
x = x.prev;
return x;
}
}
注意：这个优化只影响查找路径长度，不改变时间复杂度——仍是 O(n)，但常数因子减半，对大链表效果明显。
实际效果与注意事项
- 对于索引为 0 或
size-1的访问，都是 O(1)；最坏情况（如取中间）是 O(n/2)，等价于 O(n)，但步数减半 - 该优化在
get(int)、set(int, E)、remove(int)等需要定位节点的方法中被调用 - 如果频繁按索引随机访问，说明数据结构选型可能不合适——应考虑
ArrayList
