LinkedList 应该使用什么样的迭代？

Question

我知道通过索引遍历 LinkedList 是不好的，因为 list.get(n) 是在线性时间 O(n) 内执行的。因此我不应该使用索引。我查看了由 iterator() 调用返回的 AbstactList.Itr，它也使用 get(cursor) 。我很困惑。

正如@axtavt所指出的，LinkedList.iterator()实际上调用了listIterator()，它返回AbstactList.ListItr，它扩展了AbstactList。 Itr 并且它只添加了 ListIterator 接口的实现。因此，获取下一个元素的机制仍然与 AbstactList.Itr 中的相同。 `AbstactList.Itr 的 next(); 在指定列表上调用 get(n)。

Answer 1

foreach 循环非常高效且简单：

List<String> list = new LinkedList<String>();
list.add("First");
list.add("Second");
list.add("Third");
list.add("Fourth");

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

Answer 2

any List（实际上甚至any Iterable）的最佳迭代是 对于每个循环：

for(Element e : myList){
    // do something
}

Answer 3

LinkedList 不仅继承自 AbstractList，还继承自 AbstractSequentialList，后者又实现了 iterator()，如下所示：

public Iterator<E> iterator() {
    return listIterator();
}

以及 ListIterator LinkedList 返回的 code> 很聪明地使用顺序访问。

因此，无论您使用 foreach、iterator() 还是 listIterator()，您始终处理相同的智能迭代器类型。

Answer 4

如果可以的话，您应该使用 foreach 循环 - 这是最有效的：

List<Item> myList = ...;

for (Item item : myList) {
  ...
}

如果您需要修改循环内的列表，或者在一个循环中遍历多个集合，请使用迭代器：

List<Item> myList = ...;
Iterator<Item> it = myList.iterator();

while (it.hasNext()) {
  Item item = it.next();
  ...
}

如果您需要向后遍历，或者其他什么特定于链表，使用listIterator：

ListIterator<Item> it = myList.listIterator();
...

Answer 5

您可以使用迭代器，它由 iterator 方法返回。转到下一项不需要 O(n) 时间。它使用 LinkedList 的 ListIterator 实现，因此速度很快。

Answer 6

您可以使用Iterator，它可以让您更快地访问。列表的示例代码：

 List<String> list = new LinkedList<String>();
    list.add("First");
    list.add("Second");
    list.add("Third");
    list.add("Fourth");

    Iterator it = list.iterator();

    while(it.hasNext())
    {
        System.out.println(it.next());
    }