0

The source code in java for getting an element from a linked list using an index

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

and the code for node()

Node<E> node(int index) {
    // assert isElementIndex(index);

    if (index < (size >> 1)) {
        Node<E> x = first;
        for (int i = 0; i < index; i++)
            x = x.next;
        return x;
    } else {
        Node<E> x = last;
        for (int i = size - 1; i > index; i--)
            x = x.prev;
        return x;
    }
}

I can't understand why bitshift operator is used in the if condition. Can someone please explain?

Sujay DSa
  • 1,172
  • 2
  • 22
  • 37

2 Answers2

1

The term size >> 1 is equivalent to using size / 2. That is, the if condition will execute should the index be on the left side of the list. Otherwise, the else condition will be used.

The logic here is a simple divide and conquer approach: It guarantees that the code will only have to walk at most size / 2 items for a list with size number of items. Depending on the index, the search will either start at the end of the list or the beginning of the list.

Tim Biegeleisen
  • 502,043
  • 27
  • 286
  • 360
  • is there any specific advantage of using >> over normal integer division? – Sujay DSa Nov 13 '20 at 05:01
  • 1
    @SujayDSa Under the hood, both `size / 2` and `size >> 1` might already get optimized to the same thing. You may read [here](https://stackoverflow.com/questions/4072703/should-i-bit-shift-to-divide-by-2-in-java) that, in your own code, you probably should avoid the bitshift operator unless you are really intending to do bit shifting (not really the case here, so use divide instead). – Tim Biegeleisen Nov 13 '20 at 05:02
1

size >> 1 is technically size / 2

So if the index is less than size then the linked list is iterating from first to last to get the element.

if the index is greater than size then the linked list is iterating from last to first to get the element.

ex: if the list has 1000 element

if we try to get the element at index 1 then total iterations will be 2.

and if we try to get the element at index 998 even then the total iterations will be 2. instead of iterating 998 times.

So here we are using the shortest path to the element.

Nagasitaram Thigulla
  • 178
  • 9