What is the running of following code if implement by ArrayList and LinkedList?

Question

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

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!

score 3 · Accepted Answer · answered Nov 03 '13 at 21:50

3

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.

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).

answered Nov 03 '13 at 21:50

Steve P.

14,489
8
42
72

1

@user68498 Since you're new to SO, here take the [tour](http://www.stackoverflow.com/about). Besides the good info, I'm shamelessly asking you to accept my answer. – Steve P. Nov 05 '13 at 08:15
@SteveP. So, overall it would O(n^2) Since the .add is nested in a for loop? – Solsma Dev Nov 05 '13 at 19:42
@Turtle-in-a-bash-shell Yes. – Steve P. Nov 05 '13 at 19:43

score 1 · Answer 2 · edited May 23 '17 at 12:13

1

For LinkedList<E>:

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

For ArrayList<E>:

add(int index, E element) is O(n - index) amortized, but O(n) worst-case (as above)

Source:

https://stackoverflow.com/a/322742/2498729

edited May 23 '17 at 12:13

Community

1
1

answered Nov 03 '13 at 21:55

But I'm Not A Wrapper Class

13,614
6
43
65

@user68498 If you found this answer helpful/correct, you can upvote it or check mark it. And no problem. |=^] – But I'm Not A Wrapper Class Nov 05 '13 at 16:10

What is the running of following code if implement by ArrayList and LinkedList?

2 Answers2