問題描述
閱讀 ADT 列表的 Java 文檔 它說:
List 接口為列表元素的位置(索引)訪問提供了四種方法.列表(如 Java 數組)是從零開始的.請注意，對于某些實現(例如 LinkedList 類)，這些操作的執行時間可能與索引值成正比.因此，如果調用者不知道實現，則迭代列表中的元素通常比通過它索引更可取.
The List interface provides four methods for positional (indexed) access to list elements. Lists (like Java arrays) are zero based. Note that these operations may execute in time proportional to the index value for some implementations (the LinkedList class, for example). Thus, iterating over the elements in a list is typically preferable to indexing through it if the caller does not know the implementation.
這到底是什么意思?我不明白得出的結論.
What exactly does this mean? I don't understand the conclusion which is drawn.
推薦答案
在鏈表中，每個元素都有一個指向下一個元素的指針:
In a linked list, each element has a pointer to the next element:
head -> item1 -> item2 -> item3 -> etc.
要訪問item3，你可以清楚地看到，你需要從頭部遍歷每個節點，直到到達item3，因為你不能直接跳轉.
To access item3, you can see clearly that you need to walk from the head through every node until you reach item3, since you cannot jump directly.
因此，如果我想打印每個元素的值，如果我這樣寫:
Thus, if I wanted to print the value of each element, if I write this:
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) 只是為了遍歷列表！
This is horribly inefficient because every time you are indexing it restarts from the beginning of the list and goes through every item. This means that your complexity is effectively O(N^2) just to traverse the list!
如果我這樣做:
for(String s: list) {
System.out.println(s);
}
然后發生的事情是這樣的:
then what happens is this:
head -> print head -> item1 -> print item1 -> item2 -> print item2 etc.
全部在一次遍歷中，即O(N).
all in a single traversal, which is O(N).
現在，轉到 List 的另一個實現，即 ArrayList，它由一個簡單的數組支持.在那種情況下，上述兩種遍歷都是等價的，因為數組是連續的，所以它允許隨機跳轉到任意位置.
Now, going to the other implementation of List which is ArrayList, that one is backed by a simple array. In that case both of the above traversals are equivalent, since an array is contiguous so it allows random jumps to arbitrary positions.
這篇關于為什么迭代 List 比通過它索引更快?的文章就介紹到這了，希望我們推薦的答案對大家有所幫助，也希望大家多多支持html5模板網！