CODEWITHSUNDEEP
java
hecarim
hecarim

Reputation: 87

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

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));
}

Upvotes: 0

Views: 196

Answers (2)

Durandal
Durandal

Reputation: 20059

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.

Upvotes: 1

luizfzs
luizfzs

Reputation: 1458

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

Upvotes: 0

Related Questions