LinkedList 源码分析 - 迭代器

2022 年 5 月 21 日
本文字数：1546 字
阅读完需：约 5 分钟

LinkedList 源码分析-迭代器

LinkedList 中使用的迭代器是：ListIterator（Iterator 只支持从头到尾的访问），这个迭代器提供了向前和向后的迭代方法。

ListIterator 的主要方法：hasPrevious()，previous()，previousIndex() --> 从尾到头迭代方法 hasNext()，next()，nextIndex() --> 从头到尾迭代方法

迭代器

基础结构源码：

    private class ListItr implements ListIterator<E> {        private Node<E> lastReturned;        private Node<E> next;        private int nextIndex;        private int expectedModCount = modCount;
        ......    }

复制代码

private Node<E> lastReturned;上一次执行 next() 或者 previos() 方法时的节点位置
private Node<E> next;下一个节点
private int nextIndex;下一个节点的位置
expectedModCount 期望版本号
modCount 目前最新版本号

从头到尾方向的迭代：

源码：

        public boolean hasNext() {            return nextIndex < size;        }
        public E next() {            checkForComodification();            if (!hasNext())                throw new NoSuchElementException();
            lastReturned = next;            next = next.next;            nextIndex++;            return lastReturned.item;        }

复制代码

return nextIndex < size; 判断下一个节点的索引是否小于链表的大小
checkForComodification(); 检查期望版本号有无发生变化
if (!hasNext()) throw new NoSuchElementException(); 再次检查
lastReturned = next;next 表示当前节点，在上一次执行 next() 方法时被赋值。第一次执行时在初始化迭代器的时候被赋值的
next = next.next;next 是下一个节点
nextIndex++;为下次迭代做准备

从尾到头迭代

源码：

        public boolean hasPrevious() {            return nextIndex > 0;        }
        public E previous() {            checkForComodification();            if (!hasPrevious())                throw new NoSuchElementException();
            lastReturned = next = (next == null) ? last : next.prev;            nextIndex--;            return lastReturned.item;        }

复制代码

第一次迭代，next 为空，取尾节点 last
lastReturned = next = (next == null) ? last : next.prev;已经发生过迭代，next 不为空，直接取前一个节点 next.prev 即可
nextIndex--; 索引位置变化

删除

        public void remove() {            checkForComodification();            if (lastReturned == null)                throw new IllegalStateException();
            Node<E> lastNext = lastReturned.next;            unlink(lastReturned);            if (next == lastReturned)                next = lastNext;            else                nextIndex--;            lastReturned = null;            expectedModCount++;        }

复制代码

if (lastReturned == null) throw new IllegalStateException(); Node<E> lastNext = lastReturned.next; lastReturned 是本次迭代需要删除的值，分为非空和空的情况：
lastReturned 为空，没有主动执行过 next() 或者 previos()，直接报错
lastReturned 不为空，上次执行 next() 或者 previos()方法时赋的值
unlink(lastReturned); 删除当前节点
if (next == lastReturned)从尾到头遍历顺序，并且是第一次迭代且要删除最后一个元素，previous() 方法里面设置了 lastReturned = next = last,所以 next 和 lastReturned 会相等
next = lastNext; lastReturned 是尾节点，lastNext 是 null，所以 next 也是 null，在 previous() 方法中发现 next 是 null，就会把尾节点赋值给 next

发布于: 刚刚阅读数: 3

zarmnosaj

关注

还未添加个人签名 2020.02.06 加入

还未添加个人简介

发布

暂无评论

创作场景

LinkedList 源码分析 - 迭代器

LinkedList 源码分析-迭代器

迭代器

从头到尾方向的迭代：

从尾到头迭代

删除

zarmnosaj

评论