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

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

转载请注明出处:https://www.cnblogs.com/funnyzpc/p/16409137.html

一.不论ListIterator还是SubList,均是对ArrayList维护的数组进行操作

首先我得说下ListIterator是什么,ListIteratorIterator均是迭代器接口,对应ArrayList中的实现就是ListItrItr,我们使用ListIteratorSubList的过程中很少对ArrayList的操作,如果有那就很严重了(下面会说的),对源数组进行操作这是一个事实存在的问题,尤其在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;开始~,如果你还是存在怀疑,先看看SubListget`方法:

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

坑吧,一般理解subList返回的是一个深度拷贝的数组,哪知SubListArrayList内部都是一家人(elementData),所以在使用subList的函数时要谨记这一点,当然咯,既然SubList也是继承自AbstractListsubList返回的数组也能继续调用subList方法,内部操作的数组也是一样,是不是很吊诡

二.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方法使用后才可使用,这里就牵出另一个问题了,往下看

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); // 这里没输出
        }
    }

哈哈哈,看出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) ,知其症之所在方能对症下药

三.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
    }

我还是建议您先将上面一段代码执行下看,虽然结果还是抛错。。。
好吧,瞅瞅源码看:

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方法是条死路…, 既然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不可同时使用,尤其在循环中

先看一段代码吧,试试看你电脑会不会炸

   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可能的同时调用了 ,非循环也不建议,还是留意下源码看(此处省略n多字).

五. Itr、ListItr、SubList使用过程中不可穿插ArrayList的相关操作(remove、add等),否则抛错

废话是多余的,先给个事故现场

    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-循环、扩容、版本 关于版本的部分🤩
解决方法嘛,小标题就是结论也是规则,绕着走避坑便是啦

张贴在2