最佳答案
Integer[] elements = new Integer[] { 4, 2, 7, 8, 1, 0, 3, 5, 9, 6 };
List<Integer> arrayList = new ArrayList<>(Arrays.asList(elements));
List<Integer> linkedList = new LinkedList<>(Arrays.asList(elements));
for (int i = 0; i < elements.length; i++) { // Runs for O(n)
Integer l1 = arrayList.get(i); // returns in O(1)
Integer l2 = linkedList.get(i); // returns in O(n)
}
ArrayList 的 get(index)
直接从内存位置获取 index
处的元素。
因此,get(index)
的时间为O(1)
get(index)
通过从 LinkedList 的头位置遍历列表来获取 index
处的元素。对于 LinkedList 的给定索引元素,没有可以预测的指定内存位置。
因此,get(index)
的时间为O(n)
ArrayList 的总运行时间 = O(1) * O(n)
= O(n)
LinkedList 的总运行时间 = O(n) * O(n)
= O(n^2)
使用java.util.Iterator类
Iterator iterator = arrayList.iterator();
// total execution time: O(N)
while (iterator.hasNext()) { // runs for each element iteratively
System.out.print(iterator.next());
}
System.out.println();
iterator = linkedList.iterator();
// total execution time: O(N)
while (iterator.hasNext()) { // runs for each element iteratively
System.out.print(iterator.next());
}
System.out.println();
iterator.next()
只是迭代到 List
中的下一个元素。这样做的好处是我们不需要从链表的头部开始查找List Node
。 迭代器类
帮助您保留List
当前节点
位置的地址。
同样可以使用for-each as iterator来实现,它具有更简单的代码实现。
for (Integer I : arrayList) { // runs for each element: total execution time: O(N)
System.out.print(I); // gets in O(1)
}
System.out.println();
for (Integer I : linkedList) { // runs for each element: total execution time: O(N)
System.out.print(I); // gets in O(1)
}
因此使用迭代器,
ArrayList 的总运行时间 = O(n)
LinkedList 的总运行时间 = O(n)
关于java - LinkedList - 使用 "get()"的迭代器来更快地迭代,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/43314846/