LinkedList的node(int index)方法逻辑解析：位偏移1的由来

嘿，咱们来拆解一下LinkedList里这个node(int index)方法的门道，顺便聊聊那个位运算的小细节：

一、核心实现逻辑 #

这个方法的作用是找到链表中指定索引对应的节点。因为LinkedList是双向链表结构，没法像数组那样直接通过索引随机访问，所以它做了个很实用的优化：

• 先判断目标索引index的位置：
  • 如果index在链表的前半段，就从链表的头节点first出发，顺着next指针往后遍历，一步步走到目标索引的位置，返回该节点。
  • 如果index在链表的后半段，就从链表的尾节点last出发，顺着prev指针往前遍历，同样走到目标索引的位置后返回节点。

说白了，就是根据索引位置选最短的遍历路径，避免不管啥情况都从头走到尾，直接把遍历步数砍了一半。

二、index < (size >> 1)中位偏移的由来 #

这里的size >> 1是个关键细节，咱们拆解开说：

1. 位运算的实际含义：size >> 1是把size这个整数做右移1位的操作，在正整数场景下，这完全等价于size / 2（比如size是10，右移1位就是5；size是9，右移1位是4，和整数除法结果一致）。
2. 为啥用位运算而非除法：计算机执行位运算的效率比除法高得多——位运算是直接操作二进制位的底层操作，不需要除法那样的复杂计算逻辑，用>> 1替代/ 2是纯粹的性能优化手段。
3. 判断的核心意义：这个条件是在判断目标索引是否处于链表的前半部分，这样就能选择从头部还是尾部开始遍历，保证最多只需要遍历链表一半的长度，把实际运行时的遍历成本降到最低，尤其是长链表场景下，这个优化的体感会很明显。

方法实现代码 #

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;
    }
}

内容的提问来源于stack exchange，提问作者Vlad Pavliuk