ArrayList分析2 :Itr、ListIterator以及SubList中的坑
ArrayList分析2 : Itr
、 ListIterator
以及 SubList
中的坑
轉載請註明出處： http://www.cnblogs.com/funnyzpc/p/16409137.html
一.不論 ListIterator
還是 SubList
,均是對 ArrayList
維護的陣列進行操作
首先我得說下 ListIterator
是什麼， ListIterator
與 Iterator
均是迭代器介面，對應 ArrayList
中的實現就是 ListItr
與 Itr
，我們使用 ListIterator
或 SubList
的過程中很少對ArrayList的操作，如果有那就很嚴重了（下面會說的），對源陣列進行操作這是一個事實存在的問題:joy:，尤其在SubList表現的尤為嚴重～
先看看 ArrayList
的 subList
方法定義:
public List<E> subList(int fromIndex, int toIndex) {
subListRangeCheck(fromIndex, toIndex, size);
return new SubList(this, 0, fromIndex, toIndex);
}
可以看到 subList
方法返回的是 SubList
的一個例項，好，繼續看建構函式定義：
private class SubList extends AbstractList<E> implements RandomAccess {
private final AbstractList<E> parent;
private final int parentOffset;
private final int offset;
int size;
// SubList建構函式的具體定義
SubList(AbstractList<E> parent, int offset, int fromIndex, int toIndex) {
// 從offset開始擷取size個元素
this.parent = parent;
this.parentOffset = fromIndex;
this.offset = offset + fromIndex;
this.size = toIndex - fromIndex;
this.modCount = ArrayList.this.modCount;
}
首先我們要清楚的是 subList
對源陣列( elementData
)的取用範圍 是
fromIndex <=取用範圍< toIndex , 這裡用
取用範圍 其實很準確，接著看～ 因為
return new SubList(this, 0, fromIndex, toIndex); 對應建構函式的第一個引數
parent 其實也就是當前ArrayList的例項物件，這是其一，還有就是SubList的offset是預設的
offset+ fromIndex ，取用的範圍就
size 限制在
toIndex - fromIndex; 以內，不管是
ArrayList 還是
SubList 對陣列（
elementData ）的偏移操作，只不過一個是從0開始一個是從
offset + fromIndex; 開始～，如果你還是存在懷疑，先看看
SubList 中
get`方法：
public E get(int index) {
rangeCheck(index);
checkForComodification();
return ArrayList.this.elementData(offset + index);
}
看到沒， get
方法也只直接取用的原陣列( elementData
)-> return ArrayList.this.elementData(offset + index);
,很明白了吧，再看看 SubList
中 remove
方法論證下當前這個小標題哈～
public E remove(int index) {
rangeCheck(index);
checkForComodification();
E result = parent.remove(parentOffset + index);
this.modCount = parent.modCount;
this.size--;
return result;
}
我在前前面說過，這個 parent
其實也就是當前 ArrayList
的一個引用，既然是引用，而不是深拷貝，那這句 parent.remove(parentOffset + index);
操作的依然是原陣列 elementData
,實操一下看：
public static void main(String[] args) {
ArrayList arr = new ArrayList();
arr.add("a"); // 0
arr.add("b");
arr.add("c");
arr.add("d"); // 3
arr.add("e");
arr.add("f"); // 4
List sub_list = arr.subList(0, 3);
System.out.println(sub_list);// [a, b, c]
sub_list.remove(0);
System.out.println(sub_list); // [b, c]
System.out.println(arr); // [b, c, d, e, f]
}
坑吧:joy:，一般理解 subList
返回的是一個深度拷貝的陣列，哪知 SubList
與 ArrayList
內部都是一家人( elementData
)，所以在使用 subList
的函式時要謹記這一點，當然咯，既然 SubList
也是繼承自 AbstractList
， subList
返回的陣列也能繼續呼叫 subList
方法，內部操作的陣列也是一樣，是不是很弔詭:joy::joy::joy:
二. ListItr
的 previous
方法不太好用
其實這是個小問題，我是基於以下兩點來判斷的.
1.使用迭代器的習慣
我們實際使用迭代器的習慣是從左往右(一般陣列結構)，索引從小到大( index
),這樣的一個使用習慣：
public static void main(String[] args) {
ArrayList arr = new ArrayList();
arr.add("a"); // 0
arr.add("b");
arr.add("c");
arr.add("d"); // 3
ListIterator listIterator = arr.listIterator();
while(listIterator.hasPrevious()){
Object item = listIterator.next();
System.out.println(item);
}
}
以上程式碼是常規的程式碼邏輯，而且 previous
一般在 next
方法使用後才可使用，這裡就牽出另一個問題了，往下看:sunglasses:
2.迭代器的預設遊標是從0開始的
如果您覺得1的說法不夠信服的話，那就實操下看：
public static void main(String[] args) {
ArrayList arr = new ArrayList();
arr.add("a"); // 0
arr.add("b");
arr.add("c");
arr.add("d"); // 3
ListIterator listIterator = arr.listIterator();
while(listIterator.hasPrevious()){//這裡返回的始終是false，所以while內的邏輯根本就不會被執行
Object item = listIterator.previous();
System.out.println(item); // 這裡沒輸出
}
}
哈哈哈 :joy:
，看出 bug
所在了嘛，再看看 ListItr
的建構函式吧
（ ArrayList
函式）
public ListIterator<E> listIterator() {
// 當前方法同以上，只不過是直接從0開始索引並返回一個迭代器 ,具體程式碼方法內會有說明
return new ListItr(0);
}
( ListItr
的建構函式）
private class ListItr extends Itr implements ListIterator<E> {
ListItr(int index) {
super();
cursor = index;
}
（ ListItr
的 hasPrevious
方法）
public boolean hasPrevious() {
return cursor != 0;
}
看出癥結所在了吧，其實很簡單，也就是預設 listIterator()
的建構函式傳入的遊標是 0
( cursor = index;
)導致的，好了，對於一個正常的 previous
方法的使用該怎麼辦呢
public static void main(String[] args) {
ArrayList arr = new ArrayList();
arr.add("a"); // 0
arr.add("b");
arr.add("c");
arr.add("d"); // 3
ListIterator listIterator = arr.listIterator(arr.size());// 修改後的
while(listIterator.hasPrevious()){
Object item = listIterator.previous();
System.out.println(item);// b a
}
}
其實也就改了一句 ListIterator listIterator = arr.listIterator(arr.size());
,是不是超 easy，所以使用 previous
的時候一定要指定下 index
(對應 ListIter
的其實就是遊標： cursor
) ， 知其症之所在方能對症下藥
:stuck_out_tongue_winking_eye:
三. ListItr
中的 set、remove
方法一般在 next
或 previous
方法之後呼叫才可
如果看過上面的內容，估計你您能猜個八九，線上菜：
public static void main(String[] args) {
ArrayList arr = new ArrayList();
arr.add("a");
arr.add("b");
arr.add("c");
arr.add("d");
System.out.println(arr);
ListIterator listIterator = arr.listIterator();
listIterator.set("HELLO"); // throw error
}
我還是建議您先將上面一段程式碼執行下看:joy:，雖然結果還是拋錯。。。
好吧，瞅瞅原始碼看：
public void set(E e) {
if (lastRet < 0)
throw new IllegalStateException();//發生異常的位置
checkForComodification();
try {
ArrayList.this.set(lastRet, e);
} catch (IndexOutOfBoundsException ex) {
throw new ConcurrentModificationException();
}
}
再看看 lastRet
定義的地方:
private class Itr implements Iterator<E> {
// 這個其實預設就是 i=0;
int cursor; // index of next element to return :下一個將要返回的元素位置的索引,其實也就是個遊標
int lastRet = -1; // index of last element returned; -1 if no such :返回的最後一個元素的索引； -1 如果沒有
int expectedModCount = modCount;
順帶再回頭看看構造方法:
ListItr(int index) {
super();
cursor = index;
}
我先解釋下lastRet是什麼， lastRet
其實是 cursor
(俗稱遊標)的參照位置，具體的說它是標識當前迴圈的元素的位置( cursor-1
)
這時 是不是覺得直接使用 ListIter
的 set
方法是條死路:joy:..., 既然 lastRet
必須 >=0
才可，找找看哪裡有變動 lastRet
的地方：
@SuppressWarnings("unchecked")
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];
}
@SuppressWarnings("unchecked")
public E previous() {
checkForComodification();
int i = cursor - 1;
if (i < 0)
throw new NoSuchElementException();
Object[] elementData = ArrayList.this.elementData;
if (i >= elementData.length)
throw new ConcurrentModificationException();
cursor = i;
return (E) elementData[lastRet = i];
}
看到沒 lastRet = i
它解釋了一切
現在來嘗試解決這個問題，兩種方式：
（方式一)
public static void main(String[] args) {
ArrayList arr = new ArrayList();
arr.add("a");
arr.add("b");
arr.add("c");
arr.add("d");
System.out.println(arr);
ListIterator listIterator = arr.listIterator();
listIterator.next();
listIterator.set("HELLO");
System.out.println(arr);
}
(方式二）
public static void main(String[] args) {
ArrayList arr = new ArrayList();
arr.add("a");
arr.add("b");
arr.add("c");
arr.add("d");
System.out.println(arr);
ListIterator listIterator = arr.listIterator(3);
listIterator.previous();
listIterator.set("HELLO");
System.out.println(arr);
}
四. ListItr
中的 previous
、 next
不可同時使用,尤其在迴圈中
先看一段程式碼吧，試試看你電腦會不會炸:bomb:
public static void main(String[] args) {
ArrayList arr = new ArrayList();
arr.add("a");
arr.add("b");
arr.add("c");
arr.add("d");
ListIterator listIterator = arr.listIterator();
while (listIterator.hasNext()){
Object item = listIterator.next();
System.out.println(item);
if("c".equals(item)){
Object previous_item = listIterator.previous(); // c
if("b".equals(previous_item)){
return;
}
}
}
}
怎麼樣，我大概會猜出你的看法， previous_item
的值與預期的並不一樣，哈哈哈，不解釋了，這裡簡單的解決辦法是：如果是在迴圈內，就不要嘗試 next
與 previous
可能的同時呼叫了:smile_cat: ，非迴圈也不建議，還是留意下原始碼看(此處省略n多字:stuck_out_tongue_closed_eyes:).
五. Itr、ListItr、SubList
使用過程中不可穿插 ArrayList
的相關操作( remove、add
等)，否則拋錯
廢話是多餘的，先給個 事故現場:joy:
：
public static void main(String[] args) {
ArrayList arr = new ArrayList();
arr.add("a");
arr.add("b");
arr.add("c");
arr.add("d");
ListIterator listIterator = arr.listIterator();
arr.add("HELLO");
listIterator.hasNext();
listIterator.next(); // throw error
}
為了更清楚，給出異常資訊：
Exception in thread "main" java.util.ConcurrentModificationException at com.mee.source.c1.ArrayList$Itr.checkForComodification(ArrayList.java:1271) at com.mee.source.c1.ArrayList$Itr.next(ArrayList.java:1181) at com.mee.source.test.ArrayList_listIterator_Test.main(ArrayList_listIterator_Test.java:208)
next
方法：
@SuppressWarnings("unchecked")
public E next() {
checkForComodification(); // 1181行，這裡丟擲錯誤！
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];
}
checkForComodification方法：
final void checkForComodification() {
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
}
這裡我先賣個關子，具體原因需要您看看上一篇部落格 ArrayList分析1-迴圈、擴容、版本 關於版本的部分
解決方法嘛，小標題就是結論也是規則，繞著走避坑便是啦:blush:
- 在Go中如何正確重試請求
- 一個註解搞定SpringBoot介面定製屬性加解密
- pnpm 的 workspace 實現 monorepo 工程
- 詳解ConCurrentHashMap原始碼（jdk1.8）
- 一步一圖帶你深入剖析 JDK NIO ByteBuffer 在不同位元組序下的設計與實現
- 案例復現，帶你分析Priority Blocking Queue比較器異常導致的NPE問題
- Java多執行緒超級詳解(只看這篇就夠了)
- Docker Compose之容器編排開發初探
- 飛書前端提到的競態問題，在 Android 上怎麼解決？
- 設計模式之裝飾器模式
- 使用CSS實現多種Noise噪點效果
- 你有物件類,我有結構體,Go lang1.18入門精煉教程，由白丁入鴻儒，go lang結構體(struct)的使用EP06
- 設計模式之組合模式
- 43%非常看好TypeScript…解讀“2022前端開發者現狀報告”
- 學長告訴我，大廠MySQL都是通過SSH連線的
- 運籌帷幄決勝千里，Python3.10原生協程asyncio工業級真實協程非同步消費任務排程實踐
- 聊聊Spring事務控制策略以及@Transactional失效問題避坑
- [開源專案]可觀測、易使用的SpringBoot執行緒池
- 看到這個應用上下線方式，不禁感嘆：優雅，太優雅了！
- 【Java面試】怎麼防止快取擊穿的問題？