ArrayList与LinkedList的Big-O复杂度疑问：遍历及中间修改操作

先明确：traversal（遍历）就是iteration（迭代），指从列表的某个起点开始，逐个访问元素直到抵达目标位置的过程。

1. 遍历到列表中间 #

• ArrayList：底层基于数组实现，虽然支持通过索引直接定位元素（O(1)），但“遍历到中间”指的是从头部（或起始点）逐个迭代到中间位置，需要访问前半部分所有元素，时间复杂度为O(n)（n为列表总长度）。
• LinkedList：底层是双向链表，没有随机访问能力，不管从头部还是尾部出发，都需要逐个移动指针才能到达中间位置，时间复杂度为O(n)。

2. 在列表中间进行修改 #

这里分两种场景说明：

• ArrayList：
  • 若只是修改已有元素的值（已知目标索引）：直接通过索引定位数组位置，修改操作是O(1)，和你的猜测一致。
  • 若要插入/删除元素：需要移动中间位置之后的所有元素来调整空间，时间复杂度为O(n)。
• LinkedList：
  • 不管是修改元素值，还是插入/删除元素，都需要先遍历到中间位置（O(n)），之后的修改/指针调整操作是O(1)，整体时间复杂度为O(n)。

你的核心判断是正确的：ArrayList遍历到中间是O(n)、已知索引时修改元素值是O(1)；LinkedList的这两种操作整体都是O(n)。

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