ArrayList分析2 :Itr、ListIterator以及SubList中的坑
时间:2023-11-13 21:07:02
一.不论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: