java - 如果通过ArrayList和LinkedList实现，下面的代码是怎么运行的？

Question

 for (int i =0; i < n; i++){
        lst.add(lst.size()/2,3*i);          
    }

我在想 for 循环将占用 o(n) 但我不清楚如果使用 ArrayList 和 LinkedList 之间的 add(j,t) 有什么区别.. 谢谢！

score 3 · Accepted Answer

对于插入 an 的某个槽 k ArrayList，找到 k 是 O(1)，但是你将不得不在 k 之后推回每个元素，这是 O(n)。但是，在 an 的末尾插入ArrayList是摊销的 O(1)，摊销是因为我们需要考虑需要调整数组大小的情况。

对于 a LinkedList，除非您对位置 k 处的元素有引用，否则您需要遍历列表以找到所述位置，即 O(n)，而实际插入总是 O(1)。

score 1 · Accepted Answer

对于LinkedList<E>：

add(int index, E element) 是 O(n)

对于ArrayList<E>：

add(int index, E element) 是 O(n - index) 摊销，但 O(n) 最坏情况（如上）

来源：

2 回答 2