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) 之间有什么区别。谢谢!

Answer 1

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

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