java - LinkedList Implementation Java - get(int index) - Explain what this code does
问题描述
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?
解决方案
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.
推荐阅读
- javascript - 过滤两个 MongoDB 数组不起作用(ES6)
- android - Flow LifeCycle 是否可以识别为 LiveData?
- c# - Azure WebJob 执行该函数的频率高于应有的频率
- javascript - 错误:模块“DynamicTestModule”导入了意外的值“DomSanitizer”。请添加@NgModule 注释
- java - 仅当线程池中的线程可用于处理消息时,才从 JMS 队列中将消息出队
- wpf - WPF - 按字体名称访问 Roboto 字体时出现问题
- swift - Swift UI(Xcode 12 Beta):无法构建 ContentView.swift
- c# - 在 C# 中处理视频帧(FFMPEG 慢)
- c# - AdColony 插页式广告不显示(Unity Android)
- ios - 内部 iPad 应用分发 - 离线模式