The cause of

Today, brush force button of the day, there is an iterator related topic (284). Let me can not help thinking, Java often used iterator I have not read the source code, so through this article to learn to summarize the iterator Java implementation.

role

Understand iterators from the top down, thinking about what they do and what they mean first, don’t start with the source code.

When we’re using a List collection, and we want to iterate over elements, what do we do

A method to traverse a List

For (int I = 0; i < list.size(); i++) { System.out.println(list.get(i)); } //for-each method for (int a: list) {system.out.println (a); }Copy the code

Usually when we write algorithms, we use the first one a lot, because there are complicated judgments and subscripts and things like that; The second type of writing business is more common because foreach is more concise. Of course, after Jdk8 there is lambda notation, WHICH I will not write, because it is not the focus of this article.

Iterators are written in a way that I believe most people don’t like to write, because I don’t like to write either.

Iterator iterator = list.iterator();
while (iterator.hasNext()) {
    System.out.println(iterator.next());
}
Copy the code

In comparison, it’s cumbersome, and even the IDE will recommend that you rewrite it as foreach.

However, the general business may have the need to filter, add and delete elements, that is, the need to take a non-iterator approach is not desirable.

Add or delete lists during traversal

For the first subscript class, what happens if we delete an element, let’s do an example

List<Integer> list = new ArrayList<>(); for(int i=1; i<=10; i++){ list.add(i); } for (int i = 0; i < list.size(); i++) { list.remove(i); } System.out.println(list); //[2, 4, 6, 8, 10]Copy the code

Not quite what we expected, because we thought we would delete all of them, but only the odd numbers were deleted.

Because of the nature of linear tables, the next element moves forward, and I is already at the next element, but the for loop still uses I ++, so some elements are not deleted, and the IDE will also warn you.

The solution is to create an I — after the deletion, but this is ugly, and business code is best not to confuse logic by adding strange variables.

For Foreach, it is forbidden to change the length of the collection, delete or add the collection during traversal.

So to gracefully delete elements, you need to use iterators

while (iterator.hasNext()) {
    iterator.next();
    iterator.remove();
}
Copy the code

Just remove.

The source code parsing

Iterator

Let’s start with the Iterator interface. All iterators we use need to implement this interface, which has only a few common methods

Public interface Iterator<E>{public interface Iterator<E>{Boolean hasNext(); // Iterate over the next element E next(); // Overflow this element default void remove(); // the new jdk8 method, similar to the stream foreach implementation, operates on the remaining elements of the collection default void forEachRemaining(Consumer<? super E> action) }Copy the code

Very simple, allowing us to easily implement a simple iterator ourselves.

So let’s take a look at the implementation class of the iterator in the ArrayList JDK source code.

Itr

An inner class of ArrayList

private class Itr implements Iterator<E> { int cursor; int lastRet = -1; int expectedModCount = modCount; public boolean hasNext() { return cursor ! = size; } 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(); try { ArrayList.this.remove(lastRet); cursor = lastRet; lastRet = -1; expectedModCount = modCount; } catch (IndexOutOfBoundsException ex) { throw new ConcurrentModificationException(); }}}Copy the code

So basically, we have two Pointers called cursor, lastRet.

LastRet is on the left of cursor. Each time next(), the two Pointers move one space to the right. When remove is called, it is still the remove() method of the list that is called, but does an unconscious operation that sets the lastRet pointer =-1. Causes an exception to be thrown when removing again.

In summary, the iterator remove is used to remove elements from the bottom of the array so that the user is not aware of the changes to the position of the bottom of the array.

ListIterator and ListItr

In fact, I usually use a normal iterator, but today I looked at the source code and realized that ArrayList also has a ListIterator.

 private class ListItr extends Itr implements ListIterator<E> {
 
 }
Copy the code

The ListIterator interface implements Iterator’s interface, in contrast to adding many more diverse interfaces, such as Add, set, previous, etc. The general idea is not to go into detail.

可迭代

Iterable and Iterator are similar, so don’t confuse them.

The Iterator interface is an Iterable interface that is Iterable. The modified objects are different

It is the top-level interface for all Collection classes, such as Collection, which inherits the Iterable interface. Let’s look at the methods of this interface

Public interface Iterable<T> {// Familiar name. Iterator<T> Iterator (); }Copy the code

Each collection is required to implement the iterator() method, which generates iterators.

The for-each enhancement we mentioned above is actually implemented at the bottom through iterators. That is, collections that implement the Iterable interface can be traversed using foreach.

The subtotal

Iterator<Integer> iterator = list.iterator(); iterator <Integer> iterator = list.iterator(); // The Iterator is an Itr inner class that implements the Iterator interfaceCopy the code

\