java - 什么是对 LinkedList 内部元素的(缓慢)访问

Question

LinkedList 上的帖子说:

LinkedList 允许固定时间插入或删除，但只能顺序访问元素。换句话说，您可以向前或向后移动列表，但在中间抓取一个元素所花费的时间与列表的大小成正比。

我不明白什么有资格捕获中间的元素？

在下面的代码中，假设arrL是一个包含50个元素的LinkedList，当计数器j达到20时，程序执行arrL.get(20 ).. 这是否意味着程序正在获取中间的元素？同样在下面的程序中，我只是向前走列表，不是吗？

    for(int j=0;j<arrL.size();++j){
        arrL.get(j);
    }

Answer 1

是的，在每次迭代中，您都是从头遍历列表到第 j-th 个元素，因此整体循环性能为 n^2(非常差) .这是因为在每次迭代中，您都有独立的 get() 调用，它具有线性性能。

另一方面，如果您使用迭代器，您将一次遍历列表一个元素，在每次迭代中向前移动一个元素，这要快得多:

for(Iterator<E> iter = arrL.iterator(); iter.hasNext();) {
  E e = iter.next();
}

或更好:

for(E k: arrL) {
}

顺便说一句，这是一个非常的基本数据结构问题，Java 与这里无关...