Java Iterator - Java 迭代器

Made by Mike_Zhang

---

Java主题：

---

1. Intro

Let’s first have a look at the example code of the following program:

public static void main(String[] args) {
    ArrayList<Integer> arr = new ArrayList<>();
    arr.add(1);
    arr.add(2);
    arr.add(3);

    for (int j : arr) {
        System.out.println(j);
    }
}

Output:

1
2
3

It has a classical For-Each loop in Java. But why Java knows how to iterate through the ArrayList based on for (int j : arr)?

---

Actually, Java has compiled the above loop part code into:

// ...
Iterator i = arr.iterator();
while (i.hasNext()) {
    System.out.println(i.next());
}

With the help of the Iterator class, Java can reach each element in the ArrayList, as well as know the next element of current one in the sequence.

An iterator is a soft design pattern that describe the process of scanning through a sequence of elements, once element a time, in which the element includes container, streaming from network, or a serial of computation, etc.

In Java, iterator is abstracted in java.util.Iterator interface.

---

2. Iterator Interface

There are three methods in the java.util.Iterator interface:

At the beginning, there is a reference points to the first element in the sequence.

• hasNext(): Return true if the current reference has a next element, otherwise return false.
• next(): Return the current pointing reference and update the reference to the next element.
• remove(): Remove the element that returned by the most recently called by next() method. Return exception if that element has already been removed or no element has been returned by next() method.

With first two method, we can use general loop to iterate through the iterator sequence.

For a Iterator<Integer> i

while (i.hasNext()) {
    int val = i.next();
    System.out.println(val);
}

The above code will print out the sequence of elements in the iterator i.

---

3. Iterable Interface

• Iterator contains the content of the iterator sequence to be processed, as well as some method to control the iterator. One iterator instance only supports once traversal, and there is not way to restart the iterator from the beginning.

However, multiple iteration is commonly used in program.

• Iterable Interface can help us to create more new iterator instances for multiple iteration, which describes the ability of a class to be iterated.

The Iterable interface contains only a single method:

• iterator(): Return an iterator instance of collection.

Once the method iterator() is called, a new Iterator instance will be created and returned.

---

One of the most important usage of Iterable interface is the For-Each loop in Java.

Any instance or collection of a class implementing the Iterable interface can be iterated in the For-each loop.

for (ElementType variable : collection) {
    // loopBody
}

where

• ElementType is the type of the element in the instance or collection, which is returned by next() method in the Iterator interface;
• variable is one element with the type of ElementType in the collection;
• collection is the instance or collection of the class implementing the Iterable interface.

Above code can be translated into:

Iterator<ElementType> i = collection.iterator(); // return an iterator instance of collection
    while (i.hasNext( )) {
        ElementType variable = i.next( );
        // loopBody
}

---

4. Iterator Implementation

With the help of the Iterable interface, any class implemented the Iterable interface can be iterated easily after creating instances implemented iterator interface.

However, there two different way to implement an iterator interface:

• snapshot iterator; and
• lazy iterator.

The mainly different if whether the subsequent changes in the collection will affect the iterator or not.

• snapshot iterator:

  • Initially, maintains a private copy of the primary collection of elements. All traversals are based on that copy, which will not be affected by any subsequent changes, due to the primary collection is immutable.
  • Since a copy need to be made at the beginning, this approach is slow as running in the $O(n)$ time.

• lazy iterator:

  • No copy is made. It performs a piecewise traversal when next() is called based on the current content of the collection. So the lazy iterator is fast (in $O(1)$) but will be affected by any subsequent changes in the collection.

Following are the snapshot iterator Implementations with ArrayList and LinkedPositionalList.

---

4.1 Implementation with ArrayList

Refer to the original ArrayList in previous post.

Key steps:

1. Make the ArrayList implement the Iterable<E> interface (default in Java);
2. Add a iterator() method to the ArrayList class to return an Iterator instance;
3. Add a ArrayIterator inner class to the ArrayList class to implement the Iterator interface.

Java Implementation:

public class ArrayList<E> implements List<E>, Iterable<E> { // Step 1
    
    // ... original ArrayList in previous post

    // Step 3
    // Nested ArrayIterator Class
    // Lazy implementation of Iterator of List<E>
    private class ArrayIterator implements Iterator<E> {
        private int current = 0;
        private boolean isMoved = false;

        public boolean hasNext() {
            return current < size;
        }
        public E next() throws NoSuchElementException {
            if (!hasNext()) {
                throw new NoSuchElementException();
            }

            return data[current++];
        }
        public void remove() throws IllegalStateException {
            if (isMoved) {
                throw new IllegalStateException();
            }
            ArrayList.this.remove(--current);
            isMoved = true;
        }
    }

    // Step 2
    // Override the `iterator()` method to return an `ArrayIterator` instance
    public Iterator<E> iterator() {
        return new ArrayIterator();
    }

    // ... original ArrayList in previous post
}

Test:

public static void main(String[] args) {
    ArrayList<Integer> arr = new ArrayList<> ();
    arr.add(0, 1);
    arr.add(1, 2);
    arr.add(2, 3);

    // Method 1: traversal the elements with intuitive loop
    System.out.println("Method 1:");
    for (int i : arr) {
        System.out.println(i);
    }

    // Method 2: In fact, the same as Method 1, using iterator() to traverse the elements
    System.out.println("Method 2:");
    Iterator<Integer> iter = arr.iterator();
    while (iter.hasNext()) {
        System.out.println(iter.next());
    }
}

Output:

Method 1:
1
2
3
Method 2:
1
2
3

---

4.2 Implementation with LinkedPositionalList

Refer to the original LinkedPositionalList in previous post.

Due to the LinkedPositionalList uses Position ADT, its iterator can be implemented in two different ways: iterate the elements or iterate the positions.

We have both of them:

We will define the iterator() method return the iterator of element in the LinkedPositionalList. In addition, a new positions() method will be added to return the iterable instance of Position in the LinkedPositionalList.

Key steps:

1. Make the LinkedPositionalList implement the Iterable<E> interface;
2. Add a PositionIterator inner class to the LinkedPositionalList class to implement the Iterator interface, in order to realize all iterator functions on the position of the elements;
3. To let our positions() method return a Iterable instance on position, we need to add a PositionIterable inner class implementing the Iterable interface, in which we add a iterator() method to return a PositionIterator instance. Afterwards, the positions() method will return a PositionIterable instance. (What a perfect encapsulation!!! Why? The most outer class LinkedPositionalList implements the Iterable interface but returning the element, so we have a new Iterable class to return position, so the PositionIterable comes!);
4. Add a ElementIterator inner class to the LinkedPositionalList class to implement the Iterator interface to realize all iterator functions on the element of the sequence, which only need to adapt from the PositionIterator class by returning the element of the position.
5. Add a iterate() method in the LinkedPositionalList class to return an ElementIterator instance for the iterator of elements.

Java Implementation:

public class LinkedPositionalList<E> implements PositionList<E>, Iterable<E> { // Step 1

    // ... original LinkedPositionalList in previous post

    // Step 2
    // Lazy iterator implementation for positions
    private class PositionIterator implements Iterator<Position<E>> {
        private Position<E> current = first();
        private Position<E> oneMoved = null;
        public boolean hasNext() {
            return current != null;
        }
        public Position<E> next() throws NoSuchElementException {
            if (current == null) {
                throw new NoSuchElementException();
            }
            oneMoved = current;
            current = after(current);
            return oneMoved;
        }
        public void remove() throws IllegalStateException {
            if (oneMoved == null) {
                throw new IllegalStateException();
            }
            LinkedPositionalList.this.remove(oneMoved);
            oneMoved = null;
            throw new UnsupportedOperationException();
        }
    }

    // Step 3
    // constructs and returns a new PositionIterator object
    // each time its iterator( ) method is called
    public class PositionIterable implements Iterable<Position<E>> {
        public Iterator<Position<E>> iterator() {
            return new PositionIterator();
        }
    }

    // Step 3
    // returns an Iterable object that can be used to iterate over the positions of the list
    public Iterable<Position<E>> positions() {
        return new PositionIterable();
    }

    // Step 4
    private class ElementIterator implements Iterator<E> {
        private Iterator<Position<E>> posIterator = new PositionIterator();
        public boolean hasNext() {
            return posIterator.hasNext();
        }
        public E next() throws NoSuchElementException {
            return posIterator.next().getElement();
        }
        public void remove() throws IllegalStateException {
            posIterator.remove();
        }
    }

    // Step 5
    public Iterator<E> iterator() {
        return new ElementIterator();
    }

    // ... original LinkedPositionalList in previous post

}

Test:

public static void main(String[] args) {
    LinkedPositionalList<Integer> list = new LinkedPositionalList<Integer>();
    Position<Integer> p1 = list.addFirst(1);
    Position<Integer> p2 = list.addAfter(p1, 2);
    Position<Integer> p3 = list.addAfter(p2, 3);
    
    // Method 1: traversal the elements with intuitive loop
    System.out.println("Method 1:");
    for (Integer i : list) {
        System.out.println(i);
    }

    // Method 2: In fact, the same as Method 1, using iterator() to traverse the elements
    System.out.println("Method 2:");
    Iterator<Integer> it = list.iterator();
    while (it.hasNext()) {
        System.out.println(it.next());
    }

    // Method 3: traversal the positions with intuitive loop
    System.out.println("Method 3:");
    for (Position<Integer> p : list.positions()) {
        System.out.println(p.getElement());
    }

    // Method 4: In fact, the same as Method 3, using positions().iterator() to traverse the positions
    System.out.println("Method 4:");
    Iterator<Position<Integer>> pt = list.positions().iterator();
    while (pt.hasNext()) {
        System.out.println(pt.next());
    }
}

Output:

Method 1:
1
2
3
Method 2:
1
2
3
Method 3:
LinkedPositionalList$Node@5a39699c
LinkedPositionalList$Node@3cb5cdba
LinkedPositionalList$Node@56cbfb61
Method 4:
LinkedPositionalList$Node@5a39699c
LinkedPositionalList$Node@3cb5cdba
LinkedPositionalList$Node@56cbfb61

---

References

Goodrich, M., Tamassia, R., & O’reilly, A. (2014). Data Structures and Algorithms in Java, 6th Edition. John Wiley & Sons.

---

写在最后

Java相关的基础知识十分重要，会继续学习，继续更新.
最后，希望大家一起交流，分享，指出问题，谢谢！

---

原创文章，转载请标明出处
Made by Mike_Zhang

感谢你的支持