Why get(index) slow more than remove(index) of LinkedList in Java

Question

I have a LinkedList with 100000 items of String.When i do an operation with index such as get,remove,add, it seems same mechanism. First it browse the list to access Node[index], then does a another manipulation, with "get" it only references to item of Node, whereas even the "remove" does more. But why is the "get" operation take alot more time than the "remove" operation

for(int index=99999;index>=0;index--){
    links.get(index);
}

get time in nanoseconds: 15083052805

for(int index=99999;index>=0;index--){
    links.remove(index);
}

del time in nanoseconds: 2310625

LinkedList's functions:

public E get(int index) {
    checkElementIndex(index);
    return node(index).item;
}

public E remove(int index) {
    checkElementIndex(index);
    return unlink(node(index));
}

useful links [correct benchmark](https://stackoverflow.com/questions/504103/how-do-i-write-a-correct-micro-benchmark-in-java#answer-513259), [robust benchmarking](https://www.ibm.com/developerworks/library/j-benchmark1/) — matoni, Jun 01 '17 at 17:25
@ΔλЛ For an O(N*N) problem, which his get(i) loop represents, 100k elements can be quite enough. — Durandal, Jun 01 '17 at 18:17

score 1 · Answer 1 · answered Jun 01 '17 at 18:09

Getting the element at index N is very costly, since to actually get to the element the list nodes need to be traversed until the element is reached.

Now when you remove the elements in your loop, realize that youre always removing the last element of the list (your i corresponds exactly with list.size()-1 at all times in that loop).

The node(index) method actually optimizes the access by searching from the front/back, depending on if index is closer to 0 or list.size(). In your case of remove its always searching from the back and hits on the first try.

Lesson to be learned: LinkedList is not a suitable list type to access by random index.

score 0 · Answer 2 · answered Jun 01 '17 at 17:46

0

It seems that you are not polling System.currentTimeMillis() (getting the current time) before entering the first loop.

answered Jun 01 '17 at 17:46

luizfzs

1,328
2
18
34

Why get(index) slow more than remove(index) of LinkedList in Java

2 Answers2