ArrayList分析2 :Itr、ListIterator以及SubList中的坑

語言: CN / TW / HK

ArrayList分析2 : ItrListIterator 以及 SubList 中的坑

轉載請註明出處: https://www.cnblogs.com/funnyzpc/p/16409137.html

一.不論 ListIterator 還是 SubList ,均是對 ArrayList 維護的陣列進行操作

首先我得說下 ListIterator 是什麼, ListIteratorIterator 均是迭代器介面,對應 ArrayList 中的實現就是 ListItrItr ,我們使用 ListIteratorSubList 的過程中很少對ArrayList的操作,如果有那就很嚴重了(下面會說的),對源陣列進行操作這是一個事實存在的問題:joy:,尤其在SubList表現的尤為嚴重~

先看看 ArrayListsubList 方法定義:

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); ,很明白了吧,再看看 SubListremove 方法論證下當前這個小標題哈~

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 返回的是一個深度拷貝的陣列,哪知 SubListArrayList 內部都是一家人( elementData ),所以在使用 subList 的函式時要謹記這一點,當然咯,既然 SubList 也是繼承自 AbstractListsubList 返回的陣列也能繼續呼叫 subList 方法,內部操作的陣列也是一樣,是不是很弔詭:joy::joy::joy:

二. ListItrprevious 方法不太好用

其實這是個小問題,我是基於以下兩點來判斷的.

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;
        }

ListItrhasPrevious 方法)

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 方法一般在 nextprevious 方法之後呼叫才可

如果看過上面的內容,估計你您能猜個八九,線上菜:

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 )

這時 是不是覺得直接使用 ListIterset 方法是條死路: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 中的 previousnext 不可同時使用,尤其在迴圈中

先看一段程式碼吧,試試看你電腦會不會炸: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 的值與預期的並不一樣,哈哈哈,不解釋了,這裡簡單的解決辦法是:如果是在迴圈內,就不要嘗試 nextprevious 可能的同時呼叫了: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: