給jdk寫注釋系列之jdk1.6容器(3)-Iterator設計模式
本系列：
給jdk寫注釋系列之jdk1.6容器(1)-ArrayList源碼解析
給jdk寫注釋系列之jdk1.6容器(2)-LinkedList源碼解析
前面講了兩種List，一種基于數組實現的ArrayList，一種基于鏈表實現的LinkedList，這兩種list是我們工作中最常用到的List容器。當然數組和鏈表也是兩種常見的基本數據結構，其他基本數據結構還有堆棧、隊列、樹等，對java容器的學習，也可以看做是對數據結構的學習和使用。
在ArrayList和LinkedList的分析中，都沒有對容器遍歷進行分析，前面說過迭代器相對獨立和復雜，而且它又是一種非常經典的 設計模式 （說經典不過使用場景也就這一個…），這里開始對Iterator進行分析。
細心的童鞋會看到這邊blog的標題叫做”設計模式”而不是前面的”源碼解析”，是的這里會從設計模式層面出發，更偏重于怎么更好的進行與改善代碼的設計。
1.統一接口
先想一個問題，現在有ArrayList和LinkedList兩種容器，我們怎么實現容器的可替換性呢？什么叫做可替換性，就是我底層的容器實現可以隨意改變，而對用戶的使用不產生任何影響，說到這里應該都明白了就是要統一接口，用戶只需要面向接口編程對不對（這里以及下面說的用戶都是指開發者）。來看看ArrayList和LinkedList是不是這樣做的（假裝你還不知道的情況下，一起看吧^_^）？
ArrayList的定義：
public class ArrayList<E> extends AbstractList<E>
implements List<E>, RandomAccess, Cloneable, java.io.Serializable LinkedList的定義：
public class LinkedList<E>
extends AbstractSequentialList<E>
implements List<E>, Deque<E>, Cloneable, java.io.Serializable從定義上可以看到ArrayList和LinkedList都實現了List接口，ok看下List接口的定義：
public interface List<E> extends Collection<E> {
int size();
boolean isEmpty();
boolean contains(Object o);
Iterator<E> iterator();
Object[] toArray();
<T> T[] toArray(T[] a);
boolean add(E e);
boolean remove(Object o);
boolean containsAll(Collection<?> c);
boolean addAll(Collection<? extends E> c);
boolean addAll( int index, Collection<? extends E> c);
boolean removeAll(Collection<?> c);
boolean retainAll(Collection<?> c);
void clear();
boolean equals(Object o);
int hashCode();
E get( int index);
E set( int index, E element);
void add( int index, E element);
E remove( int index);
int indexOf(Object o);
int lastIndexOf(Object o);
ListIterator<E> listIterator();
ListIterator<E> listIterator( int index);
List<E> subList( int fromIndex, int toIndex);
} 可以看到List中對容器的各種操作add、remove、set、get、size等進行了統一定義，同時List實現了Collection接口，繼續看下Collection接口的定義（先不關心Iterator）：
public interface Collection<E> extends Iterable<E> {
int size();
boolean isEmpty();
boolean contains(Object o);
Iterator<E> iterator();
Object[] toArray();
<T> T[] toArray(T[] a);
boolean add(E e);
boolean remove(Object o);
boolean containsAll(Collection<?> c);
boolean addAll(Collection<? extends E> c);
boolean removeAll(Collection<?> c);
boolean retainAll(Collection<?> c);
void clear();
boolean equals(Object o);
int hashCode();
}<span style="font-weight: normal;"> </span> 有了這兩個接口，對于ArrayList和LinkeList的操作是不是就可以這么寫了呢？
Collection<String> collection = new ArrayList<String>();
collection.add("hello");
collection.add("java");
collection.remove("hello"); 對于ArrayList的實現不滿意，ok換成LinkedList實現，
Collection<String> collection = new LinkedList<String>();
collection.add("hello");
collection.add("java");
collection.remove("hello"); 對于用戶來說，add、remove等操作是沒有任何影響的，好了，到這里了解了統一接口，面向接口編程的好處，接下來在思考另外一個問題，怎么給容器提供一種遍歷方式。
2.Iterator設計思想
你可能會認為不就是遍歷嘛，很好提供啊，ArrayList就用數組下標進行遍歷，LinkedList就用指針next進行遍歷，仔細想一下真的這么簡單嘛？結合上一個問題，如果底層的容器實現變化了，用戶的使用是不是也需要根據具體實現的數據結構來改變遍歷方式呢？顯然這樣是不科學的嗎，這么簡單我講上面的統一接口干嘛，對不對。。。
是的，需要統一一種遍歷方式，提供一個統計遍歷接口，而具體實現需要具體的容器自己根據自身數據結構特點來完成，而對于用戶就只有一個接口而已，萬年不變。于是就有了Iterator，接下來看下Iterator的實現吧。。。
先回過頭去看Collection的定義，發現Collection 實現了一個Iterable 接口（早就發現了好嘛？），來看下的Iterable的定義，
/** Implementing this interface allows an object to be the target of
* the "foreach" statement.
* @since 1.5
*/
public interface Iterable<T> {
/**
* Returns an iterator over a set of elements of type T.
*
* @return an Iterator.
*/
Iterator<T> iterator();
}英文注釋說，實現iterable接口的類可以使用“foreach”操作，然后并要求實現Iterator<T> iterator()方法，該方法返回一個Iterator接口對象，來看下Iterator接口，
public interface Iterator<E> {
// 是否還有元素
boolean hasNext();
// 下一個元素
E next();
// 將迭代器返回的元素刪除
void remove();
} Iterator接口一共有三個方法，通過這三個方法就可以實現通用遍歷了，ok，我們來試一下。
Collection<String> collection = new ArrayList<String>();
collection.add("hello");
collection.add("java");
Iterator<String> iterator = collection.iterator();
while (iterator.hasNext()) {
System. out.println(iterator.next());
} 用戶再也不用關心容器的底層實現了，不管你是數組還是鏈表還是其他什么，只需要用Iterator就可以進行遍歷了。
到這里Iterator的設計原則和思路實際上已經講完了，我們來整理下Iterator模式的幾個角色：
1.迭代器Iterator接口。
2.迭代器Iterator的實現類，要求重寫hasNext()，next()，remove()三個方法 。
3.容器統一接口，要求有一個返回Iterator接口的方法。
4.容器實現類，實現一個返回Iterator接口的方法。
3.自己實現容器的Iterator遍歷
如果讓我們自己來實現Iterator模式，應該怎么來實現呢，試一下。
Iterator接口：
public interface MyIterator {
Object next();
boolean hasNext();
} 容器統一接口：
public interface MyCollection {
void add(Object o);
int size();
MyIterator iterator();
} 容器實現類和Iterator實現類（Iterator實現類為容器內部類）：
public class MyArrayList implements MyCollection {
private Object[] data ;
private int size;
public MyArrayList() {
data = new Object[10];
}
public void add(Object o) {
if (size == data. length) {
Object[] newData = new Object[data .length * 2];
System. arraycopy(data, 0, newData, 0, data.length );
data = newData;
}
data[size ] = o;
size++;
}
public int size() {
return size ;
}
@Override
public MyIterator iterator() {
return new Itr();
}
private class Itr implements MyIterator {
private int index = 0;
@Override
public boolean hasNext() {
if (index >= size) {
return false;
} else {
return true;
}
}
@Override
public Object next() {
Object o = data[index ];
index++;
return o;
}
}
} 應用一下：
public class Test {
public static void main(String[] args) {
MyCollection c = new MyArrayList();
c.add( "t");
c.add( "s");
c.add( "t");
c.add( "d");
System. out.println(c.size());
MyIterator itr = c.iterator();
while (itr.hasNext()) {
System. out.println(itr.next());
}
}
} 4 t s t d
沒問題，很容易就實現了對不對，當然這里只是簡單模擬，沒有過多的追求效率和優雅的設計。
4.ArrayList的Iterator實現
下面來看一看ArrayList和LinkedList對Iterator接口的實現吧，ArrayList的Iterator實現封裝在AbstractList中，看一下它的實現：
public Iterator<E> iterator() {
return new Itr();
}<span style="font-weight: normal;"> </span> 和自己實現的一樣，采用內部類實現 Iterator接口。
private class Itr implements Iterator<E> {
// 將要next返回元素的索引
int cursor = 0;
// 當前返回的元素的索引，初始值-1
int lastRet = -1;
/**
* The modCount value that the iterator believes that the backing
* List should have. If this expectation is violated, the iterator
* has detected concurrent modification.
*/
int expectedModCount = modCount;
public boolean hasNext() {
// 由于cursor是將要返回元素的索引，也就是下一個元素的索引，和size比較是否相等，也就是判斷是否已經next到最后一個元素
return cursor != size();
}
public E next() {
checkForComodification();
try {
// 根據下一個元素索引取出對應元素
E next = get( cursor);
// 更新lastRet為當前元素的索引，cursor加1
lastRet = cursor ++;
// 返回元素
return next;
} catch (IndexOutOfBoundsException e) {
checkForComodification();
throw new NoSuchElementException();
}
}
public void remove() {
// remove前必須先next一下，先取得當前元素
if (lastRet == -1)
throw new IllegalStateException();
checkForComodification();
try {
AbstractList. this.remove(lastRet );
// 確保lastRet比cursor小、理論上永遠lastRet比cursor小1
if (lastRet < cursor)
// 由于刪除了一個元素cursor回退1
cursor--;
// 重置為-1
lastRet = -1;
expectedModCount = modCount ;
} catch (IndexOutOfBoundsException e) {
throw new ConcurrentModificationException();
}
}
final void checkForComodification() {
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
}
} ArrayList的Iterator實現起來和我們自己實現的大同小異，很好理解。
有一點需要指出的是這里的checkForComodification 檢查，之前ArrayList中留了個懸念，modCount這個變量到底是做什么的，這里簡單解釋一下：迭代器Iterator允許在容器遍歷的時候對元素進行刪除，但是有一點問題那就是當多線程操作容器的時候，在用Iterator對容器遍歷的同時，其他線程可能已經改變了該容器的內容（add、remove等操作），所以每次對容器內容的更改操作（add、remove等）都會對modCount+1，這樣相當于樂觀鎖的版本號+1，當在Iterator遍歷中remove時，檢查到modCount發生了變化，則馬上拋出異常ConcurrentModificationException，這就是Java容器中的 “fail-fast”機制 。
5.LinkedList的Iterator實現
LinkedList的Iterator實現定義在AbstracSequentialtList中，實現在AbstractList中，看一下：
AbstracSequentialtList的定義：
public Iterator<E> iterator() {
return listIterator();
} AbstractList的實現：
public ListIterator<E> listIterator() {
return listIterator(0);
}
public ListIterator<E> listIterator(final int index) {
if (index<0 || index>size())
throw new IndexOutOfBoundsException( "Index: "+index);
return new ListItr(index);
} 看一下ListItr實現：
private class ListItr implements ListIterator<E> {
// 最后一次返回的節點，默認位header節點
private Entry<E> lastReturned = header;
// 將要返回的節點
private Entry<E> next ;
// 將要返回的節點index索引
private int nextIndex;
private int expectedModCount = modCount;
ListItr( int index) {
// 索引越界檢查
if (index < 0 || index > size)
throw new IndexOutOfBoundsException( "Index: "+index+
", Size: "+size );
// 簡單二分，判斷遍歷的方向
if (index < (size >> 1)) {
// 取得index位置對應的節點
next = header .next;
for (nextIndex =0; nextIndex<index; nextIndex++)
next = next .next;
} else {
next = header ;
for (nextIndex =size; nextIndex>index; nextIndex --)
next = next .previous;
}
}
public boolean hasNext() {
// 根據下一個節點index是否等于size，判斷是否有下一個節點
return nextIndex != size;
}
public E next() {
checkForComodification();
// 遍歷完成
if (nextIndex == size)
throw new NoSuchElementException();
// 賦值最近一次返回的節點
lastReturned = next ;
// 賦值下一次要返回的節點（next后移）
next = next .next;
// 將要返回的節點index索引+1
nextIndex++;
return lastReturned .element;
}
public boolean hasPrevious() {
return nextIndex != 0;
}
// 返回上一個節點（雙向循環鏈表嘛、可以兩個方向遍歷）
public E previous() {
if (nextIndex == 0)
throw new NoSuchElementException();
lastReturned = next = next. previous;
nextIndex--;
checkForComodification();
return lastReturned .element;
}
public int nextIndex() {
return nextIndex ;
}
public int previousIndex() {
return nextIndex -1;
}
public void remove() {
checkForComodification();
// 取出當前返回節點的下一個節點
Entry<E> lastNext = lastReturned.next ;
try {
LinkedList. this.remove(lastReturned );
} catch (NoSuchElementException e) {
throw new IllegalStateException();
}
// 確認下次要返回的節點不是當前節點，如果是則修正
if (next ==lastReturned)
next = lastNext;
else
// 由于刪除了一個節點，下次要返回的節點索引-1
nextIndex--;
// 重置lastReturned為header節點
lastReturned = header ;
expectedModCount++;
}
public void set(E e) {
if (lastReturned == header)
throw new IllegalStateException();
checkForComodification();
lastReturned.element = e;
}
public void add(E e) {
checkForComodification();
lastReturned = header ;
addBefore(e, next);
nextIndex++;
expectedModCount++;
}
final void checkForComodification() {
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
}
}<span style="font-weight: normal;"> </span> LinkedList的Iterator實現就分析完了，從這里可以看出數組和鏈表的遍歷方式不同，但對于用戶統一使用Iterator迭代器進行遍歷器，做到只需面對接口編程，這也是Iterator的最終要做到的。
最后啰嗦一句，Iterator是比較簡單的一種設計模式，使用場景也僅限于此，不要糾結于Iterator的應用而是要明白其設計思想，同時要對一些常用數據結構應該要了解掌握。
Iterator 完！