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 条评论
登录 后参与评论

相关文章

来自专栏java思维导图

【一分钟知识】HashSet和TreeSet,HashMap与HashTable

java思维导图 xmind导图配合精美文章,可视化学习,让java不再难懂。 ? ? HashSet和TreeSet HashSet 哈希表实现的,HashS...

3637
来自专栏xingoo, 一个梦想做发明家的程序员

20120918-向量实现《数据结构与算法分析》

#include <iostream> #include <list> #include <string> #include <vector> #include...

2266
来自专栏计算机视觉与深度学习基础

Leetcode 215. Kth Largest Element in an Array

Find the kth largest element in an unsorted array. Note that it is the kth larg...

22210
来自专栏一英里广度一英寸深度的学习

二叉树的深度优先遍历与广度优先遍历

先遍历子节点,再遍历兄弟节点。 从根节点开始递归,如果存在子节点,继续遍历子节点。

6833
来自专栏一个会写诗的程序员的博客

FastJson中@JSONField注解使用FastJson中@JSONField注解使用

如果json格式数据不符合Java中的标准驼峰式变量定义规则,并且难以理解,这个时候就需要在后台中做二次处理,将数据处理成我们系统中定义的格式。

1633
来自专栏软件开发 -- 分享 互助 成长

为什么无返回值的链表的插入操作头结点一定要用指向指针的指针

前言: 为什么链表的插入操作头结点一定要用指向指针的指针?之前自己对这个问题总是一知半解,今天终于花了点时间彻底搞懂了。 总的来说这样做的目的是为了应对“空链表...

2387
来自专栏青玉伏案

算法与数据结构(一) 线性表的顺序存储与链式存储(Swift版)

温故而知新,在接下来的几篇博客中,将会系统的对数据结构的相关内容进行回顾并总结。数据结构乃编程的基础呢,还是要不时拿出来翻一翻回顾一下。当然数据结构相关博客中我...

2147
来自专栏java工会

面试官最喜欢问的十道java面试题

2018
来自专栏数据结构与算法

洛谷P3380 【模板】二逼平衡树(树套树)

您需要写一种数据结构(可参考题目标题),来维护一个有序数列,其中需要提供以下操作:

2893
来自专栏项勇

笔记72 | 将姓放在名的后面,排序按姓氏首字母排列的修改笔记

1865

扫码关注云+社区

领取腾讯云代金券