java - 迭代链表

Question

如果我在java中的链表上使用for-each循环， 是否保证我会按顺序迭代元素 它们出现在哪个列表中？

Answer 1

我发现了 5 种在 Java 中迭代链表的主要方法（包括 Java 8 方法）：

1. For 循环
2. 增强型 For 循环
3. While 循环
4. < em>迭代器
5. 集合的stream() util (Java8)

For循环

LinkedList<String> linkedList = new LinkedList<>();
System.out.println("==> For Loop Example.");
for (int i = 0; i < linkedList.size(); i++) {
    System.out.println(linkedList.get(i));
}

增强的for循环

for (String temp : linkedList) {
    System.out.println(temp);
}

While循环

int i = 0;
while (i < linkedList.size()) {
    System.out.println(linkedList.get(i));
    i++;
}

Iterator

Iterator<String> iterator = linkedList.iterator();
while (iterator.hasNext()) {
    System.out.println(iterator.next()); 
}

collection stream() util (Java 8)

linkedList.forEach((temp) -> {
    System.out.println(temp);
});

需要指出的是，For Loop 或 While 的运行时间循环的时间复杂度为 O(n 平方)，因为 get(i) 操作需要 O(n) 时间（有关详细信息，请参阅此）。其他 3 种方式需要线性时间并且性能更好。

Answer 2

链表保证按顺序执行。

来自文档

有序集合（也称为
顺序）。该界面的使用者
可以精确控制其中的位置
列出每个插入的元素。这
用户可以通过其访问元素
整数索引（列表中的位置），
并在列表中搜索元素。

迭代器()
按正确顺序返回此列表中元素的迭代器。

Answer 3

正如 Linkedlist 的定义所示，它是一个序列，并且保证您按顺序获取元素。

例如：

import java.util.LinkedList;

public class ForEachDemonstrater {
  public static void main(String args[]) {
    LinkedList<Character> pl = new LinkedList<Character>();
    pl.add('j');
    pl.add('a');
    pl.add('v');
    pl.add('a');
    for (char s : pl)
      System.out.print(s+"->");
  }
}

Answer 4

链表确实保证顺序。

不要使用 linkedList.get(i)，尤其是在顺序循环内，因为它违背了链表的目的，并且代码效率低下。

使用ListIterator

    ListIterator<Object> iterator = myLinkedList.listIterator();
    while( iterator.hasNext()) {
        System.out.println(iterator.next());
    }

Answer 5

每个 java.util.List 实现都需要保留顺序，因此您可以使用 ArrayList、LinkedList、Vector 等。它们中的每一个都是有序集合，并且它们中的每一个都保留插入的顺序（请参阅 http://download.oracle.com/javase/1.4.2/docs/ api/java/util/List.html)

Answer 6

为未来的访问者添加我的输入。

首先要做的事情：按照 $jls-14.14.2，for-each内部使用迭代器。

现在，当您使用for-遍历LinkedList时every 或迭代器，则循环始终是顺序的。

但这样很容易出现线程安全问题。因此，可能会发生两件事：

1. 如果您使用非线程安全的 List 实现，那么您将遇到 ConcurrentModificationException
2. 您可以使用像 CopyOnWriteArrayList 这样的线程安全 List 实现。如果您必须使用LinkedList，则只能使用Collections.synchronizedList()将非线程安全LL转换为线程安全LL，但您再次需要注意使用以线程安全的方式迭代器。