我对 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);
最佳答案
根据source code对于 LinkedList
,它确实有一个指向最后一个 Node
的指针:
/**
* Pointer to last node.
* Invariant: (first == null && last == null) ||
* (last.next == null && last.item != null)
*/
transient Node<E> last;
与 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;
}
}
关于java - 如果你想要接近它尾部的元素,LinkedList 是否从末尾开始搜索?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/55224968/