Java 集合源碼解析：ListIterator

ListIterator

根據官方文檔介紹, ListIterator 有以下功能：

允許我們向前、向後兩個方向遍歷 List; 在遍歷時修改 List 的元素； 遍歷時獲取迭代器當前游標所在位置。

注意，迭代器 沒有當前所在元素一說，它只有一個游標( cursor )的概念，這個游標總是在元素之間，比如這樣:

初始時它在第 0 個元素之前，調用 next() 游標後移一位：

調用 previous() 游標就會回到之前位置。當向後遍歷完元素，游標就會在元素 N 的後面：

也就是說長度為 N 的集合會有 N+1 個游標的位置。

---

ListIterator 繼承自 Iterator 接口（關於 Iterator 的介紹 請點這裡），在 Iterator 的基礎上增加了 6 個方法：

介紹一下新來的幾個方法：

void hasPrevious()
判斷游標前面是否有元素; Object previous()
返回游標前面的元素，同時游標前移一位。游標前沒有元素就報 java.util.NoSuchElementException 的錯，所以使用前最好判斷一下; int nextIndex()
返回游標後邊元素的索引位置，初始為 0 ；遍歷 N 個元素結束時為 N; int previousIndex()
返回游標前面元素的位置，初始時為 -1，同時報 java.util.NoSuchElementException 錯; void add(E)
在游標 前面 插入一個元素 注意，是前面 void set(E)
更新迭代器最後一次操作的元素為 E，也就是更新最後一次調用 next() 或者 previous() 返回的元素。 注意，當沒有迭代，也就是沒有調用 next() 或者 previous() 直接調用 set 時會報 java.lang.IllegalStateException 錯; void remove()
刪除迭代器最後一次操作的元素，注意事項和 set 一樣。

ListIterator 有兩種獲取方式

List.listIterator() List.listIterator(int location)

區別在於第二種可以指定 游標的所在位置。

ListIterator 的具體實現？

AbstractList 作為 List 的直接子類，裡面實現了 listIterator() 方法，並且有兩個內部迭代器實現類：SimpleListIterator，FullListIterator：

listIterator() 返回的是 FullListIterator()：

FullListIterator 繼承了 SimpleListIterator, SimpleListIterator 實現了 Iterator 接口：

private class SimpleListIterator implements Iterator {
    //游標的位置，初始為 -1
    int pos = -1;
    //用來判斷是否 fail-fast 的變量
    int expectedModCount;
    //記錄上次迭代的位置
    int lastPosition = -1;

    SimpleListIterator() {
        expectedModCount = modCount;
    }

    //當游標沒有跑到最後一個元素後面時 hasNext 返回 true
    public boolean hasNext() {
        return pos + 1 < size();
    }

    //獲取下一個元素
    public E next() {
        if (expectedModCount == modCount) {
            try {
                //獲取游標後面的元素，具體子類有具體實現
                E result = get(pos + 1);
                //更新
                lastPosition = ++pos;
                return result;
            } catch (IndexOutOfBoundsException e) {
                throw new NoSuchElementException();
            }
        }
        //當迭代時修改元素，就會報這個錯，上篇文章介紹過解決辦法~
        throw new ConcurrentModificationException();
    }

    //刪除上次迭代操作的元素
    public void remove() {
        //還沒進行迭代操作就會報這個錯
        if (this.lastPosition == -1) {
            throw new IllegalStateException();
        }

        if (expectedModCount != modCount) {
            throw new ConcurrentModificationException();
        }

        try {
            //調用子類實現的刪除操作
            AbstractList.this.remove(lastPosition);
        } catch (IndexOutOfBoundsException e) {
            throw new ConcurrentModificationException();
        }

        expectedModCount = modCount;
        if (pos == lastPosition) {
            pos--;
        }
        //每次刪除後都會還原為 -1，也就是說我們迭代一次後只能 remove 一次，再 remove 就會報錯
        lastPosition = -1;
    }
}

了解了 SimpleListIterator 後我們看下 FullListIterator 的具體實現：

private final class FullListIterator extends SimpleListIterator implements ListIterator {
    //根據 start 指定游標位置
    FullListIterator(int start) {
        if (start >= 0 && start <= size()) {
            pos = start - 1;
        } else {
            throw new IndexOutOfBoundsException();
        }
    }

    //在游標前面添加元素
    public void add(E object) {
        if (expectedModCount == modCount) {
            try {
                //調用子類的添加操作，ArrayList, LinkedList,Vector 的添加操作實現有所不同
                AbstractList.this.add(pos + 1, object);
            } catch (IndexOutOfBoundsException e) {
                throw new NoSuchElementException();
            }
            //游標後移一位
            pos++;
            //!注意！ 添加後 上次迭代位置又變回 -1 了，說明 add 後調用 remove, set 會有問題！
            lastPosition = -1;
            if (modCount != expectedModCount) {
                expectedModCount = modCount;
            }
        } else {
            throw new ConcurrentModificationException();
        }
    }

    //當游標不在初始位置（-1）時返回true
    public boolean hasPrevious() {
        return pos >= 0;
    }

    //游標後面的元素索引，就是游標 +1
    public int nextIndex() {
        return pos + 1;
    }

    //游標前面一個元素
    public E previous() {
        if (expectedModCount == modCount) {
            try {
                E result = get(pos);
                lastPosition = pos;
                pos--;
                return result;
            } catch (IndexOutOfBoundsException e) {
                throw new NoSuchElementException();
            }
        }
        throw new ConcurrentModificationException();
    }

    //游標前面元素的索引，就是游標的位置,有點暈的看開頭那幾張圖
    public int previousIndex() {
        return pos;
    }

    //更新之前迭代的元素為 object
    public void set(E object) {
        if (expectedModCount == modCount) {
            try {
                //調用子類的set
                AbstractList.this.set(lastPosition, object);
            } catch (IndexOutOfBoundsException e) {
                throw new IllegalStateException();
            }
        } else {
            throw new ConcurrentModificationException();
        }
    }
}

可以看到 SimpleListIterator 的主要操作最後都交給子類來實現，List 的子類 ArrayList, LinkedList, Vector 由於底層實現原理不同（數組，雙向鏈表），具體操作類實現有所不同。

等接下來分析到具體子類再看相關實現吧。