List集合之LinkedList（二）通过源码看迭代器实现

蔚落 2023-10-04 09:34 11阅读 0赞

# 思维导图 #

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FmY18xMjgyMjA_size_16_color_FFFFFF_t_70][]

***(以下源码来自jdk1.8.0\_282)***

# ListIterator迭代器 #

## ListIterator<E> listIterator(int index) ##

public ListIterator<E> listIterator(int index) {
            checkPositionIndex(index);
            return new ListItr(index);
        }
    
        private void checkPositionIndex(int index) {
            if (!isPositionIndex(index))
                throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
        }
    
        /**
         * Tells if the argument is the index of a valid position for an
         * iterator or an add operation.
         */
        private boolean isPositionIndex(int index) {
            return index >= 0 && index <= size;
        }

ListIterator<E> listIterator(int index)

该方法用于生成一个迭代器，且该迭代器下一个将要迭代的节点索引是index。index范围是\[0,size\]

该方法返回值 new ListItr(index)。

### ListItr类 ###

ListItr类是LinkedList的私有成员内部类，它实现类ListIterator接口，所以要重写ListIterator中的抽象方法。

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;
            }
    
            //...省略ListItr内部类方法，到后面具体一一解析
        }

该类成员有：

*  成员变量

> lastReturned：表示正在被迭代的链表节点。默认初始化为null。
> 
> next：表示将要被迭代的链表节点。默认初始化为null。
> 
> nextIndex：用于记录next成员变量所代表节点的索引值。默认初始化为0。
> 
> expectedModCount：该变量用于记录集合创建迭代器时，集合对象modCount属性值。用于帮助迭代器在迭代过程中检查集合对象的modCount是否发生改变，若改变则fail-fast。

*  构造器

> 该类只有一个构造器：ListItr(int index)
> 
> 该构造器用于完成对next，nextIndex成员变量的初始化。即由外部指定迭代器初始时将要迭代的节点。
> 
> next = (index == size) ? null : node(index);//当index指定为size，即表示指定的将要迭代的节点是尾节点（size-1）后面的节点，即为null。否则将要迭代的节点就是node(index)节点。
> 
> nextIndex = index;//nextIndex就是next节点的索引，即这里由外部指定的index

*  公开方法

hasNext()

public boolean hasNext() {
                return nextIndex < size;
            }

> 该方法用于判断迭代器将要迭代的元素是否存在。存在就返回true,不存在就返回false。
> 
> 内部实现是根据 return nextIndex < size ;
> 
> 我们知道当迭代到尾节点时，即 lastReturned = last , next = null ，即 nextIndex = size
> 
> 这就是迭代器的正向最后一次迭代，到此次后，无法继续迭代。

next()

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

> 该方法操作前需要检查并发修改异常。
> 
> 该方法操作前需要检查将要迭代的节点是否存在，若不存在，则无法迭代到不存在的节点上，会抛出无此元素异常。
> 
> 该方法用于 返回本次迭代中，将要迭代节点的元素。
> 
> 迭代器总是将lastRetruned指向的节点的元素返回。
> 
> 所以想要返回将要被迭代的元素，则需要让lastReturned指向next节点。即lastReturned = next;
> 
> 此时本次迭代正在迭代的元素已经是next指向的节点元素了。所以next要指向下次将要迭代的节点。即next = next.next;
> 
> nextIndex++;表示将要迭代节点的索引+1。

hasPrevoius()

public boolean hasPrevious() {
                return nextIndex > 0;
            }

> 该方法是指将要被迭代的节点的上一个节点是否存在。
> 
> 内部实现是：return nextIndex>0;
> 
> 我们知道当迭代器向前迭代到头节点时：lastReturn = first , next = first ,此时nextIndex = 0
> 
> 即这是迭代器反向迭代的最后一次迭代，无法继续向前迭代了。

previous()

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

> 该方法操作前需要检查并发修改异常。
> 
> 该方法操作前需要检查将要被迭代节点的上一个节点是否存在，若不存在，则无法迭代到一个不存在的节点上，会抛出无此元素异常。
> 
> 该方法用于获取将要被迭代节点的上一个节点的元素。
> 
> 迭代器总是将lastRetruned指向的节点的元素返回。
> 
> 所以需要把将要被迭代节点的上一个节点赋值给lastReturned。即lastReturned = next.prev
> 
> 由于next节点索引只能是\[0,size\],而在previous()操作前判断了hasPrevious(),所以next节点的索引只能是\[1,size\]
> 
> 则此时会出现一种极端情况，即nextIndex == size时，即next的上一个节点是尾节点，但是此时next本身为null，null对象无法调用prev实例变量。所以需要特殊指定下当next==null时，lastReturned = last。

nextIndex()

public int nextIndex() {
                return nextIndex;
            }

> nextIndex()方法获取nextIndex值。

previousIndex()

public int previousIndex() {
                return nextIndex - 1;
            }

> previousIndex()获取nextIndex-1值。

remove()

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++;
            }

> 该方法操作前需要检查并发修改异常。
> 
> 该方法用于删除lastReturned指向的节点。如果lastReturned是null，则无法删除不存在的节点，抛出非法状态异常。
> 
> 由于该方法会调用集合的unlink方法，所以集合对象会被结构化修改。为了不影响后续迭代操作，需要将expectedModCount++
> 
> 由于要删除掉lastRetruned节点，所以lastReturned的下一个节点
> 
> 1.需要断开与lastReturned节点的联系；
> 
> 2.需要建立于lastReturned节点前一个节点的联系
> 
> 这两步操作可以使用LinkedList的unlink(Node node)方法。
> 
> 由于previous()操作会导致lastReturned和next指向同一个节点，所以当next == lastReturned时，next指向的节点会被删除掉，next需要重新指向相同索引位置的节点，即lastReturned.next,即lastNext
> 
> 如果next和lastReturned没有指向同一个节点，则删除lastReturned指向的节点不影响next节点指向，只是会影响next节点的索引，即nextIndex--
> 
> 而执行删除操作后：lastReturned 执行节点已经被删除，所以lastReturned已经没有指向的节点。所以将lastReturned重置为null

add(E e)

public void add(E e) {
                checkForComodification();
                lastReturned = null;
                if (next == null)
                    linkLast(e);
                else
                    linkBefore(e, next);
                nextIndex++;
                expectedModCount++;
            }

> 该方法操作前需要检查并发修改异常。
> 
> 由于该方法会调用集合的link方法，所以集合对象会被结构化修改。为了不影响后续迭代操作，需要将expectedModCount++
> 
> add,remove操作会导致lastReturned被重置为null。
> 
> 该方法是将e元素（创建对应节点）插入到链表的nextIndex索引处。
> 
> 如果next是在尾节点后面，则e接单插入到链表尾部
> 
> 如果next不在尾节点后面，则e节点插入到next节点前面。即linkBefore(e,next)
> 
> 插入后，next节点索引+1，即nextIndex++

set(E e)

public void set(E e) {
                if (lastReturned == null)
                    throw new IllegalStateException();
                checkForComodification();
                lastReturned.item = e;
            }

> 该方法用于将lastReturned指向节点的元素改为e

foreachRemaining(Consumer)

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();
            }

> 该方法用于遍历剩余节点，并处理节点中元素。
> 
> 遍历时需要检查并发修改异常。

## ListIterator<E> listIterator() ##

public ListIterator<E> listIterator() {
            return listIterator(0);
        }

ListIterator<E> listIterator()该方法是LinkedList继承自超类AbstractList的方法

内部实现:return listIterator(0);

而listIterator(0) 方法并不是调用的AbstractList类中方法，而是调用的被子类LinkedList重写的listIterator(int index)。

所以该方法返回的迭代器本质和LinkedList中 ListIterator listIterator(int index) 方法返回的迭代器一样，只是该方法指定了迭代器的初始将要迭代的节点索引是0，即next是first

# Iterator迭代器 #

## Iterator<E> iterator() ##

/* AbstractSequentialList */   
       /**
         * Returns an iterator over the elements in this list (in proper
         * sequence).<p>
         *
         * This implementation merely returns a list iterator over the list.
         *
         * @return an iterator over the elements in this list (in proper sequence)
         */
        public Iterator<E> iterator() {
            return listIterator();
        }
    
    
    
        /* AbstractList */
        /**
         * {@inheritDoc}
         *
         * <p>This implementation returns {@code listIterator(0)}.
         *
         * @see #listIterator(int)
         */
        public ListIterator<E> listIterator() {
            return listIterator(0);
        }

通过以上代码，可以发现LinkedList的iterator()方法继承自AbstractSequentialList，

而AbstractSequentialList的iterator方法实现是调用了listIterator(),listIterator()又是继承自AbstractList的。

而AbstractList的listIterator()方法实现是调用了listIterator(int index),但是listIterator（int index）方法已经被AbstractList的间接子类LinkedList重写了，

所以AbstractList的listIterator()方法最终还是调用了LinkedList的

ListIterator<E> listIterator(int index)，且index传值为0。

## Iterator<E> descendingIterator() ##

/**
         * @since 1.6
         */
        public Iterator<E> descendingIterator() {
            return new DescendingIterator();
        }

该方法的返回值是 new DescendingIterator()

### DescendingIterator类 ###

/**
         * Adapter to provide descending iterators via ListItr.previous
         */
        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();
            }
        }

该类是LinkedList的私有成员内部类。

该类没有采用继承ListItr类的方式来复用ListItr的内部实现。而是采用组合的方式，定义了一个ListItr类对象itr。

创建itr时，指定了迭代器的初始将要迭代节点索引为size。即链表尾节点后面的位置。

该类只提供了三个方法，hasNext(),next().remove(），它们的实现分别复用了ListItr类的hasPrevious(),previous(),remove()。

另外该类实现了Iterator接口，所以可以使用Iterator接口中的默认方法foreachRemaining(Consumer consumer)

可以看出：

如果将ListItr类的hasNext(),next()看成时正向迭代中的判断是否有下一个节点，获取下一个节点的元素

那么就可以将DescendingIterator类的hasNext(),next()看成逆向迭代中判断是否又下一个节点，获取下一个节点的元素。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FmY18xMjgyMjA_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20210330191246897.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FmY18xMjgyMjA=,size_16,color_FFFFFF,t_70