欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

Java 集合系列(四)—— ListIterator 源码分析

程序员文章站 2022-07-11 22:02:46
以脑图的形式来展示Java集合知识,让零碎知识点形成体系 Iterator 对比 Iterator(迭代器)是一种设计模式,是一个对象,用于遍历集合中的所有元素。 Iterator 包含四个方法,分别是:next()、hasNext()、remove()、forEachRemaining(Consu ......

以脑图的形式来展示java集合知识,让零碎知识点形成体系

iterator 对比

  iterator(迭代器)是一种设计模式,是一个对象,用于遍历集合中的所有元素。
  iterator 包含四个方法,分别是:next()、hasnext()、remove()、foreachremaining(consumer<? super e> action)

  collection 接口继承 java.lang.iterable,因此所有 collection 实现类都拥有 iterator 迭代能力。
  逆向思考,iterable 面向众多的 collection 类型实现类,定义的方法就不可能太定制化,因此 iterator 定义的功能比较简单。
  仅有如上所列出来的四种方法,并且该迭代器只能够单向移动。

  由于 list 类型的 collection 是一个有序集合,对于拥有双向迭代是很有意义的。
  listiterator 接口则在继承 iterator 接口的基础上定义了:add(e newelement)、set(e newelement)、hasprevious()、previous()、nextindex()、previousindex() 等方法,使得 listiterator 迭代能力增强,能够进行双向迭代、迭代过程中可以进行增删改操作。

现象与问题

 

  1. add() 方法在迭代器位置前面添加一个新元素
  2. next() 与 previous() 返回越过的对象
  3. set() 方法替换的是 next() 和 previous() 方法返回的上一个元素
  4. next() 后,再 remove() 则删除前面的元素;previous() 则会删除后面的元素
 1         list<string> list = new linkedlist<>();
 2         list.add("aaa");
 3         list.add("bbb");
 4         list.add("ccc");
 5 
 6         listiterator<string> listiterator = list.listiterator();
 7 
 8         //迭代器位置: add-1 | aaa bbb ccc
 9         listiterator.add("add-1");
10         // add-1 add-1 | aaa bbb ccc
11         listiterator.add("add-2");
12 
13         // 返回: aaa
14         // add-1 add-1 aaa | bbb ccc
15         listiterator.next();
16         // add-1 add-1 aaa-set | bbb ccc
17         listiterator.set("aaa-set");
18         // bbb
19         // add-1 add-1 aaa-set bbb | ccc
20         listiterator.next();
21 
22         // 返回: bbb
23         // add-1 add-1 aaa-set | bbb ccc
24         listiterator.previous();
25         // add-1 add-1 aaa-set | bbb-set ccc
26         listiterator.set("bbb-set");
27 
28         // 删除 bbb-set
29         listiterator.remove();
30         listiterator.remove();
31 
32         system.out.println(list);

 

很多书本都有给出这样子的结论:

  • 链表有 n 个元素,则有 n+1 个位置可以添加新元素;

  • add() 方法只依赖迭代器的+位置;remove() 和 set() 方法依赖于迭代器的状态(此时迭代的方向);

  • 连续两个 remove() 会出错,remove() 前应先执行 next() 或 previous()。

迭代同时修改问题: 

  一个迭代器指向另一个迭代器刚刚删除的元素,则现在这个迭代器就变成无效的了(节点删除被回收;即使没被回收,该节点的前后引用也被重置为null)。
链表迭代器有能够检测到这种修改的功能,当发现集合被修改了,将会抛出一个 concurrentmodificationexception 异常

  为什么出现上面的这些现象与问题呢,我们还是从源码中寻找答案吧

 

源码分析

  有多个集合类根据自己的特点实现了 listiterator 接口,其实现都大同小异,这里我们主要分析 linkedlist 中所实现的 listiterator。

  首先我们来分析 linkedlist 的 listiterator() 和 listiterator(int index) 方法获取 listiterator 迭代器过程。

 1 // abstractlist.java
 2 // listiterator() 方法 linkedlist 类本身并没有重写,需要追溯到 abstractlist 抽象类
 3 
 4     // 获取 listiterator 迭代器
 5     public listiterator<e> listiterator() {
 6         return listiterator(0);
 7     }
 8 
 9     public listiterator<e> listiterator(final int index) {
10         rangecheckforadd(index);    // 检查 index 范围是否超出
11 
12         return new listitr(index);  // 该抽象类也有实现 listitr 类
13     }
14 
15     private void rangecheckforadd(int index) {
16         if (index < 0 || index > size())
17             throw new indexoutofboundsexception(outofboundsmsg(index));
18     }
  1 // linkedlist.java
  2 // linkedlist 类重写了 listiterator(int index) 方法
  3 
  4     public listiterator<e> listiterator(int index) {
  5         checkpositionindex(index);  // 同理 检查 index 范围;相关代码就不贴了
  6         return new listitr(index);
  7     }
  8 
  9 
 10     private class listitr implements listiterator<e> {
 11         private node<e> lastreturned;   // 上一次处理的节点
 12         private node<e> next;   // 即将要处理的节点
 13         private int nextindex;  // 即将要处理的节点的 index
 14         // modcount 表示集合和迭代器修改的次数;expectedmodcount 表示当前迭代器对集合修改的次数
 15         private int expectedmodcount = modcount;
 16 
 17         listitr(int index) {
 18             // assert ispositionindex(index);
 19             next = (index == size) ? null : node(index);
 20             nextindex = index;
 21         }
 22 
 23         public boolean hasnext() {
 24             return nextindex < size;
 25         }
 26 
 27         /**
 28         * 处理对象:迭代器当前的 next 节点
 29         * 将处理目标储到 lastreturned 变量中
 30         * 然后将当前的 next.next 节点保存起来,用于下一次迭代处理
 31         * nextindex 同时 +1
 32         * 返回 lastreturned.item 元素
 33         * 执行后:lastreturned 指向该次处理的节点;next、nextindex 指向该次处理节点的后一个节点
 34         */
 35         public e next() {
 36             // 检查 modcount 与 expectedmodcount 是否相等
 37             // 实际检查该链表是否被其他迭代器或者集合本身修改
 38             checkforcomodification();
 39             // 判断是否存在 next 节点
 40             if (!hasnext())
 41                 throw new nosuchelementexception();
 42             
 43             lastreturned = next;    // 将这次返回的 node 节点更新到迭代器中的 lastreturned 变量
 44             next = next.next;   // 将下一次需要处理 node 节点更新会 next 变量
 45             nextindex++;    // 变量 nextindex +1
 46             return lastreturned.item;   // 返回元素
 47         }
 48 
 49         public boolean hasprevious() {
 50             return nextindex > 0;
 51         }
 52 
 53         /**
 54         * 处理对象:迭代器当前的 next.prev 节点
 55         * 将处理目标储到 lastreturned 变量中
 56         * 然后将当前的 next.prev 节点保存起来,用于下一次迭代处理
 57         * nextindex 同时 -1
 58         * 返回当前的 next.item 元素
 59         * 执行后:next、lastreturned、nextindex 指向该次处理节点的前一个节点
 60         */
 61         public e previous() {
 62             checkforcomodification();
 63             // 判断是否存在 prev 节点
 64             if (!hasprevious())
 65                 throw new nosuchelementexception();
 66 
 67             // 处理当前 next 的 prev 节点
 68             // 特殊情况:next = null 时,则它的 prev 节点为 last 节点  
 69             lastreturned = next = (next == null) ? last : next.prev;    
 70             nextindex--;    // nextindex -1
 71             return lastreturned.item;
 72         }
 73 
 74         public int nextindex() {
 75             return nextindex;
 76         }
 77 
 78         public int previousindex() {
 79             return nextindex - 1;
 80         }
 81 
 82         /**
 83         * 处理对象:lastreturned
 84         * 删除 lastreturned 指向的节点,并置为 null
 85         * 同时保证 next 和 nextindex 指向同一个节点
 86         */
 87         public void remove() {
 88             checkforcomodification();   // 同理, 检查 modcount 与 expectedmodcount 是否相等
 89             if (lastreturned == null)
 90                 throw new illegalstateexception();
 91 
 92             node<e> lastnext = lastreturned.next;  // 暂存 lastreturned 的 next 节点,用于恢复迭代状态
 93             unlink(lastreturned);   // 删除最后返回的节点    modcount++;
 94             
 95             // 分迭代方向处理(因为删除一个节点后,需要恢复迭代状态:next 和 nextindex 指向同一个节点)
 96             if (next == lastreturned)   // next 与 lastreturned 节点相同则表明最近一次迭代操作是 previous()
 97                 next = lastnext;        // 删除了原有 next 指向的节点,因此 nextindex 相对指向的节点变为 next.next,需要更新 next 变量的指向
 98             else
 99                 nextindex--;    // next() 迭代方向;删除了next前面的节点,因此next的相对位置发生变化,需要 nextindex -1
100             lastreturned = null;    
101             expectedmodcount++;     // 同时 expectedmodcount++
102         }
103 
104         /**
105         * 处理对象:lastreturned
106         */
107         public void set(e e) {
108             if (lastreturned == null)
109                 throw new illegalstateexception();
110             checkforcomodification();
111             lastreturned.item = e;
112         }
113 
114         /**
115         * 分位置进行添加
116         */
117         public void add(e e) {
118             checkforcomodification();
119             lastreturned = null;
120             if (next == null)
121                 linklast(e);
122             else
123                 linkbefore(e, next);
124             nextindex++;
125             expectedmodcount++;
126         }
127 
128         public void foreachremaining(consumer<? super e> action) {
129             objects.requirenonnull(action);
130             while (modcount == expectedmodcount && nextindex < size) {
131                 action.accept(next.item);
132                 lastreturned = next;
133                 next = next.next;
134                 nextindex++;
135             }
136             checkforcomodification();
137         }
138 
139         /**
140         * 检查 modcount 与 expectedmodcount 是否相等,否则抛出错误
141         * listiterator 迭代器进行增删操作时,都会同时对这两个变量 +1
142         * 目的:
143         * 使用 listiterator 迭代器期间,linkedlist 对象有且只能当前这一个迭代器可以进行修改
144         * 避免 linkedlist 对象本身以及其他迭代器进行修改导致链表混乱
145         */
146         final void checkforcomodification() {
147             if (modcount != expectedmodcount)
148                 throw new concurrentmodificationexception();
149         }
150     }

 

 

小结

  总的来说 listiterator 是记录 list 位置的一个对象,它主要的成员变量是 lastreturned、next、nextindex 以及 expectedmodcount。

  1. next() 处理的是 next 节点,返回 next.item

  2. previous() 处理的是 next.prev 节点 返回 next.prev.item

  3. remove() 处理的是 lastreturned 节点,并置为null,但要注意的是,删除节点后的 next 与 nextindex 需分情况处理。

  4. set() 处理的是 lastreturned 节点,lastreturned.item = e

  5. add() 添加,并将 lastreturned 置为null

  这就很好地解释上面所提到的一些现象与问题了。
  典型的就是连续两个 remove() 会报错,那是因为第一个 reomve() 之后 lastreturned 被置为null;第二个 remove() 处理的对象是null,因此炮锤 illegalstateexception

 

知识脑图

from java core knowledge tree

Java 集合系列(四)—— ListIterator 源码分析

 

 

在 github 上建了一个 repository ,java core knowledge tree,各位看官若是喜欢请给个star,以示鼓励,谢谢。
https://github.com/suifeng412/jcktree

 

(以上是自己的一些见解,若有不足或者错误的地方请各位指出)

 作者:   

 原文地址: 

 声明:本博客文章为原创,只代表本人在工作学习中某一时间内总结的观点或结论。转载时请在文章页面明显位置给出原文链接