CODEWITHSUNDEEP
javaperformancedata-structureslinked-list
minhaz1
minhaz1

Reputation: 743

Is Java's LinkedList optimized to do get(index) in reverse when necessary?

I've been working on some ways to optimize LinkedList's. Does anyone know if the Java default doubly-linked LinkedList class is optimized to do get() operations in reverse? For example:

// Some LinkedList list that exists with n elements;
int half = list.size() / 2;
list.get(half + 1);

Would the call to list.get(half + 1) optimize the search and go in reverse since it is a doubly-linked list? It would make more sense to do the search from the end and go towards the center if you know the element is in the second half of the list.

I know using get(index) is O(n) time and that you should use an iterator when traversing a LinkedList, but I am just curious.

Upvotes: 6

Views: 533

Answers (1)

jacobm
jacobm

Reputation: 14025

Yes it is. You can inspect the source code yourself: http://grepcode.com/file/repository.grepcode.com/java/root/jdk/openjdk/6-b14/java/util/LinkedList.java#LinkedList.entry%28int%29

LinkedList#get(int) is implemented as just

return entry(index).element;

where entry is a private method. entry's definition is:

private Entry<E> entry(int index) {
    if (index < 0 || index >= size)
        throw new IndexOutOfBoundsException("Index: "+index+
                                            ", Size: "+size);
    Entry<E> e = header;
    if (index < (size >> 1)) {
        for (int i = 0; i <= index; i++)
            e = e.next;
    } else {
        for (int i = size; i > index; i--)
            e = e.previous;
    }
    return e;
}

As you can see, it counts down from the end if index is greater than the midpoint of the list.

Upvotes: 6

Related Questions