問(wèn)題描述

閱讀 ADT 列表的 Java 文檔 它說(shuō):

List 接口為列表元素的位置(索引)訪問(wèn)提供了四種方法.列表(如 Java 數(shù)組)是從零開(kāi)始的.請(qǐng)注意，對(duì)于某些實(shí)現(xiàn)(例如 LinkedList 類(lèi))，這些操作的執(zhí)行時(shí)間可能與索引值成正比.因此，如果調(diào)用者不知道實(shí)現(xiàn)，則迭代列表中的元素通常比通過(guò)它索引更可取.

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.

這到底是什么意思?我不明白得出的結(jié)論.

What exactly does this mean? I don't understand the conclusion which is drawn.

推薦答案

在鏈表中，每個(gè)元素都有一個(gè)指向下一個(gè)元素的指針:

In a linked list, each element has a pointer to the next element:

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

要訪問(wèn)item3，你可以清楚地看到，你需要從頭部遍歷每個(gè)節(jié)點(diǎn)，直到到達(dá)item3，因?yàn)槟悴荒苤苯犹D(zhuǎn).

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.

因此，如果我想打印每個(gè)元素的值，如果我這樣寫(xiě):

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));
}

發(fā)生了什么:

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

這效率極低，因?yàn)槊看文幹扑饕龝r(shí)，它都會(huì)從列表的開(kāi)頭重新開(kāi)始并遍歷每個(gè)項(xiàng)目.這意味著您的復(fù)雜性實(shí)際上是 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);
}

然后發(fā)生的事情是這樣的:

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).

現(xiàn)在，轉(zhuǎn)到 List 的另一個(gè)實(shí)現(xiàn)，即 ArrayList，它由一個(gè)簡(jiǎn)單的數(shù)組支持.在那種情況下，上述兩種遍歷都是等價(jià)的，因?yàn)閿?shù)組是連續(xù)的，所以它允許隨機(jī)跳轉(zhuǎn)到任意位置.

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.

這篇關(guān)于為什么迭代 List 比通過(guò)它索引更快?的文章就介紹到這了，希望我們推薦的答案對(duì)大家有所幫助，也希望大家多多支持html5模板網(wǎng)！