узел (int index) в LinkedList

Question

Может кто-нибудь объяснить мне логику метода узла (int index) в LinkedList.Что дает битовое смещение на 1:

(index < (size >> 1))

Метод:

Node<E> node(int 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;
    }
}

Спасибо за ответы!

Answer 1

size >> 1 эквивалентно size / 2

Полагаю, эта функция находит node по индексу x.

По сути, она сравнивает index собщее число узлов.

Если index < size/2, то поиск выполняется от 0 до size/2

Если index > size/2, то поиск выполняется от size до size/2

Так, например, если вы не сравниваете index с size/2, у вас может быть цикл по всему списку, который равен O(n).Делая это, вы можете уменьшить итерацию вдвое.(O(n/2))