LinkedList基于节点实现，为何支持get(index)索引访问？

问题场景 #

调用linkedList.get(1)可以获取LinkedList中的第二个元素，但LinkedList内部是基于双向链表节点实现的，它是如何做到支持通过索引访问元素的？

代码示例 #

LinkedList<String> linkedList = new LinkedList<>();

linkedList.add("Java");
linkedList.add("Python");
linkedList.get(1); 

get方法核心流程 #

public E get(int index) {
    checkElementIndex(index);
    return node(index).item;
}

private void checkElementIndex(int index) {
     if (!isElementIndex(index))
     throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}

实现原理 #

LinkedList能实现索引访问，关键在于node(int index)方法（上述代码未包含，但它是核心逻辑）：

• 第一步先通过checkElementIndex校验索引合法性，超出链表有效范围直接抛出索引越界异常。
• 进入node方法后，LinkedList会先判断目标索引更靠近链表头部还是尾部：
  • 若索引小于链表长度的一半，就从头节点开始向后逐个遍历，直到找到对应索引的节点。
  • 若索引更靠近尾部，就从尾节点开始向前逐个遍历，定位到目标索引的节点。
• 找到目标节点后，直接返回节点中存储的item值，这就是get(index)能获取对应元素的原因。

需要注意的是，这种基于遍历的索引访问效率较低，时间复杂度为O(n)，远不如ArrayList的O(1)随机访问高效，因此LinkedList不适合频繁按索引访问元素的场景。

内容的提问来源于stack exchange，提问作者Er Rahul Raj