迭代器
在java中主要有两种迭代器，Iterator和ListIterator。这两个都是接口。先来看一下这两个接口有什么区别
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
|
public interface Iterator<E> {
boolean hasNext();
E next();
default void remove() {
throw new UnsupportedOperationException("remove");
}
default void forEachRemaining(Consumer<? super E> action) {
Objects.requireNonNull(action);
while (hasNext())
action.accept(next());
}
}
|
Iterator主要有四个方法。判断有没有下一个元素、获取下一个元素，删除元素和forEachRemaining方法。
再来看一下ListIterator
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
|
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);
}
|
我们可以看到他是继承了Iterator。除了上面的两个方法还多了好几个方法。判断是否有上一个元素，获取上一个元素的值，获取上一个元素的索引，获取上一个元素的索引。除了移除还有添加和更新的方法。
他们在不同的类里面都有自己的实现，之前看ArrayList，HashMap的时候把这一块给跳过了，现在来看一下他们是如何实现的。
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
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
|
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;
Itr() {}
/**
* 判断有没有下一个元素，将下一个元素的索引与元素长度进行对比
*/
public boolean hasNext() {
return cursor != size;
}
@SuppressWarnings("unchecked")
public E next() {
checkForComodification();
/** 将下一个的索引赋给i，如果下一个索引比集合长度还大，则抛出异常 **/
int i = cursor;
if (i >= size)
throw new NoSuchElementException();
Object[] elementData = ArrayList.this.elementData;
if (i >= elementData.length)
/** 这里又进行了一次判断，判断索引值与元素长度的关系 **/
throw new ConcurrentModificationException();
/**然后将下一个的索引进行加一**/
cursor = i + 1;
/**返回这个位置上的元素，并且将lastRet赋值为i **/
return (E) elementData[lastRet = i];
}
/**这个方法是移除刚刚获取的那个元素**/
public void remove() {
/**如果lastRet小于0，则表示刚刚没有获取过元素**/
if (lastRet < 0)
throw new IllegalStateException();
checkForComodification();
try {
/**调用了ArrayList的根据索引删除元素方法**/
ArrayList.this.remove(lastRet);
/**将下一个元素索引赋值为上一个索引，并且将最后返回的索引置为-1**/
cursor = lastRet;
lastRet = -1;
/**因为进行了删除，所以modCount进行了修改，这里要再次赋值到expectedModCount上**/
expectedModCount = modCount;
} catch (IndexOutOfBoundsException ex) {
throw new ConcurrentModificationException();
}
}
/**
* 检查
* 在开始的时候将 expectedModCount初始化为modCount的值
* 如果在初始化后集合进行了 添加或删除元素的操作 则modCount会改变
* 在这里进行判断，有没有进行修改的操作。
* 例：[1,2,3,4,5]。从开始用迭代器，判断了第一位有值(现在是1)，在调用next()方法之前进行了删除，把1删除了。
* 这时再调用next()会返回2。这是不对的。这个判断就是为了这种情况的。
*/
final void checkForComodification() {
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
}
}
|
从上面的代码可以看出
- 对于移除元素来说，只能移除刚刚获取的那一个元素。如果刚刚没获取元素获取则抛出异常，如果要删除获取的前两个元素也不可以。
然后再来看一下实现的ListIterator接口
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
|
private class ListItr extends Itr implements ListIterator<E> {
/**它的构造方法必须传入一个参数**/
ListItr(int index) {
super();
cursor = index;
}
/**判断有没有上一个元素，如果下一个返回元素不是第一个元素则表示有上一个元素**/
public boolean hasPrevious() {
return cursor != 0;
}
public int nextIndex() {
return cursor;
}
public int previousIndex() {
return cursor - 1;
}
@SuppressWarnings("unchecked")
public E previous() {
checkForComodification();
int i = cursor - 1;
if (i < 0)
throw new NoSuchElementException();
Object[] elementData = ArrayList.this.elementData;
if (i >= elementData.length)
throw new ConcurrentModificationException();
cursor = i;
return (E) elementData[lastRet = i];
}
/**调用了ArrayList的set方法，传入的坐标是刚刚返回值的坐标**/
public void set(E e) {
if (lastRet < 0)
throw new IllegalStateException();
checkForComodification();
try {
ArrayList.this.set(lastRet, e);
} catch (IndexOutOfBoundsException ex) {
throw new ConcurrentModificationException();
}
}
/**添加一个元素，因为多了一个元素，所以下一个元素的索引要加1，并且刚刚没有返回元素，lastRet置为-1**/
public void add(E e) {
checkForComodification();
try {
int i = cursor;
ArrayList.this.add(i, e);
cursor = i + 1;
lastRet = -1;
expectedModCount = modCount;
} catch (IndexOutOfBoundsException ex) {
throw new ConcurrentModificationException();
}
}
}
|
LinkedList
也是将这两个接口都实现了，但是从代码里可以看出实现的Iterator最终还是调用了ListIterator方法
不过他后面的调用next、hasNext方法是调用是是否有上一个值。
1
2
3
4
5
6
7
8
9
10
11
12
13
|
private class DescendingIterator implements Iterator<E> {
// 这个类是在下面声明的 实现了ListIterator的类
private final ListItr itr = new ListItr(size());
public boolean hasNext() {
return itr.hasPrevious();
}
public E next() {
return itr.previous();
}
public void remove() {
itr.remove();
}
}
|
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
|
private class ListItr implements ListIterator<E> {
private Node<E> lastReturned;
private Node<E> next;
private int nextIndex;
private int expectedModCount = modCount;
/**
* 上面调用方法时传入了 size()方法的返回值相当于传入了size变量
* 如果传入的值等于size则 next赋值为null 不然置为该位置上的元素
* 然后让 nextIndex置为传入的值
**/
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();
}
}
|
总结
从这里可以看出之前定义的modCount的作用，这个变量在迭代器中作为一个判断。
forEachRemaining方法暂时还没弄明白他的作用，而且它的作用应该并不是为了在迭代器中使用，应该有其他方面的作用，这个就放到后面再来看。