LinkedList 源码分析 - 迭代器
LinkedList 源码分析-迭代器
LinkedList 中使用的迭代器是:ListIterator(Iterator 只支持从头到尾的访问),这个迭代器提供了向前和向后的迭代方法。
ListIterator 的主要方法:hasPrevious(),previous(),previousIndex() --> 从尾到头迭代方法 hasNext(),next(),nextIndex() --> 从头到尾迭代方法
迭代器
基础结构源码:
private Node<E> lastReturned;
上一次执行 next() 或者 previos() 方法时的节点位置private Node<E> next;
下一个节点private int nextIndex;
下一个节点的位置expectedModCount
期望版本号modCount
目前最新版本号
从头到尾方向的迭代:
源码:
return nextIndex < size;
判断下一个节点的索引是否小于链表的大小checkForComodification();
检查期望版本号有无发生变化if (!hasNext()) throw new NoSuchElementException();
再次检查lastReturned = next;
next 表示当前节点,在上一次执行 next() 方法时被赋值。第一次执行时在初始化迭代器的时候被赋值的next = next.next;
next 是下一个节点nextIndex++;
为下次迭代做准备
从尾到头迭代
源码:
第一次迭代,next 为空,取尾节点 last
lastReturned = next = (next == null) ? last : next.prev;
已经发生过迭代,next 不为空,直接取前一个节点 next.prev 即可nextIndex--;
索引位置变化
删除
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
评论