java - 如果您想要接近其尾部的元素,LinkedList 是否从末尾开始搜索?
问题描述
我对 LinkedList 在我想要获取数据时如何搜索数据感兴趣。例如:我们有一个包含 1000 个元素的 LinkedList。我想按索引 950 取元素,所以我写了“ list.get (950)
”。java会从一开始就开始寻找那个元素吗?或者它也有一个指向最后一个元素的指针?我写了一个小程序来测试它。但它工作不正确(显示第一次获取的最大时间,不管它是什么。
long time;
time = System.nanoTime();
list.get(1);
time = System.nanoTime() - time;
System.out.println("For element at the beginning " + time);
time = System.nanoTime();
list.get(999);
time = System.nanoTime() - time;
System.out.println("For element at the end " + time);
解决方案
根据它的源代码,LinkedList
它确实有一个指向 last 的指针Node
:
/**
* Pointer to last node.
* Invariant: (first == null && last == null) ||
* (last.next == null && last.item != null)
*/
transient Node<E> last;
与调用 with 的内部方法之一一起使用get
:
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;
}
}
推荐阅读
- c++ - 使用 Tensorflow Lite C,数字分类器
- sql - CTE获取每个父母的所有孩子和嵌套孩子
- javascript - 是否可以在 nuxt static 中启用 gzip 压缩?
- npm - 如何在 m1 上使用 chromedriver err 解决 npm install
- linux - 使用 linux command/srcipting 在 HTML 的特定单词之后提取单词
- telegram-bot - CallbackQueryHandler 或 ConversationHandler 用于从机器人类发送的消息
- html - Angular如何遍历组件类文件数组并渲染它们的模板
- c# - 使用具有指定列的 OpenXml 在 Excel 中插入新行
- python - 如何仅在scrapy spider中每个http请求成功后才执行方法?
- java - Java:LinkedList 插入返回“列表为空”