什么是以下code如果ArrayList和LinkedList实现的运行？ [英] What is the running of following code if implement by ArrayList and LinkedList?

问题描述

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

我在想，for循环将采取O（N），但我不清楚是什么东西，如果使用ArrayList和LinkedList加（J，T）之间的区别..
谢谢！

I was thinking that the for loop will take o(n) but I was not clear what what the difference between add(j,t) if using ArrayList and LinkedList.. Thanks!

推荐答案

有关在的ArrayList的一些时隙k插入，发现k为O（1），但那么你将不得不向后推后ķ每一个元素，这是O（n）。然而，在一个结尾插入的ArrayList 摊销O（1），摊销因为我们需要在阵列需要调整大小的情况下，要因素。

For inserting in the some slot k of an ArrayList, finding k is O(1), but then you're going to have to push back each element after k, which is O(n). However, inserting at the end of an ArrayList is amortized O(1), amortized since we need to factor in the situations when the array needs to be resized.

对于的LinkedList ，除非你要在位置k元素的引用，那么你就需要通过列表迭代找到说的位置，这是O（n ），而实际插入始终是O（1）。

For a LinkedList, unless you have a reference to the element at position k, then you need to iterate through the list to find said position, which is O(n), whereas actually inserting is always O(1).

这篇关于什么是以下code如果ArrayList和LinkedList实现的运行？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！