首先看段代码:

1
2
3
4
5
public void print(List<String> list) {
for (int i = 0; i < list.size(); i++) {
System.out.println(list.get(i));
}
}

这段代码不仔细看,感觉没什么问题,就是普通的循环输出 list 每一个元素。

但是仔细想想其中就会有性能问题,因为 List 的实现有多种,如果传入的是个 LinkedList,那么这个代码的效率就会极低。

修改后的代码:

1
2
3
4
5
public void print(List<String> list) {
for (String string : list) {
System.out.println(string);
}
}

这个是 java 提供的语法糖,增强的 for 循环功能,我们看编译后的样子是什么:

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
public print(Ljava/util/List;)V
L0
LINENUMBER 12 L0
ALOAD 1
INVOKEINTERFACE java/util/List.iterator ()Ljava/util/Iterator;
ASTORE 3
GOTO L1
L2
FRAME FULL [com/rcx/log/man java/util/List T java/util/Iterator] []
ALOAD 3
INVOKEINTERFACE java/util/Iterator.next ()Ljava/lang/Object;
CHECKCAST java/lang/String
ASTORE 2
L3
LINENUMBER 13 L3
GETSTATIC java/lang/System.out : Ljava/io/PrintStream;
ALOAD 2
INVOKEVIRTUAL java/io/PrintStream.println (Ljava/lang/String;)V
L1
LINENUMBER 12 L1
FRAME SAME
ALOAD 3
INVOKEINTERFACE java/util/Iterator.hasNext ()Z
IFNE L2
L4
LINENUMBER 15 L4
RETURN
L5
LOCALVARIABLE this Lcom/rcx/log/man; L0 L5 0
LOCALVARIABLE list Ljava/util/List; L0 L5 1
// signature Ljava/util/List<Ljava/lang/String;>;
// declaration: java.util.List<java.lang.String>
LOCALVARIABLE string Ljava/lang/String; L3 L1 2
MAXSTACK = 2
MAXLOCALS = 4

通过 bytecode 工具看出,其实增强的 for 循环,就是转换成 iterator。

Iterator 接口

Iterator 的定义如下:

1
2
3
4
5
6
7
8
9
10
11
public interface Iterator<E> {

boolean hasNext();

E next();

default void remove() {
throw new UnsupportedOperationException("remove");
}

}

不考虑 java8 的新语法,提供了3个接口。

hasNext 判断是否还有下一个元素。next 返回下一个元素,remove 删除当前元素,并且如果删除了在删除的话会抛出异常。

ArrayList 当中的 Iterator 实现

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
public Iterator<E> iterator() {
return new Itr();
}

private class Itr implements Iterator<E> {
int cursor; // index of next element to return
int lastRet = -1; // index of last element returned; -1 if no such
int expectedModCount = modCount;

public boolean hasNext() {
return cursor != size;
}

@SuppressWarnings("unchecked")
public E next() {
checkForComodification();
int i = cursor;
if (i >= size)
throw new NoSuchElementException();
Object[] elementData = ArrayList.this.elementData;
if (i >= elementData.length)
throw new ConcurrentModificationException();
cursor = i + 1;
return (E) elementData[lastRet = i];
}

public void remove() {
if (lastRet < 0)
throw new IllegalStateException();
checkForComodification();

try {
ArrayList.this.remove(lastRet);
cursor = lastRet;
lastRet = -1;
expectedModCount = modCount;
} catch (IndexOutOfBoundsException ex) {
throw new ConcurrentModificationException();
}
}

final void checkForComodification() {
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
}
}

详细分析实现:

  1. 创建 Itr,用 ArrayList 当中的 modCount 赋值给 expectedModCount。
  2. cursor 代表当前索引的游标。
  3. lastRet 代表调用 next 返回的值的索引,如果在当前调用 remove 后,这个值会设置成 -1。当是 -1 的时候抛出异常。
  4. next,hasNext 代码比较简单,不详细分析
  5. checkForComodification 方法,在每次操作的时候都会进行检查,这个 list 的元素是否有变动,详细看下面的例子
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public static void main(String[] args) {
List<String> list = new ArrayList<String>();
list.add("a");
list.add("b");
list.add("c");
list.add("d");

for (String string : list) {
list.add("ads");
}

System.out.println(list);
}

// 这段代码抛出了异常,因为在通过 Iterator 进行对 list 迭代的时候,如果使用 list 修改了 list 的元素,那么就会抛出异常。
// 但是我们可以通过 Iterator 进行元素是删除

Exception in thread "main" java.util.ConcurrentModificationException
at java.util.ArrayList$Itr.checkForComodification(ArrayList.java:901)
at java.util.ArrayList$Itr.next(ArrayList.java:851)
at com.rcx.log.man.main(man.java:18

在看下面这段代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public static void main(String[] args) {
List<String> list = new ArrayList<String>();
list.add("a");
list.add("b");
list.add("c");
list.add("d");

Iterator<String> iterator = list.iterator();
while (iterator.hasNext()) {
if (iterator.next().equals("b")) {
iterator.remove();
}
}

System.out.println(list);
}

//输出
[a, c, d]

所以我们得出了一个结论:

在对 list 进行迭代的过程中,如果想对 list 进行操作,那么一定要通过 iterator 迭代起来实现。

那么我们在来一个例子:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public static void main(String[] args) {
List<String> list = new ArrayList<String>();
list.add("a");
list.add("b");
list.add("c");
list.add("d");

for (int i = 0; i < list.size(); i++) {
System.out.println(list.get(i));
if ("b".equals(list.get(i))) {
list.remove(i);
}
}
}

//输出
a
b
d

为什么删除了 b 之后,需要迭代的 c 居然没了,仔细分析下就会知道,当 remove 一个元素后 list 的 size 会减 1,并且是在当前元素上 remove 那么之后的元素都会前移,所以就会跳过了 c。

再来看下一个情况:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public static void main(String[] args) {
List<String> list = new ArrayList<String>();
list.add("a");
list.add("b");
list.add("c");
list.add("d");

for (int i = 0; i < list.size(); i++) {
if ("d".equals(list.get(i))) {
list.remove(i);
}
System.out.println(list.get(i));
}
}

a
b
c
Exception in thread "main" java.lang.IndexOutOfBoundsException: Index: 3, Size: 3
at java.util.ArrayList.rangeCheck(ArrayList.java:653)
at java.util.ArrayList.get(ArrayList.java:429)
at com.rcx.log.man.main(man.java:19)

结果抛出异常,仔细分析也能够明白在删除了 d 之后又获取它,肯定会数组越界。

当前上面的2个例子都可以完善,避免他们出错,然后还是使用 jdk 提供的 iterator 来做会更加完美。

LinkedList 当中的 Iterator 实现

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
89
90
91
92
public ListIterator<E> listIterator(int index) {
checkPositionIndex(index);//check 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++;
}

final void checkForComodification() {
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
}
}

详细分析:

  1. next 代表调用 next 方法需要返回的元素。
  2. nextIndex 代表 next() 方法返回的元素的索引,用于在 hasNext 方法当中做判断。
  3. lastReturned 同样是记录当前 next 的元素,可以对当前元素进行操作,remove 之类。
  4. ListItr 实现了 ListIterator,这里面会多一些方法,后面分析

分析 remove 方法:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
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++;
}

ListIterator 接口定义:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public interface ListIterator<E> extends Iterator<E> {
boolean hasNext();

E next();

boolean hasPrevious();

E previous();

int nextIndex();

int previousIndex();

void remove();

void set(E e);

void add(E e);
}

增加可以指向前一位指针,以及元素,以及后一个元素的 index,并且可以对当前元素进行重新赋值,或者在当前位置进行插入。

分析 ListItr 当中的这些实现:

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
public boolean hasPrevious() {
return nextIndex > 0;
}

public E previous() {
checkForComodification();
if (!hasPrevious())
throw new NoSuchElementException();

lastReturned = next = (next == null) ? last : next.prev;//这一步会导致,在 remove 的里面判断 next == lastReturned
nextIndex--;
return lastReturned.item;
}

public int nextIndex() {
return nextIndex;
}


public int previousIndex() {
return nextIndex - 1;
}

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

举个例子:

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
public static void main(String[] args) {
LinkedList<String> list = new LinkedList<String>();
list.addLast("0");
list.addLast("1");
list.addLast("2");
list.addLast("3");
list.addLast("a");
list.addLast("b");
list.addLast("c");
list.addLast("d");

ListIterator<String> iterator = list.listIterator();
while (iterator.hasNext()) {
if (iterator.next().equals("c")) {
iterator.previous();
iterator.previous();
iterator.previous();
iterator.remove();
System.out.println("---");
}
}
}

//输出如下
---
---
---
---
---
Exception in thread "main" java.util.NoSuchElementException
at java.util.LinkedList$ListItr.previous(LinkedList.java:905)
at com.rcx.log.man.main(man.java:25)

ArrayList 当中的 ListItr 这次不分析了。

总结:

  1. 循环尽量使用迭代器
  2. 循环当中对 list 进行修改,必须使用迭代器,如果涉及到 add set 操作可以使用 ListItr 迭代器

—EOF—