什么是对LinkedList的内部元素的(慢)访问的限定条件

Question

LinkedList上的帖子说:

LinkedList允许恒定时间插入或删除,但仅允许元素的顺序访问.换句话说,you can walk the list forwards or backwards, but grabbing an element in the middle需要时间与列表的大小成比例.

我不明白什么才有资格抓住中间的元素？

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

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

Answer 1

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

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

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

或更好:

for(E k: arrL) {
}

BTW这是一个非常基本的数据结构问题,Java在这里无关......