ListIterator 源碼分析
Iterator 對(duì)比
??Iterator（迭代器）是一種設(shè)計(jì)模式，是一個(gè)對(duì)象，用于遍歷集合中的所有元素。
??Iterator 包含四個(gè)方法，分別是：next()、hasNext()、remove()、forEachRemaining(Consumer<? super E> action)
??Collection 接口繼承 java.lang.Iterable，因此所有 Collection 實(shí)現(xiàn)類都擁有 Iterator 迭代能力。
??逆向思考，Iterable 面向眾多的 Collection 類型實(shí)現(xiàn)類，定義的方法就不可能太定制化，因此 Iterator 定義的功能比較簡單。
??僅有如上所列出來的四種方法，并且該迭代器只能夠單向移動(dòng)。
??由于 List 類型的 Collection 是一個(gè)有序集合，對(duì)于擁有雙向迭代是很有意義的。
??ListIterator 接口則在繼承 Iterator 接口的基礎(chǔ)上定義了：add(E newElement)、set(E newElement)、hasPrevious()、previous()、nextIndex()、previousIndex() 等方法，使得 ListIterator 迭代能力增強(qiáng)，能夠進(jìn)行雙向迭代、迭代過程中可以進(jìn)行增刪改操作。
現(xiàn)象與問題
- add() 方法在迭代器位置前面添加一個(gè)新元素
- next() 與 previous() 返回越過的對(duì)象
- set() 方法替換的是 next() 和 previous() 方法返回的上一個(gè)元素
- next() 后，再 remove() 則刪除前面的元素；previous() 則會(huì)刪除后面的元素
List<String> list = new LinkedList<>();
list.add("aaa");
list.add("bbb");
list.add("ccc");
ListIterator<String> listIterator = list.listIterator();
//迭代器位置： add-1 | aaa bbb ccc
listIterator.add("add-1");
// add-1 add-1 | aaa bbb ccc
listIterator.add("add-2");
// 返回： aaa
// add-1 add-1 aaa | bbb ccc
listIterator.next();
// add-1 add-1 aaa-set | bbb ccc
listIterator.set("aaa-set");
// bbb
// add-1 add-1 aaa-set bbb | ccc
listIterator.next();
// 返回： bbb
// add-1 add-1 aaa-set | bbb ccc
listIterator.previous();
// add-1 add-1 aaa-set | bbb-set ccc
listIterator.set("bbb-set");
// 刪除 bbb-set
listIterator.remove();
listIterator.remove();
System.out.println(list);
很多書本都有給出這樣子的結(jié)論：
- 鏈表有 n 個(gè)元素，則有 n+1 個(gè)位置可以添加新元素；
- add() 方法只依賴迭代器的+位置；remove() 和 set() 方法依賴于迭代器的狀態(tài)（此時(shí)迭代的方向）；
- 連續(xù)兩個(gè) remove() 會(huì)出錯(cuò)，remove() 前應(yīng)先執(zhí)行 next() 或 previous()。
迭代同時(shí)修改問題：
??一個(gè)迭代器指向另一個(gè)迭代器剛剛刪除的元素，則現(xiàn)在這個(gè)迭代器就變成無效的了（節(jié)點(diǎn)刪除被回收；即使沒被回收，該節(jié)點(diǎn)的前后引用也被重置為null）。
鏈表迭代器有能夠檢測到這種修改的功能，當(dāng)發(fā)現(xiàn)集合被修改了，將會(huì)拋出一個(gè) ConcurrentModificationException 異常
??為什么出現(xiàn)上面的這些現(xiàn)象與問題呢，我們還是從源碼中尋找答案吧
源碼分析
??有多個(gè)集合類根據(jù)自己的特點(diǎn)實(shí)現(xiàn)了 ListIterator 接口，其實(shí)現(xiàn)都大同小異，這里我們主要分析 LinkedList 中所實(shí)現(xiàn)的 ListIterator。
??首先我們來分析 LinkedList 的 listIterator() 和 listIterator(int index) 方法獲取 ListIterator 迭代器過程。
// AbstractList.java
// listIterator() 方法 LinkedList 類本身并沒有重寫，需要追溯到 AbstractList 抽象類
// 獲取 ListIterator 迭代器
public ListIterator<E> listIterator() {
return listIterator(0);
}
public ListIterator<E> listIterator(final int index) {
rangeCheckForAdd(index); // 檢查 index 范圍是否超出
return new ListItr(index); // 該抽象類也有實(shí)現(xiàn) ListItr 類
}
private void rangeCheckForAdd(int index) {
if (index < 0 || index > size())
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
// LinkedList.java
// LinkedList 類重寫了 listIterator(int index) 方法
public ListIterator<E> listIterator(int index) {
checkPositionIndex(index); // 同理 檢查 index 范圍；相關(guān)代碼就不貼了
return new ListItr(index);
}
private class ListItr implements ListIterator<E> {
private Node<E> lastReturned; // 上一次處理的節(jié)點(diǎn)
private Node<E> next; // 即將要處理的節(jié)點(diǎn)
private int nextIndex; // 即將要處理的節(jié)點(diǎn)的 index
// modCount 表示集合和迭代器修改的次數(shù)；expectedModCount 表示當(dāng)前迭代器對(duì)集合修改的次數(shù)
private int expectedModCount = modCount;
ListItr(int index) {
// assert isPositionIndex(index);
next = (index == size) ? null : node(index);
nextIndex = index;
}
public boolean hasNext() {
return nextIndex < size;
}
/**
* 處理對(duì)象：迭代器當(dāng)前的 next 節(jié)點(diǎn)
* 將處理目標(biāo)儲(chǔ)到 lastReturned 變量中
* 然后將當(dāng)前的 next.next 節(jié)點(diǎn)保存起來，用于下一次迭代處理
* nextIndex 同時(shí) +1
* 返回 lastReturned.item 元素
* 執(zhí)行后：lastReturned 指向該次處理的節(jié)點(diǎn)；next、nextIndex 指向該次處理節(jié)點(diǎn)的后一個(gè)節(jié)點(diǎn)
*/
public E next() {
// 檢查 modCount 與 expectedModCount 是否相等
// 實(shí)際檢查該鏈表是否被其他迭代器或者集合本身修改
checkForComodification();
// 判斷是否存在 next 節(jié)點(diǎn)
if (!hasNext())
throw new NoSuchElementException();
lastReturned = next; // 將這次返回的 node 節(jié)點(diǎn)更新到迭代器中的 lastReturned 變量
next = next.next; // 將下一次需要處理 node 節(jié)點(diǎn)更新會(huì) next 變量
nextIndex++; // 變量 nextIndex +1
return lastReturned.item; // 返回元素
}
public boolean hasPrevious() {
return nextIndex > 0;
}
/**
* 處理對(duì)象：迭代器當(dāng)前的 next.prev 節(jié)點(diǎn)
* 將處理目標(biāo)儲(chǔ)到 lastReturned 變量中
* 然后將當(dāng)前的 next.prev 節(jié)點(diǎn)保存起來，用于下一次迭代處理
* nextIndex 同時(shí) -1
* 返回當(dāng)前的 next.item 元素
* 執(zhí)行后：next、lastReturned、nextIndex 指向該次處理節(jié)點(diǎn)的前一個(gè)節(jié)點(diǎn)
*/
public E previous() {
checkForComodification();
// 判斷是否存在 prev 節(jié)點(diǎn)
if (!hasPrevious())
throw new NoSuchElementException();
// 處理當(dāng)前 next 的 prev 節(jié)點(diǎn)
// 特殊情況：next = null 時(shí)，則它的 prev 節(jié)點(diǎn)為 last 節(jié)點(diǎn)
lastReturned = next = (next == null) ? last : next.prev;
nextIndex--; // nextIndex -1
return lastReturned.item;
}
public int nextIndex() {
return nextIndex;
}
public int previousIndex() {
return nextIndex - 1;
}
/**
* 處理對(duì)象：lastReturned
* 刪除 lastReturned 指向的節(jié)點(diǎn)，并置為 null
* 同時(shí)保證 next 和 nextIndex 指向同一個(gè)節(jié)點(diǎn)
*/
public void remove() {
checkForComodification(); // 同理， 檢查 modCount 與 expectedModCount 是否相等
if (lastReturned == null)
throw new IllegalStateException();
Node<E> lastNext = lastReturned.next; // 暫存 lastReturned 的 next 節(jié)點(diǎn)，用于恢復(fù)迭代狀態(tài)
unlink(lastReturned); // 刪除最后返回的節(jié)點(diǎn) modCount++;
// 分迭代方向處理（因?yàn)閯h除一個(gè)節(jié)點(diǎn)后，需要恢復(fù)迭代狀態(tài)：next 和 nextIndex 指向同一個(gè)節(jié)點(diǎn)）
if (next == lastReturned) // next 與 lastReturned 節(jié)點(diǎn)相同則表明最近一次迭代操作是 previous()
next = lastNext; // 刪除了原有 next 指向的節(jié)點(diǎn)，因此 nextIndex 相對(duì)指向的節(jié)點(diǎn)變?yōu)?next.next，需要更新 next 變量的指向
else
nextIndex--; // next() 迭代方向；刪除了next前面的節(jié)點(diǎn)，因此next的相對(duì)位置發(fā)生變化，需要 nextIndex -1
lastReturned = null;
expectedModCount++; // 同時(shí) expectedModCount++
}
/**
* 處理對(duì)象：lastReturned
*/
public void set(E e) {
if (lastReturned == null)
throw new IllegalStateException();
checkForComodification();
lastReturned.item = e;
}
/**
* 分位置進(jìn)行添加
*/
public void add(E e) {
checkForComodification();
lastReturned = null;
if (next == null)
linkLast(e);
else
linkBefore(e, next);
nextIndex++;
expectedModCount++;
}
public void forEachRemaining(Consumer<? super E> action) {
Objects.requireNonNull(action);
while (modCount == expectedModCount && nextIndex < size) {
action.accept(next.item);
lastReturned = next;
next = next.next;
nextIndex++;
}
checkForComodification();
}
/**
* 檢查 modCount 與 expectedModCount 是否相等，否則拋出錯(cuò)誤
* ListIterator 迭代器進(jìn)行增刪操作時(shí)，都會(huì)同時(shí)對(duì)這兩個(gè)變量 +1
* 目的：
* 使用 ListIterator 迭代器期間，LinkedList 對(duì)象有且只能當(dāng)前這一個(gè)迭代器可以進(jìn)行修改
* 避免 LinkedList 對(duì)象本身以及其他迭代器進(jìn)行修改導(dǎo)致鏈表混亂
*/
final void checkForComodification() {
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
}
}
小結(jié)
??總的來說 ListIterator 是記錄 List 位置的一個(gè)對(duì)象，它主要的成員變量是 lastReturned、next、nextIndex 以及 expectedModCount。
- next() 處理的是 next 節(jié)點(diǎn)，返回 next.item
- previous() 處理的是 next.prev 節(jié)點(diǎn) 返回 next.prev.item
- remove() 處理的是 lastReturned 節(jié)點(diǎn)，并置為null，但要注意的是，刪除節(jié)點(diǎn)后的 next 與 nextIndex 需分情況處理。
- set() 處理的是 lastReturned 節(jié)點(diǎn)，lastReturned.item = e
- add() 添加，并將 lastReturned 置為null
??這就很好地解釋上面所提到的一些現(xiàn)象與問題了。
??典型的就是連續(xù)兩個(gè) remove() 會(huì)報(bào)錯(cuò)，那是因?yàn)榈谝粋€(gè) reomve() 之后 lastReturned 被置為null；第二個(gè) remove() 處理的對(duì)象是null，因此炮錘 IllegalStateException
知識(shí)腦圖
ListIterator
