linkedlist 的 get(int index) 方法时间复杂度为 o(n)，因其基于双向链表，需从头或尾遍历定位节点，虽有折半优化但仍属线性扫描；替代方案是使用迭代器遍历以避免重复开销。
Java 中 LinkedList 本身不支持真正意义上的随机访问，get(int index) 方法只是“模拟”随机访问——它内部仍需遍历链表定位节点，时间复杂度为 O(n)，而非数组的 O(1)。
为什么 get(index) 看似随机，实际很慢？
LinkedList 是双向链表，每个节点只存前后引用，没有下标索引。调用 list.get(500) 时，源码会自动判断：如果目标索引小于链表长度一半，就从头节点开始往后走；否则从尾节点往前走。虽然做了折半优化，但仍是线性扫描。
- 例如链表有 1000 个元素，访问索引 500，仍需遍历约 500 次指针跳转
- 访问索引 0 或 size−1 很快（O(1)），但访问中间位置无法避免大量遍历
- 频繁调用 get(i) 遍历整个链表（如 for 循环中写 list.get(i)）会导致性能急剧下降
替代方案：避免在循环中用 get() 访问中间元素
如果你需要顺序处理所有或大部分元素，直接用迭代器更高效：
- 用
for (String s : list)或list.iterator()—— 每次只推进一步，无重复遍历 - 若需同时知道索引，可用
list.listIterator()，它支持nextIndex()和hasNext() - 避免写
for (int i = 0; i 这类代码，复杂度是 O(n²)
真要高频访问中间位置？考虑结构改造
如果业务确实要求低延迟、高频率按索引查 LinkedList 中间元素（比如日志索引、缓存映射），单靠原生 LinkedList 不合适，可搭配辅助结构：
-
Map 缓存索引 → 节点引用：插入/删除时同步维护
Map<integer node>></integer>，查询时 O(1) 定位；代价是额外内存和维护逻辑 - 混合结构：对静态或少变数据，可定期导出到 ArrayList 做只读查询；变动频繁则回写到 LinkedList
- 改用 ArrayList：若随机访问远多于增删，ArrayList 的 O(1) 查找 + 批量操作更合适
小技巧：获取中间元素（非频繁场景）
如果只是偶尔取中间值（比如调试、分页首项），可以用原生方法，但注意边界检查：
int mid = list.size() / 2;if (!list.isEmpty()) E middle = list.get(mid);- 别忘了判空和越界，
get()在非法索引时抛IndexOutOfBoundsException
本质上，LinkedList 的设计目标不是快速索引访问，而是高效增删。选对结构比硬优化 get 更重要。
Java免费学习笔记：立即使用
解锁 Java 大师之旅：从入门到精通的终极指南
