一般 for 循环遍历和迭代器遍历 LinkedList 区别

93 阅读 0 评论 62 点赞

我是靠谱客的博主尊敬月光，这篇文章主要介绍一般 for 循环遍历和迭代器遍历 LinkedList 区别，现在分享给大家，希望可以做个参考。

先说区别：

普通for循环：每次遍历一个索引的元素之前，都要访问之前所有的索引。
每次访问一个元素后，都会用游标记录当前访问元素的位置，遍历一个元素，记录一个位置。

普通 for 循环

普通 for 循环遍历方式如下：

复制代码

1
2
3
4
5
6
7
8
9
LinkedList<String> linkedList = new LinkedList<>();
linkedList.add("A");
linkedList.add("B");
linkedList.add("C");
linkedList.add("D");
for(int i = 0 ; i < linkedList.size() ; i++){
System.out.print(linkedList.get(i)+" ");
}

需要注意的是， get(int index) 方法每次都要遍历该索引之前的所有元素，这句话这么理解：

比如上面的一个 LinkedList 集合，放入了 A、B、C、D 四个元素。总共需要四次遍历：

第一次遍历打印 A：只需遍历一次。
第二次遍历打印 B：需要先找到 A，然后再找到 B 打印。
第三次遍历打印 C：需要先找到 A，然后找到 B，最后找到 C 打印。
第四次遍历打印 D：需要先找到 A，然后找到 B，然后找到 C，最后找到 D。

也就是说每次调用 get(int index) 方法时，都是从最前面开始依次往后遍历。这样的话如果集合元素很多，越查找到后面（当然此处的get方法进行了优化，查找前半部分从前面开始遍历，查找后半部分从后面开始遍历，但是需要的时间还是很多）花费的时间越多。那么如何改进呢？

迭代器

迭代器遍历如下：

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
LinkedList<String> linkedList = new LinkedList<>();
linkedList.add("A");
linkedList.add("B");
linkedList.add("C");
linkedList.add("D");
// 从前往后打印
Iterator<String> listIt = linkedList.listIterator();
while(listIt.hasNext()){
System.out.print(listIt.next()+" ");
// A B C D
}
// 从后往前打印
// 通过适配器模式实现的接口，作用是倒叙打印链表
Iterator<String> it = linkedList.descendingIterator();
while(it.hasNext()){
System.out.print(it.next()+" ");
// D C B A
}

在 LinkedList 集合中也有一个内部类 ListItr，方法实现大体上也差不多，通过移动游标指向每一次要遍历的元素，不用在遍历某个元素之前都要从头开始。其方法实现也比较简单：

复制代码

public ListIterator<E> listIterator(int index) {
checkPositionIndex(index);
return new ListItr(index);
}
private class ListItr implements ListIterator<E> {
private Node<E> lastReturned;
private Node<E> next;
private int nextIndex;
private int expectedModCount = modCount;
ListItr(int index) {
// assert isPositionIndex(index);
next = (index == size) ? null : node(index);
nextIndex = index;
}
public boolean hasNext() {
return nextIndex < size;
}
public E next() {
checkForComodification();
if (!hasNext())
throw new NoSuchElementException();
lastReturned = next;
next = next.next;
nextIndex++;
return lastReturned.item;
}
public boolean hasPrevious() {
return nextIndex > 0;
}
public E previous() {
checkForComodification();
if (!hasPrevious())
throw new NoSuchElementException();
lastReturned = next = (next == null) ? last : next.prev;
nextIndex--;
return lastReturned.item;
}
public int nextIndex() {
return nextIndex;
}
public int previousIndex() {
return nextIndex - 1;
}
public void remove() {
checkForComodification();
if (lastReturned == null)
throw new IllegalStateException();
Node<E> lastNext = lastReturned.next;
unlink(lastReturned);
if (next == lastReturned)
next = lastNext;
else
nextIndex--;
lastReturned = null;
expectedModCount++;
}
public void set(E e) {
if (lastReturned == null)
throw new IllegalStateException();
checkForComodification();
lastReturned.item = e;
}
public void add(E e) {
checkForComodification();
lastReturned = null;
if (next == null)
linkLast(e);
else
linkBefore(e, next);
nextIndex++;
expectedModCount++;
}
public void forEachRemaining(Consumer<? super E> action) {
Objects.requireNonNull(action);
while (modCount == expectedModCount && nextIndex < size) {
action.accept(next.item);
lastReturned = next;
next = next.next;
nextIndex++;
}
checkForComodification();
}
final void checkForComodification() {
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
}
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
public ListIterator<E> listIterator(int index) {
checkPositionIndex(index);
return new ListItr(index);
}
private class ListItr implements ListIterator<E> {
private Node<E> lastReturned;
private Node<E> next;
private int nextIndex;
private int expectedModCount = modCount;
ListItr(int index) {
// assert isPositionIndex(index);
next = (index == size) ? null : node(index);
nextIndex = index;
}
public boolean hasNext() {
return nextIndex < size;
}
public E next() {
checkForComodification();
if (!hasNext())
throw new NoSuchElementException();
lastReturned = next;
next = next.next;
nextIndex++;
return lastReturned.item;
}
public boolean hasPrevious() {
return nextIndex > 0;
}
public E previous() {
checkForComodification();
if (!hasPrevious())
throw new NoSuchElementException();
lastReturned = next = (next == null) ? last : next.prev;
nextIndex--;
return lastReturned.item;
}
public int nextIndex() {
return nextIndex;
}
public int previousIndex() {
return nextIndex - 1;
}
public void remove() {
checkForComodification();
if (lastReturned == null)
throw new IllegalStateException();
Node<E> lastNext = lastReturned.next;
unlink(lastReturned);
if (next == lastReturned)
next = lastNext;
else
nextIndex--;
lastReturned = null;
expectedModCount++;
}
public void set(E e) {
if (lastReturned == null)
throw new IllegalStateException();
checkForComodification();
lastReturned.item = e;
}
public void add(E e) {
checkForComodification();
lastReturned = null;
if (next == null)
linkLast(e);
else
linkBefore(e, next);
nextIndex++;
expectedModCount++;
}
public void forEachRemaining(Consumer<? super E> action) {
Objects.requireNonNull(action);
while (modCount == expectedModCount && nextIndex < size) {
action.accept(next.item);
lastReturned = next;
next = next.next;
nextIndex++;
}
checkForComodification();
}
final void checkForComodification() {
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
}
}

这里需要重点注意的是 modCount 字段，前面在增加和删除元素的时候，都会进行自增操作 modCount，这是因为如果想一边迭代，一边用集合自带的方法进行删除或者新增操作，都会抛出异常。（使用迭代器的增删方法不会抛异常）

复制代码

1
2
3
4
5
final void checkForComodification() {
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
}

比如：

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
LinkedList<String> linkedList = new LinkedList<>();
linkedList.add("A");
linkedList.add("B");
linkedList.add("C");
linkedList.add("D");
Iterator<String> listIt = linkedList.listIterator();
while(listIt.hasNext()){
System.out.print(listIt.next()+" ");
// A B C D
// linkedList.remove();
// 此处会抛出异常
listIt.remove();
// 这样可以进行删除操作
}

迭代器的另一种形式就是使用 foreach 循环，底层实现也是使用的迭代器：

复制代码

1
2
3
4
5
6
7
8
9
LinkedList<String> linkedList = new LinkedList<>();
linkedList.add("A");
linkedList.add("B");
linkedList.add("C");
linkedList.add("D");
for(String str : linkedList){
System.out.print(str + "");
}

迭代器和 for 循环性能差异测试

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
LinkedList<Integer> linkedList = new LinkedList<>();
for(int i = 0 ; i < 10000 ; i++){
// 向链表中添加一万个元素
linkedList.add(i);
}
long beginTimeFor = System.currentTimeMillis();
for(int i = 0 ; i < 10000 ; i++){
System.out.print(linkedList.get(i));
}
long endTimeFor = System.currentTimeMillis();
System.out.println("使用普通for循环遍历10000个元素需要的时间："+ (endTimeFor - beginTimeFor));
long beginTimeIte = System.currentTimeMillis();
Iterator<Integer> it = linkedList.listIterator();
while(it.hasNext()){
System.out.print(it.next()+" ");
}
long endTimeIte = System.currentTimeMillis();
System.out.println("使用迭代器遍历10000个元素需要的时间："+ (endTimeIte - beginTimeIte));

打印结果：

复制代码

1
2
3
使用普通for循环遍历10000个元素需要的时间：100
使用迭代器遍历10000个元素需要的时间：24

可以看出当打印10000个元素时，两者的时间大约相差3倍，当元素个数更多时，性能差距将会更大。

最后

以上就是尊敬月光最近收集整理的关于一般 for 循环遍历和迭代器遍历 LinkedList 区别的全部内容，更多相关一般内容请搜索靠谱客的其他文章。

本图文内容来源于网友提供，作为学习参考使用，或来自网络收集整理，版权属于原作者所有。

本文分类：Java源码
浏览次数：93 次浏览
发布日期：2023-03-09 15:42:01
本文链接：https://www.kaopuke.com/article/k-p-k_14_ujo_6_fx_14_zg4.html

一般 for 循环遍历和迭代器遍历 LinkedList 区别

普通 for 循环

迭代器

迭代器和 for 循环性能差异测试

最后

评论列表共有 0 条评论

发表评论取消回复

一般 for 循环遍历和迭代器遍历 LinkedList 区别

普通 for 循环

迭代器

迭代器和 for 循环性能差异测试

最后

相关文章

评论列表共有 0 条评论

发表评论 取消回复

微信扫一扫：分享

发表评论取消回复