Java 集合源码解析(2):ListIterator

今天心情和股票一样红,还是学学 ListIterator 吧!

ListIterator

根据官方文档介绍, ListIterator 有以下功能:

  1. 允许我们向前、向后两个方向遍历 List;
  2. 在遍历时修改 List 的元素;
  3. 遍历时获取迭代器当前游标所在位置。

注意,迭代器 没有当前所在元素一说,它只有一个游标( cursor )的概念,这个游标总是在元素之间,比如这样:

初始时它在第 0 个元素之前,调用 next() 游标后移一位:

调用 previous() 游标就会回到之前位置。当向后遍历完元素,游标就会在元素 N 的后面:

也就是说长度为 N 的集合会有 N+1 个游标的位置。

ListIterator 继承自 Iterator 接口(关于 Iterator 的介绍 请点这里),在 Iterator 的基础上增加了 6 个方法:

介绍一下新来的几个方法:

  • void hasPrevious()
    • 判断游标前面是否有元素;
  • Object previous()
    • 返回游标前面的元素,同时游标前移一位。游标前没有元素就报 java.util.NoSuchElementException 的错,所以使用前最好判断一下;
  • int nextIndex()
    • 返回游标后边元素的索引位置,初始为 0 ;遍历 N 个元素结束时为 N;
  • int previousIndex()
    • 返回游标前面元素的位置,初始时为 -1,同时报 java.util.NoSuchElementException 错;
  • void add(E)
    • 在游标 前面 插入一个元素
    • 注意,是前面
  • void set(E)
    • 更新迭代器最后一次操作的元素为 E,也就是更新最后一次调用 next() 或者 previous() 返回的元素。
    • 注意,当没有迭代,也就是没有调用 next() 或者 previous() 直接调用 set 时会报 java.lang.IllegalStateException 错;
  • void remove()
    • 删除迭代器最后一次操作的元素,注意事项和 set 一样。

ListIterator 有两种获取方式

  • List.listIterator()
  • List.listIterator(int location)

区别在于第二种可以指定 游标的所在位置。

ListIterator 的具体实现?

AbstractList 作为 List 的直接子类,里面实现了 listIterator() 方法,并且有两个内部迭代器实现类:SimpleListIterator,FullListIterator:

listIterator() 返回的是 FullListIterator():

FullListIterator 继承了 SimpleListIterator, SimpleListIterator 实现了 Iterator 接口:

private class SimpleListIterator implements Iterator<E> {
    //游标的位置,初始为 -1
    int pos = -1;
    //用来判断是否 fail-fast 的变量
    int expectedModCount;
    //记录上次迭代的位置
    int lastPosition = -1;

    SimpleListIterator() {
        expectedModCount = modCount;
    }

    //当游标没有跑到最后一个元素后面时 hasNext 返回 true
    public boolean hasNext() {
        return pos + 1 < size();
    }

    //获取下一个元素
    public E next() {
        if (expectedModCount == modCount) {
            try {
                //获取游标后面的元素,具体子类有具体实现
                E result = get(pos + 1);
                //更新
                lastPosition = ++pos;
                return result;
            } catch (IndexOutOfBoundsException e) {
                throw new NoSuchElementException();
            }
        }
        //当迭代时修改元素,就会报这个错,上篇文章介绍过解决办法~
        throw new ConcurrentModificationException();
    }

    //删除上次迭代操作的元素
    public void remove() {
        //还没进行迭代操作就会报这个错
        if (this.lastPosition == -1) {
            throw new IllegalStateException();
        }

        if (expectedModCount != modCount) {
            throw new ConcurrentModificationException();
        }

        try {
            //调用子类实现的删除操作
            AbstractList.this.remove(lastPosition);
        } catch (IndexOutOfBoundsException e) {
            throw new ConcurrentModificationException();
        }

        expectedModCount = modCount;
        if (pos == lastPosition) {
            pos--;
        }
        //每次删除后都会还原为 -1,也就是说我们迭代一次后只能 remove 一次,再 remove 就会报错
        lastPosition = -1;
    }
}

了解了 SimpleListIterator 后我们看下 FullListIterator 的具体实现:

private final class FullListIterator extends SimpleListIterator implements ListIterator<E> {
    //根据 start 指定游标位置
    FullListIterator(int start) {
        if (start >= 0 && start <= size()) {
            pos = start - 1;
        } else {
            throw new IndexOutOfBoundsException();
        }
    }

    //在游标前面添加元素
    public void add(E object) {
        if (expectedModCount == modCount) {
            try {
                //调用子类的添加操作,ArrayList, LinkedList,Vector 的添加操作实现有所不同
                AbstractList.this.add(pos + 1, object);
            } catch (IndexOutOfBoundsException e) {
                throw new NoSuchElementException();
            }
            //游标后移一位
            pos++;
            //!注意! 添加后 上次迭代位置又变回 -1 了,说明 add 后调用 remove, set 会有问题!
            lastPosition = -1;
            if (modCount != expectedModCount) {
                expectedModCount = modCount;
            }
        } else {
            throw new ConcurrentModificationException();
        }
    }

    //当游标不在初始位置(-1)时返回true
    public boolean hasPrevious() {
        return pos >= 0;
    }

    //游标后面的元素索引,就是游标 +1
    public int nextIndex() {
        return pos + 1;
    }

    //游标前面一个元素
    public E previous() {
        if (expectedModCount == modCount) {
            try {
                E result = get(pos);
                lastPosition = pos;
                pos--;
                return result;
            } catch (IndexOutOfBoundsException e) {
                throw new NoSuchElementException();
            }
        }
        throw new ConcurrentModificationException();
    }

    //游标前面元素的索引,就是游标的位置,有点晕的看开头那几张图
    public int previousIndex() {
        return pos;
    }

    //更新之前迭代的元素为 object
    public void set(E object) {
        if (expectedModCount == modCount) {
            try {
                //调用子类的set
                AbstractList.this.set(lastPosition, object);
            } catch (IndexOutOfBoundsException e) {
                throw new IllegalStateException();
            }
        } else {
            throw new ConcurrentModificationException();
        }
    }
}

可以看到 SimpleListIterator 的主要操作最后都交给子类来实现,List 的子类 ArrayList, LinkedList, Vector 由于底层实现原理不同(数组,双向链表),具体操作类实现有所不同。

等接下来分析到具体子类再看相关实现吧。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏desperate633

HashSet实现原理分析(Java源码剖析)add(E e)remove(Object o)iterator()小结

本文将深入讨论HashSet实现原理的源码细节。在分析源码之前,首先我们需要对HashSet有一个基本的理解。

853
来自专栏Java爬坑系列

【Java入门提高篇】Day24 Java容器类详解(七)HashMap源码分析(下)

953
来自专栏King_3的技术专栏

leetcode-80-删除排序数组中的重复项 II

给定一个排序数组,你需要在原地删除重复出现的元素,使得每个元素最多出现两次,返回移除后数组的新长度。

841
来自专栏LIN_ZONE

java 算法中常见的问题总结1(代码实现,不包含逻辑)

详情参考  http://www.cnblogs.com/nayitian/p/3214178.html

773
来自专栏小筱月

嵌套数组的合并,扁平化数组

- 对于 [ [], [], [], ...] 数组里嵌套数组,有个需求:将里面的数组元素都放到外层数组,变成 [ , , , ...]

562
来自专栏后端之路

可重复key的HashMap

碰到一些需求需要放入可重复key的HashMap,比如Excel需要报错的行号。 那么如果对象实现过hashCode方法和equals 那么放入到hashMap...

2149
来自专栏salesforce零基础学习

salesforce零基础学习(七十八)线性表链形结构简单实现

前两篇内容为栈和队列的顺序结构的实现,栈和队列都是特殊的线性表,线性表除了有顺序结构以外,还有线性结构。 一.线性表的链形结构--链表 使用顺序存储结构好处为实...

2050
来自专栏小樱的经验随笔

洛谷 P1308 统计单词数【字符串+模拟】

P1308 统计单词数 题目描述 一般的文本编辑器都有查找单词的功能,该功能可以快速定位特定单词在文章中的位置,有的还能统计出特定单词在文章中出现的次数。 现在...

2695
来自专栏Golang语言社区

厚土Go学习笔记 | 28. go语言没有类 却可以在结构体或任意类型定义方法

在go语言中没有类。可是,是有方法的。 给结构体定义方法,在对应的 func 和方法名之间,加上方法的接收者就可以了。 比如,我们定义了一个结构体 type V...

3698
来自专栏测试开发架构之路

C语言程序设计50例(一)(经典收藏)

【程序1】 题目:有1、2、3、4个数字,能组成多少个互不相同且无重复数字的三位数?都是多少? 1.程序分析:可填在百位、十位、个位的数字都是1、2、3、4。组...

3297

扫码关注云+社区