java list遍历修改 - 为什么迭代List会比编制索引更快?




3 Answers

在链表中,每个元素都有一个指向下一个元素的指针:

head -> item1 -> item2 -> item3 -> etc.

要访问item3 ,您可以清楚地看到,您需要从头部走过每个节点,直到到达item3,因为您无法直接跳转。

因此,如果我想打印每个元素的值,如果我写这个:

for(int i = 0; i < 4; i++) {
    System.out.println(list.get(i));
}

会发生什么呢?

head -> print head
head -> item1 -> print item1
head -> item1 -> item2 -> print item2
head -> item1 -> item2 -> item3 print item3

这是非常低效的,因为每次索引时都会从列表的开始处重新开始并遍历每个项目。 这意味着你的复杂性实际上是O(N^2)来遍历列表!

如果我做到了这一点:

for(String s: list) {
    System.out.println(s);
}

那么会发生什么呢?

head -> print head -> item1 -> print item1 -> item2 -> print item2 etc.

全部在一次遍历中,即O(N)

现在,转到List的另一个实现ArrayList ,它由一个简单的数组支持。 在这种情况下,上述两个遍历都是等价的,因为数组是连续的,所以它允许随机跳转到任意位置。

java修改list元素 java中list

阅读ADT列表Java文档,它说:

List接口提供了四种位置(索引)访问列表元素的方法。 列表(如Java数组)基于零。 请注意,对于某些实现(例如,LinkedList类),这些操作的执行时间可能与索引值成比例。 因此,如果调用者不知道实现,遍历列表中的元素通常更适合通过索引进行索引。

这到底是什么意思? 我不明白所得出的结论。




虽然接受的答案肯定是正确的,但我是否可以指出一个小缺陷。 引用都铎王朝:

现在,转到List的另一个实现ArrayList,它由一个简单的数组支持。 在这种情况下,上述两个遍历都是等价的 ,因为数组是连续的,所以它允许随机跳转到任意位置。

这并不完全正确。 事实是,那

使用ArrayList,手写计数循环速度快大约3倍

来源:Google的Android文档“性能设计”

请注意,手写循环是指索引迭代。 我怀疑它是因为用于增强for循环的迭代器。 它在一个由连续阵列支持的结构中产生较小的惩罚表现。 我也怀疑Vector类可能是这样的。

我的规则是,尽可能使用增强型for循环,如果您真的关心性能,请仅对ArrayLists或Vectors使用索引迭代。 在大多数情况下,你甚至可以忽略这个 - 编译器可能会在后台优化它。

我只想指出,在Android的开发环境中,ArrayLists的遍历不一定等价 。 只是思考的食物。




要查找LinkedList的第i个元素,实现会遍历所有元素直到第i个元素。

所以

for(int i = 0; i < list.length ; i++ ) {
    Object something = list.get(i); //Slow for LinkedList
}



Related