List列表集合，Iterator迭代器-Java8源码教会你正确的使用方式

ArrayList集合

ArrayList集合在java中，是基于数组实现，get(i)查询操作时间复杂度为O(1)。其特性如下：

1. add新增和remove操作存在潜在的昂贵时间花销。对数组中某个元素（非尾元素）进行add和remove操作，该元素后的所有元素会进行整体移动操作。
2. 执行add添加操作时，当添加元素的个数大于集合容量，arraylist会进行扩容处理，重新创建原始容量2倍大小的数组，然后进行数据复制操作。

arraylist侧重查询操作，在使用时，最好初始化使用的容量，避免频繁地进行add和remove操作。其源码如下：

public class ArrayList<E> extends AbstractList<E>
        implements List<E>, RandomAccess, Cloneable, java.io.Serializable
{

    /**
     * 默认初始化大小
     */
    private static final int DEFAULT_CAPACITY = 10;

    /**
     * 存储集合元素地数组
     */
    transient Object[] elementData; // non-private to simplify nested class access

    /**
     * 添加元素
     */
    public boolean add(E e) {
        ensureCapacityInternal(size + 1);  // Increments modCount!!
        elementData[size++] = e;
        return true;
    }

    /**
     *在添加元素时，如果个数大于数组容量，则调用此方法进行数组扩容，并且拷贝数组到新创建的数组
     */
    private void grow(int minCapacity) {
        // overflow-conscious code
        int oldCapacity = elementData.length;
        int newCapacity = oldCapacity + (oldCapacity >> 1);
        if (newCapacity - minCapacity < 0)
            newCapacity = minCapacity;
        if (newCapacity - MAX_ARRAY_SIZE > 0)
            newCapacity = hugeCapacity(minCapacity);
        // minCapacity is usually close to size, so this is a win:
        elementData = Arrays.copyOf(elementData, newCapacity);
    }


    /**
     * 在指定index位置添加新的元素后，此index以后的元素会整体地往后移动
     */
    public void add(int index, E element) {
        rangeCheckForAdd(index);

        ensureCapacityInternal(size + 1);  // Increments modCount!!
        System.arraycopy(elementData, index, elementData, index + 1,
                         size - index);
        elementData[index] = element;
        size++;
    }
    
   /**
     * 删除指定index的元素，此index以后的元素会整体地往前移动
     */
    public E remove(int index) {
        rangeCheck(index);

        modCount++;
        E oldValue = elementData(index);

        int numMoved = size - index - 1;
        if (numMoved > 0)
            System.arraycopy(elementData, index+1, elementData, index,
                             numMoved);
        elementData[--size] = null; // clear to let GC do its work

        return oldValue;
    }
}

LinkedList集合

LinkedList集合在java中，基于双向链表实现，可以基于集合首元素和尾元素进行操作。其特性如下：

1. 对于get(i)的查询操作，时间复杂度为O(n)。
2. 对于已知指定位置的元素进行add和remove操作，时间复杂度为常数。

linkedlist侧重与对集合进行add和remove操作偏多的场景。需要添加数量比较大的元素的场景，由于节点不连续，原理上是可以存储内存可以允许的最大量的数据。其源码如下：

public class LinkedList<E>
    extends AbstractSequentialList<E>
    implements List<E>, Deque<E>, Cloneable, java.io.Serializable
{
    transient int size = 0;

    /**
     *首节点
     */
    transient Node<E> first;

    /**
     * 尾节点
     */
    transient Node<E> last;

    /**
     * 添加元素
     */
    public boolean add(E e) {
        linkLast(e);
        return true;
    }

    /**
     * Links e as last element.
     */
    void linkLast(E e) {
        final Node<E> l = last;
        final Node<E> newNode = new Node<>(l, e, null);
        last = newNode;
        if (l == null)
            first = newNode;
        else
            l.next = newNode;
        size++;
        modCount++;
    }

    /**
     * 先从first节点开始遍历，待删除元素，找到后再执行删除操作
     * 删除操作是常数时间，但是，有个查询的时间
     */
    public boolean remove(Object o) {
        if (o == null) {
            for (Node<E> x = first; x != null; x = x.next) {
                if (x.item == null) {
                    unlink(x);
                    return true;
                }
            }
        } else {
            for (Node<E> x = first; x != null; x = x.next) {
                if (o.equals(x.item)) {
                    unlink(x);
                    return true;
                }
            }
        }
        return false;
    }

    /**
     * Node节点的定义了双链表结构，next下一个元素，prev前一个元素
     */
    private static class Node<E> {
        E item;
        Node<E> next;
        Node<E> prev;

        Node(Node<E> prev, E element, Node<E> next) {
            this.item = element;
            this.next = next;
            this.prev = prev;
        }
    }

}

Iterator迭代器

Iterator迭代器，主要定义了一个当前元素的概念，该元素由next()返回；并提供了for循环增强。java中，对正在被迭代的集合进行结构上的改变，例如对正在进行for循环遍历的集合进行add，remove或clear操作，那么该迭代器会抛出ConcurrentModificationException。但是，对于Iterator迭代器next()方法返回的元素，执行remove方法就不会报错，并且其时间复杂对为常数。针对于集合的remove操作，特别是对于arraylist或linked集合中的remove操作，都会存在一个查询到指定删除元素的运行时间消耗。

当对linkedlist列表，进行遍历删除指定条件的元素的操作，最适合使用Iterator迭代器的next()获取元素，然后再执行remove方法。其接口定义如下：

public interface Iterator<E> {

    boolean hasNext();

    E next();

    default void remove() {
        throw new UnsupportedOperationException("remove");
    }
}

ListIterator迭代器

ListIterator迭代器继承于Iterator，是功能上的增加。增加了previous()方法，以及set和add方法。对于linkedlist集合中，遍历集合对于满足指定条件的元素进行修改，添加新增元素或者删除操作，特别适合适用ListIterator迭代器实现。其接口定义如下：

public interface ListIterator<E> extends Iterator<E> {

    /**
     * 下一个元素
     */
    E next();

    /**
     * 前一个元素
     */
    E previous();


    /**
     * 删除当前位置元素
     */
    void remove();

    /**
     * 在当前元素位置修改元素
     */
    void set(E e);

    /**
     * 在当前元素位置添加新的元素
     */
    void add(E e);
}