写点什么

LinkedList 源码分析 - 迭代器

作者:zarmnosaj
  • 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;
...... }
复制代码


  1. private Node<E> lastReturned;上一次执行 next() 或者 previos() 方法时的节点位置

  2. private Node<E> next;下一个节点

  3. private int nextIndex;下一个节点的位置

  4. expectedModCount 期望版本号

  5. 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; }
复制代码


  1. return nextIndex < size; 判断下一个节点的索引是否小于链表的大小

  2. checkForComodification(); 检查期望版本号有无发生变化

  3. if (!hasNext()) throw new NoSuchElementException(); 再次检查

  4. lastReturned = next;next 表示当前节点,在上一次执行 next() 方法时被赋值。第一次执行时在初始化迭代器的时候被赋值的

  5. next = next.next;next 是下一个节点

  6. 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; }
复制代码


  1. 第一次迭代,next 为空,取尾节点 last

  2. lastReturned = next = (next == null) ? last : next.prev;已经发生过迭代,next 不为空,直接取前一个节点 next.prev 即可

  3. 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++; }
复制代码


  1. if (lastReturned == null) throw new IllegalStateException(); Node<E> lastNext = lastReturned.next; lastReturned 是本次迭代需要删除的值,分为非空和空的情况:

  2. lastReturned 为空,没有主动执行过 next() 或者 previos(),直接报错

  3. lastReturned 不为空,上次执行 next() 或者 previos()方法时赋的值

  4. unlink(lastReturned); 删除当前节点

  5. if (next == lastReturned)从尾到头遍历顺序,并且是第一次迭代且要删除最后一个元素,previous() 方法里面设置了 lastReturned = next = last,所以 next 和 lastReturned 会相等

  6. next = lastNext; lastReturned 是尾节点,lastNext 是 null,所以 next 也是 null,在 previous() 方法中发现 next 是 null,就会把尾节点赋值给 next

用户头像

zarmnosaj

关注

还未添加个人签名 2020.02.06 加入

还未添加个人简介

评论

发布
暂无评论
LinkedList 源码分析-迭代器_5 月月更_zarmnosaj_InfoQ写作社区