ListIterator的LinkedList实现

源码来自jdk1.8

---

对于实现了List接口的集合类，他们的iterator都是通过实现ListIterator接口得到的，每个集合类都有自己的ListIterator实现，这里给出LinkedList的实现：

private class ListItr implements ListIterator<E> {
    private Node<E> lastReturned;
    private Node<E> next;
    private int nextIndex;
    private int expectedModCount = modCount;
    //省略了方法
}

lastReturned和next说明了迭代器一直处于元素之间的位置，lastReturned代表了上次访问过的元素，next表示下一个要访问的元素，由于可以向前迭代，所以这两个可以是同一个节点。

hasNext / next

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

        public E next() {
            checkForComodification();
            if (!hasNext())
                throw new NoSuchElementException();

            lastReturned = next;
            next = next.next;
            nextIndex++;
            return lastReturned.item;
        }

通过节点的next域在链表中迭代

remove

每次删除lastReturned节点，然后lastReturned置空，所以不能连续两次调用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++;
    }

set与remove类似，修改lastReturned。

checkForComodification

如果迭代器发现它的集合被另一个迭代器或是集合自身的方法修改（添加／删除元素）了，抛出一个ConcurrentModificationException（fast－fail快速失败）。实现方法是集合与迭代器分别维护一个独立的集合改写次数，每个迭代器方法开始的地方都检查数值是否一致，迭代器自身的修改方法会增加自己以及集合的修改次数，而集合本身的方法只会增加集合的修改次数。

final void checkForComodification() {
    if (modCount != expectedModCount)
        throw new ConcurrentModificationException();
}

这个特性在使用foreach（内部使用iterator实现）时也会触发，例如

foreach(element e: list){
    if(condition){
        list.remove(e);
    }
};

所以需要使用iterator自己的remove来对容器进行修改：

Iterator<Element> e = list.iterator();  
while(e.hasNext()){  
    Element element = e.next();
    if(condition){
        e.remove();
    }
}

add

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

通过迭代器添加节点