CODEWITHSUNDEEP
javaoptimizationdoubly-linked-list
Tobias Johansson
Tobias Johansson

Reputation: 376

Get entry/node from LinkedList fastest

From LinkedList.java I found this method for getting a an entry.

/**
 * Returns the indexed entry.
 */
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;
}

What bugs me is:

    if (index < (size >> 1))

Why do a bit shift operation here? Would not something like this be the optimal?

if (index < (size / 2)) {
    for (int i = 0; i <= index; i++)
        e = e.next;
} else {
    for (int i = size; i > index; i--)
        e = e.previous;
}

Since

if (index < (size / 2))

would promise our requested index are in the first half of the list.

Upvotes: 1

Views: 491

Answers (2)

xkothe
xkothe

Reputation: 674

Actually no. Shift operation if very fast at hardware level. It's like connecting wires (bits) and discarting the shifted ones. This only works for integer operations and "for base 2 divisions" so be aware.

Upvotes: 0

Sergey Kalinichenko
Sergey Kalinichenko

Reputation: 726509

There is no reason to do a bit shift right by one in the code example: dividing by two will have the same performance, and perhaps better readability than that of a bit shift. This micro-optimization was very common in the old days of C, but now every optimizer worth its salt would do this replacement for you.

Upvotes: 1

Related Questions