LinkedList源码解析(2)

这篇记录下LinkedList的迭代器实现。 LinkedList的源码内记录了两种迭代器ListIterator和DescendingIterator，一开始很奇怪，平常用的Iterator迭代器实现却没看到，后面看了LinkedList的继承关系才知道答案。

public class LinkedList<E> extends AbstractSequentialList<E> implements List<E>, Deque<E>, Cloneable, java.io.Serializable

LinkedList继承自AbstractSequentialList，里面有了Iterator迭代器的实现：

public Iterator<E> iterator() { return listIterator(); }

它调用的也是ListIterator的迭代器实现，被LinkedList重写了实现。 所以这里直接先讲下ListIterator的实现：

public ListIterator<E> listIterator(int index) { checkPositionIndex(index); return new ListItr(index); } private class ListItr implements ListIterator<E> { private Node<E> lastReturned; private Node<E> next; private int nextIndex; private int expectedModCount = modCount; ListItr(int index) { // assert isPositionIndex(index); next = (index == size) ? null : node(index); nextIndex = index; } public boolean hasNext() { return nextIndex < size; } public E next() { checkForComodification(); if (!hasNext()) throw new NoSuchElementException(); lastReturned = next; next = next.next; nextIndex++; return lastReturned.item; } 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; } public int nextIndex() { return nextIndex; } public int previousIndex() { return nextIndex - 1; } 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++; } public void set(E e) { if (lastReturned == null) throw new IllegalStateException(); checkForComodification(); lastReturned.item = e; } public void add(E e) { checkForComodification(); lastReturned = null; if (next == null) linkLast(e); else linkBefore(e, next); nextIndex++; expectedModCount++; } public void forEachRemaining(Consumer<? super E> action) { Objects.requireNonNull(action); while (modCount == expectedModCount && nextIndex < size) { action.accept(next.item); lastReturned = next; next = next.next; nextIndex++; } checkForComodification(); } final void checkForComodification() { if (modCount != expectedModCount) throw new ConcurrentModificationException(); } }

这里有两点注意下：

在按链表顺序遍历和逆链表顺序迭代上，lastReturned和next代表的意思不同，在顺序遍历时，lastReturned是最近一次返回的元素，next是下一个将要返回的元素；在逆序遍历时，lastReturned和next都表示最近一次返回的元素。由于第一点在remove()方法的实现上做了差异处理。

还有个DescendingIterator迭代器：

public Iterator<E> descendingIterator() { return new DescendingIterator(); } private class DescendingIterator implements Iterator<E> { private final ListItr itr = new ListItr(size()); public boolean hasNext() { return itr.hasPrevious(); } public E next() { return itr.previous(); } public void remove() { itr.remove(); } }

这个迭代器是返回一个迭代器在此双端队列逆向顺序的元素，就是倒着获取元素。