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

  
    private static final int DEFAULT_CAPACITY = 10;    //默认容量为10

    private static final Object[] EMPTY_ELEMENTDATA = {};   

    private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};   

  
    transient Object[] elementData; // non-private to simplify nested class access

    private int size;             //ArrayList的实际大小


    public ArrayList(int initialCapacity) {              //构造方法一，输入一个表示ArrayList容量的参数，
        if (initialCapacity > 0) {
            this.elementData = new Object[initialCapacity];
        } else if (initialCapacity == 0) {
            this.elementData = EMPTY_ELEMENTDATA;
        } else {
            throw new IllegalArgumentException("Illegal Capacity: "+
                                               initialCapacity);
        }
    }

    

    public ArrayList() {　　　　　　　　　　　　　　　　　　　　　　　　//构造方法二，直接初始化一个Object型的数组　　
        this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
    }

   

    public ArrayList(Collection<? extends E> c) {            //构造方法三，将一个Collection集合中的元素加载进ArrayList中
        elementData = c.toArray();
        if ((size = elementData.length) != 0) {
            // defend against c.toArray (incorrectly) not returning Object[]
            // (see e.g. https://bugs.openjdk.java.net/browse/JDK-6260652)
            if (elementData.getClass() != Object[].class)
                elementData = Arrays.copyOf(elementData, size, Object[].class);
        } else {
            // replace with empty array.
            this.elementData = EMPTY_ELEMENTDATA;
        }
    }

/* ArrayList 添加元素，当容量不足时需要调用 grow（）进行扩容，新容量的大小为 oldCapacity + (oldCapacity >> 1，
* 也就是原来的1.5倍，扩容需要调用一次Arrays.copyOf()复制原数组，这个操作代价很高，
* 所以最好在初始化时就指定容量，减少扩容操作的次数。
*/

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

private void ensureCapacityInternal(int minCapacity) {
    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
    }
    ensureExplicitCapacity(minCapacity);
}

private void ensureExplicitCapacity(int minCapacity) {
    modCount++;
    // overflow-conscious code
    if (minCapacity - elementData.length > 0)
        grow(minCapacity);
}

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

// 删除指定位置的元素
// 需要调用 System.arraycopy() 将 index+1 后面的元素都复制到 index 位置上
// 可以看出 ArrayList 删除元素的代价是非常高的。

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

//删除指定类型的元素，从头遍历

public boolean remove(Object o) {
        if (o == null) {
            for (int index = 0; index < size; index++)
                if (elementData[index] == null) {
                    fastRemove(index);
                    return true;
                }
        } else {
            for (int index = 0; index < size; index++)
                if (o.equals(elementData[index])) {
                    fastRemove(index);
                    return true;
                }
        }
        return false;
    }

//  节点 Node 类，这说明我们使用的实际上是一个双向链表，

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

//构造方法：比ArrayList更灵活，不需要考虑初始的数组容量
//
public LinkedList() {
    }

public LinkedList(Collection<? extends E> c) {
        this();
        addAll(c);
    }

// 增
// 无论在头还是在尾添加元素，都会一直维护first ,last 两个指针指向链表的头尾，
private void linkFirst(E e) {
        final Node<E> f = first;
        final Node<E> newNode = new Node<>(null, e, f);
        first = newNode;
        if (f == null)
            last = newNode;
        else
            f.prev = newNode;
        size++;
        modCount++;
    }

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

// 删
// 通过将待删除结点的前一节点指向待删除节点的后一个即可完成，
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;
    }

unlink(Node<E> x) {
        // assert x != null;
        final E element = x.item;
        final Node<E> next = x.next;
        final Node<E> prev = x.prev;

        if (prev == null) {
            first = next;
        } else {
            prev.next = next;
            x.prev = null;
        }

        if (next == null) {
            last = prev;
        } else {
            next.prev = prev;
            x.next = null;
        }

        x.item = null;
        size--;
        modCount++;
        return element;
    }

public static void main(String[] args) {
        // write your code here
        int[] nums = {1,2,3,4,5,6,7,8};
        LinkedList<Integer> list = new LinkedList<>();
        for(int each:nums){
            list.add(each);
        }
        System.out.println(list);
        Iterator<Integer> it = list.iterator();
        while(it.hasNext()){
            if(it.next()%2==0){
                it.remove();
            }
        }
        System.out.println(list);
    }