锐单电子商城 , 一站式电子元器件采购平台!
  • 电话:400-990-0325

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

时间:2023-11-13 21:07:02 二极管模块mee75

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

首先,我得说说ListIterator是什么,ListIterator与Iterator都是迭代接口,对应ArrayList实现就是ListItr与Itr,我们使用ListIterator或SubList很少对ArrayList如果有,操作会很严重(下面会说),操作源数组是一个事实问题:joy:,尤其在SubList特别严重

先看看ArrayList的subList方法定义:

public List subList(int fromIndex, int toIndex) {         subListRangeCheck(fromIndex, toIndex, size);         return new SubList(this, 0, fromIndex, toIndex);     }

可以看到subList方法返回是SubList一个例子,好的,继续看构造函数的定义:

private class SubList extends AbstractList implements RandomAccess {         private final AbstractList parent;         private final int parentOffset;         private final int offset;         int size;         // SubList构造函数的具体定义         SubList(AbstractList 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开始,从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

( ListItr 的构造函数)

private class ListItr extends Itr implements ListIterator {
        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 {
       // 这个其实默认就是 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:

锐单商城拥有海量元器件数据手册IC替代型号,打造电子元器件IC百科大全!

相关文章