Java集合框架——Iterator接口

发表于

Iterator接口

Iterator是一个接口，它是集合的迭代器。集合可以通过Iterator去遍历集合中的元素。其定义如下。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public interface Iterator<E> {
  	// 判断集合中是否存在下一个元素，如果有，返回true
    boolean hasNext();
	// 返回集合里的下一个元素
    E next();
	// 删除集合里上一次next方法返回的元素
    default void remove() {
        throw new UnsupportedOperationException("remove");
    }
    default void forEachRemaining(Consumer<? super E> action) {
        Objects.requireNonNull(action);
        while (hasNext())
            action.accept(next());
    }
}

下面通过ArrayList的Iterator和HashMap的Iterator来分析一下Iterator接口。

ArrayList的Iterator的源码实现

通过分析ArrayList的源码可以知道，在ArrayList内部定义了一个内部类Itr，该内部类实现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
private class Itr implements Iterator<E> {
        int cursor; // 表示下一个元素的索引
        int lastRet; // 表示上一个元素的索引
        int expectedModCount;
        private Itr() {
            this.lastRet = -1;
            this.expectedModCount = ArrayList.this.modCount;
        }
        public boolean hasNext() {
            return this.cursor != ArrayList.this.size;
        }
        public E next() {
            this.checkForComodification();
            int var1 = this.cursor;
            if(var1 >= ArrayList.this.size) {
                throw new NoSuchElementException();
            } else {
                Object[] var2 = ArrayList.this.elementData;
                if(var1 >= var2.length) {
                    throw new ConcurrentModificationException();
                } else {
                    this.cursor = var1 + 1;
                    return var2[this.lastRet = var1];
                }
            }
        }
        public void remove() {
            if(this.lastRet < 0) {
                throw new IllegalStateException();
            } else {
                this.checkForComodification();
                try {
                    ArrayList.this.remove(this.lastRet);
                    this.cursor = this.lastRet;
                    this.lastRet = -1;
                    this.expectedModCount = ArrayList.this.modCount;
                } catch (IndexOutOfBoundsException var2) {
                    throw new ConcurrentModificationException();
                }
            }
        }
        public void forEachRemaining(Consumer<? super E> var1) {
            Objects.requireNonNull(var1);
            int var2 = ArrayList.this.size;
            int var3 = this.cursor;
            if(var3 < var2) {
                Object[] var4 = ArrayList.this.elementData;
                if(var3 >= var4.length) {
                    throw new ConcurrentModificationException();
                } else {
                    while(var3 != var2 && ArrayList.this.modCount == this.expectedModCount) {
                        var1.accept(var4[var3++]);
                    }
                    this.cursor = var3;
                    this.lastRet = var3 - 1;
                    this.checkForComodification();
                }
            }
        }
        final void checkForComodification() {
            if(ArrayList.this.modCount != this.expectedModCount) {
                throw new ConcurrentModificationException();
            }
        }
    }

对于ArrayList的迭代方法，主要是判断索引的值和数组的大小进行比较，看看还没有数据可以遍历了，然后再依次获取数组中的值，而已，主要抓住各个集合的底层实现方式即可进行迭代。

HashMap的Iterator的源码实现

在HashMap中，也有一个类实现了Iterator接口，只不过是个抽象类，HashIterator，我们来看看它的实现方式。

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
private abstract class HashIterator<E> implements Iterator<E> {
        HashMapEntry<K,V> next;        // 表示下一个entry的节点
        int expectedModCount;   // 用于判断修改状态，用于集合的快速失败机制
        int index;              // 表示当前索引
        HashMapEntry<K,V> current;     // 表示当前所索引的节点entry
        HashIterator() {
            expectedModCount = modCount;
            if (size > 0) { // advance to first entry
                HashMapEntry[] t = table;
                while (index < t.length && (next = t[index++]) == null)
                    ;
            }
        }
        public final boolean hasNext() {
            return next != null;
        }
        final Entry<K,V> nextEntry() {
            if (modCount != expectedModCount)
                throw new ConcurrentModificationException();
            HashMapEntry<K,V> e = next;
            if (e == null)
                throw new NoSuchElementException();
 			// 一个Entry就是一个单向链表
            // 若该Entry的下一个节点不为空，就将next指向下一个节点;
            // 否则，将next指向下一个链表(也是下一个Entry)的不为null的节点。
            if ((next = e.next) == null) {
                HashMapEntry[] t = table;
                while (index < t.length && (next = t[index++]) == null)
                    ;
            }
            current = e;
            return e;
        }
        public void remove() {
            if (current == null)
                throw new IllegalStateException();
            if (modCount != expectedModCount)
                throw new ConcurrentModificationException();
            Object k = current.key;
            current = null;
            HashMap.this.removeEntryForKey(k);
            expectedModCount = modCount;
        }
    }

以上便是HashMap的Iterator的源码实现。

ListIterator接口

ListIterator是一个功能更加强大的迭代器， 它继承于Iterator接口，只能用于各种List类型的访问。可以通过调用listIterator()方法产生一个指向List开始处的ListIterator，还可以调用listIterator(n)方法创建一个一开始就指向列表索引为n的元素处的ListIterator。以下是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 var1);
    void add(E var1);
}

由以上定义可以推出ListIterator可以双向遍历，产生相对于迭代器在列表中指向的当前位置的前一个和后一个元素的索引，可以用set()方法来替换它访问过的最后一个元素，可以使用add()方法在next()方法返回的元素之前或previous()方法返回的元素之后插入一个元素。

下面以ArrayList的ListItr为例分析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
59
60
61
62
private class ListItr extends ArrayList<E>.Itr implements ListIterator<E> {
        ListItr(int var2) {
            super(null);
            this.cursor = var2;
        }
        public boolean hasPrevious() {
            return this.cursor != 0;
        }
        public int nextIndex() {
            return this.cursor;
        }
        public int previousIndex() {
            return this.cursor - 1;
        }
        public E previous() {
            this.checkForComodification();
            int var1 = this.cursor - 1;
            if(var1 < 0) {
                throw new NoSuchElementException();
            } else {
                Object[] var2 = ArrayList.this.elementData;
                if(var1 >= var2.length) {
                    throw new ConcurrentModificationException();
                } else {
                    this.cursor = var1;
                    return var2[this.lastRet = var1];
                }
            }
        }
        public void set(E var1) {
            if(this.lastRet < 0) {
                throw new IllegalStateException();
            } else {
                this.checkForComodification();
                try {
                    ArrayList.this.set(this.lastRet, var1);
                } catch (IndexOutOfBoundsException var3) {
                    throw new ConcurrentModificationException();
                }
            }
        }
        public void add(E var1) {
            this.checkForComodification();
            try {
                int var2 = this.cursor;
                ArrayList.this.add(var2, var1);
                this.cursor = var2 + 1;
                this.lastRet = -1;
                this.expectedModCount = ArrayList.this.modCount;
            } catch (IndexOutOfBoundsException var3) {
                throw new ConcurrentModificationException();
            }
        }
    }

ListItr也是ArrayList的内部类，其继承于ArrayList的另一个内部类Itr并实现了ListIterator接口。可以看到ListItr是对Itr的扩展，把一个单向遍历数组扩展为双向遍历数组，并相应增加了双向遍历数组的功能。

Iterator和ListIterator的区别

Iterator和ListIterator主要区别在以下方面：

  • ListIterator有add()方法，可以向List中添加对象，而Iterator不能。
  • ListIterator和Iterator都有hasNext()和next()方法，可以实现顺序向后遍历，但是ListIterator有hasPrevious()和previous()方法，可以实现顺序向前遍历，Iterator则不可以。
  • ListIterator可以定位当前的索引位置，nextIndex()和previousIndex()可以实现，Iterator没有此功能。
  • 都可以删除对象，但是ListIterator可以实现对象的修改，set()方法可以实现，Iterator仅能遍历，不能修改。

总结

数据结构对程序设计有着深远的影响，在面向过程的C语言中，数据结构用struct来描述，在面向对象的编程中，数据结构是用类来描述的，并且包含有对该数据结构操作的方法。

在Java语言中，Java语言的设计者对常用的数据结构和算法做了一些规范（接口）和实现（具体实现接口的类）。所有抽象出来的数据结构和操作（算法）统称为Java集合框架。

Java程序员在具体应用时，不必考虑数据结构和算法实现细节，只需要用这些类创建出来一些对象，然后直接应用就可以了，这样就大大提高了编程效率。