public class ArrayList<E> extends AbstractList<E>
        implements List<E>, RandomAccess, Cloneable, java.io.Serializable
{
    // 版本号
    private static final long serialVersionUID = 8683452581122892189L;
    // 缺省容量
    private static final int DEFAULT_CAPACITY = 10;
    // 空对象数组
    private static final Object[] EMPTY_ELEMENTDATA = {};
    // 缺省空对象数组
    private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
    // 元素数组
    transient Object[] elementData;
    // 实际元素大小，默认为0
    private int size;
    // 最大数组容量
    private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
}

/*
*Constructs an empty list with an initial capacity of ten.　　
*这里就说明了默认会给10的大小，所以说一开始arrayList的容量是10.
*/
//ArrayList中储存数据的其实就是一个数组，这个数组就是elementData，
//在123行定义的 private transient Object[] elementData;
public ArrayList() {　　
    super();        
    //调用父类中的无参构造方法，父类中的是个空的构造方法
    this.elementData = EMPTY_ELEMENTDATA;
    //EMPTY_ELEMENTDATA：是个空的Object[]， 将elementData初始化，
    	 //elementData也是个Object[]类型。空的Object[]会给默认大小10
}

public ArrayList(int initialCapacity) {
    super(); //父类中空的构造方法
    if (initialCapacity < 0)    
    //判断如果自定义大小的容量小于0，则报下面这个非法数据异常
        throw new IllegalArgumentException("Illegal Capacity: "+
                                           initialCapacity);
    this.elementData = new Object[initialCapacity]; 
    //将自定义的容量大小当成初始化elementData的大小
}

/**
* 把元素添加到集合的末尾
*/
public boolean add(E e) {
    
    //确定数组容量是否足够，size是数据个数，所以+1. 
    ensureCapacityInternal(size + 1); 
    
    //在数组中正确的位置上添加元素e，并size++
    elementData[size++] = e;
    
    return true;
}

//用于确定数组容量
private void ensureCapacityInternal(int minCapacity) {
    
    //判断初始化elementdata是否为一个空数组
    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        
        //如果是，相当于是空数组没有长度，则获取“默认的容量”和“传入参数”两者之间的最大值
        minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);

    }
    //确认实际的容量，判断是否需要进行扩容操作
    ensureExplicitCapacity(minCapacity);
}

//判断是否需要扩容
private void ensureExplicitCapacity(int minCapacity) {
    //记录修改次数
    modCount++;

    //如果最小大小 减 数组长度 大于0 -> 进行数组扩容
    if (minCapacity - elementData.length > 0)
        //实际进入扩容机制
        grow(minCapacity);
}

/**
* ArrayList扩容的核心方法。
*/
private void grow(int minCapacity) {
     // oldCapacity为旧容量，newCapacity为新容量
    
    //将扩充前的elementData大小给oldCapacity
    int oldCapacity = elementData.length;
	
    //将oldCapacity 右移一位，其效果相当于oldCapacity/2
    //newCapacity就是1.5倍的oldCapacity
    int newCapacity = oldCapacity + (oldCapacity >> 1);

     //检查新容量是否大于最小需要容量，若小于最小需要容量，那么就把最小需要容量当作数组的新容量
    if (newCapacity - minCapacity < 0)
        newCapacity = minCapacity;

    /**
     * 检查新容量是否超出了ArrayList所定义的最大容量，
     * 若超出了，则调用hugeCapacity()来比较minCapacity和 MAX_ARRAY_SIZE，
     * 如果minCapacity大于MAX_ARRAY_SIZE，则新容量则为Interger.MAX_VALUE，否则，新容量大小则为 MAX_ARRAY_SIZE。
    */
    if (newCapacity - MAX_ARRAY_SIZE > 0)
        //比较minCapacity和 MAX_ARRAY_SIZE
        newCapacity = hugeCapacity(minCapacity);
    
    //新的容量大小已经确定好了，就copy数组，改变容量大小
    elementData = Arrays.copyOf(elementData, newCapacity);
}

//这个就是上面用到的方法，很简单，就是用来赋最大值。
private static int hugeCapacity(int minCapacity) {
    if (minCapacity < 0) // overflow
        throw new OutOfMemoryError();
    //如果minCapacity都大于MAX_ARRAY_SIZE，那么就Integer.MAX_VALUE返回，反之将MAX_ARRAY_SIZE返回
    return (minCapacity > MAX_ARRAY_SIZE) ？Integer.MAX_VALUE:MAX_ARRAY_SIZE;
}

/**
* 在此列表中的指定位置插入指定的元素。 

*先调用 rangeCheckForAdd 对index进行界限检查；然后调用 ensureCapacityInternal 方法保证capacity足够大；

*再将从index开始之后的所有成员后移一个位置；将element插入index位置；最后size加1。
*/
public void add(int index, E element) {
    rangeCheckForAdd(index);

    ensureCapacityInternal(size + 1);  // Increments modCount!!
    
    //arraycopy()方法实现数组自己复制自己
    System.arraycopy(elementData, index, elementData, index + 1,size - index);
    elementData[index] = element;
    size++;
}

private void rangeCheckForAdd(int index) {
    if (index > size || index < 0)   
    //插入的位置肯定不能大于size 和小于0
	 //如果是，就报这个越界异常
    throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}

public E remove(int index) {
    rangeCheck(index);//检查index的合理性

    modCount++;//增加修改次数
    E oldValue = elementData(index);//通过索引直接找到该元素

    int numMoved = size - index - 1;//计算要移动的位数。
    if (numMoved > 0)
        //用来移动元素的。
        System.arraycopy(elementData, index+1, elementData, index,
                         numMoved);
    //将--size上的位置赋值为null，让gc(垃圾回收机制)更快的回收它。
    elementData[--size] = null; // clear to let GC do its work
    //返回删除的元素。
    return oldValue;
}

//通过元素来删除该元素，就依次遍历，如果有这个元素，就将该元素的索引传给fastRemobe(index)，使用这个方法来删除该元素，
//fastRemove(index)方法的内部跟remove(index)的实现几乎一样，这里最主要是知道arrayList可以存储null值
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;
}

public void clear() {
    modCount++;

    // clear to let GC do its work
    for (int i = 0; i < size; i++)
        elementData[i] = null;

    size = 0;
}

public E set(int index, E element) {
    // 检验索引是否合法
    rangeCheck(index);
    // 旧值
    E oldValue = elementData(index);
    // 赋新值
    elementData[index] = element;
    // 返回旧值
    return oldValue;
}

// 从首开始查找数组里面是否存在指定元素
public int indexOf(Object o) {
    if (o == null) { // 查找的元素为空
        for (int i = 0; i < size; i++) 
        // 遍历数组，找到第一个为空的元素，返回下标
            if (elementData[i]==null)
                return i;
    } else { // 查找的元素不为空
        for (int i = 0; i < size; i++) 
        // 遍历数组，找到第一个和指定元素相等的元素，返回下标
            if (o.equals(elementData[i]))
                return i;
    } 
    // 没有找到，返回空
    return -1;
}

public E get(int index) {
    // 检验索引是否合法
    rangeCheck(index);

    return elementData(index);
}

E elementData(int index) {
    return (E) elementData[index];
}

// 实际元素个数，链表长度
transient int size = 0;

// 头结点
transient Node<E> first;

// 尾结点
transient Node<E> last;

public LinkedList() { }

//将集合c中的各个元素构建成LinkedList链表。
public LinkedList(Collection<? extends E> c) {
    // 调用无参构造函数
    this();
    // 添加集合中所有的元素
    addAll(c);
}

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

public boolean add(E e) {
    // 添加到末尾
    linkLast(e);
    return true;
}

/**
     * Links e as last element.
     */
void linkLast(E e) {
    final Node<E> l = last;    
    //临时节点l(L的小写)保存last，也就是l指向了最后一个节点
    final Node<E> newNode = new Node<>(l, e, null);
    //将e封装为节点，并且e.prev指向了最后一个节点
    last = newNode;
    //newNode成为了最后一个节点，所以last指向了它
    if (l == null)    
    //判断是不是一开始链表中就什么都没有，如果没有，则newNode就成为了第一个节点，first和last都要指向它
        first = newNode;
    else 
    //正常的在最后一个节点后追加，那么原先的最后一个节点的next就要指向现在真正的最后一个节点，原先的最后一个节点就变成了倒数第二个节点
        l.next = newNode;
    size++;//添加一个节点，size自增
    modCount++;
}

List<Integer> lists = new LinkedList<Integer>();
lists.add("e1");
lists.add("e2");

//首先通过看上面的注释，我们可以知道，如果我们要移除的值在链表中存在多个一样的值
//那么我们会移除index最小的那个，也就是最先找到的那个值，如果不存在这个值，那么什么也不做
public boolean remove(Object o) {
    //这里可以看到，linkedList也能存储null
    if (o == null) {
        //循环遍历链表，直到找到null值，然后使用unlink移除该值。下面的这个else中也一样
        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;
}

/**
 * Unlinks non-null node x.
 */
//不能传一个null值过，注意，看之前要注意之前的next、prev这些都是谁。
E unlink(Node<E> x) {
    // assert x != null;
//拿到节点x的三个属性
    final E element = x.item;
    final Node<E> next = x.next;
    final Node<E> prev = x.prev;

//这里开始往下就进行移除该元素之后的操作，也就是把指向哪个节点搞定。
    if (prev == null) {
//说明移除的节点是头节点，则first头节点应该指向下一个节点
        first = next;
    } else {
//不是头节点，prev.next=next：有1、2、3，将1.next指向3
        prev.next = next;
//然后解除x节点的前指向。
        x.prev = null;
    }

    if (next == null) {
//说明移除的节点是尾节点
        last = prev;
    } else {
//不是尾节点，有1、2、3，将3.prev指向1. 然后将2.next=解除指向。
        next.prev = prev;
        x.next = null;
    }
//x的前后指向都为null了，也把item为null，让gc回收它
    x.item = null;
    size--;    //移除一个节点，size自减
    modCount++;
    return element;    //由于一开始已经保存了x的值到element，所以返回。
}

//这里没有什么，重点还是在node(index)中
public E get(int index) {
    checkElementIndex(index);
    return node(index).item;
}

/**
 * Returns the (non-null) Node at the specified element index.
 */
//这里查询使用的是先从中间分一半查找
Node<E> node(int index) {
     // assert isElementIndex(index);
     //这个if中就是查询前半部分
     if (index < (size >> 1)) {
        Node<E> x = first;
        for (int i = 0; i < index; i++)
            x = x.next;
        return x;
    } else {
    //前半部分没找到，所以找后半部分
        Node<E> x = last;
        for (int i = size - 1; i > index; i--)
            x = x.prev;
        return x;
    }
}

//这个很简单，就是通过实体元素来查找到该元素在链表中的位置。跟remove中的代码类似，只是返回类型不一样。
public int indexOf(Object o) {
    int index = 0;
    if (o == null) {
        for (Node<E> x = first; x != null; x = x.next) {
            if (x.item == null)
                return index;
            index++;
        }
    } else {
        for (Node<E> x = first; x != null; x = x.next) {
            if (o.equals(x.item))
                return index;
            index++;
        }
    }
    return -1;
}

package java.util;

public class Stack<E> extends Vector<E> {
    private static final long serialVersionUID = 1224463164541339165L;
// 构造函数
public Stack() {
}

// push函数：将元素存入栈顶
public E push(E item) {
    // 将元素存入栈顶。
    // addElement()的实现在Vector.java中
    addElement(item);
    return item;
}

// pop函数：返回栈顶元素，并将其从栈中删除
public synchronized E pop() {
    E   obj;
    int  len = size();
    obj = peek();
    // 删除栈顶元素，removeElementAt()的实现在Vector.java中
    removeElementAt(len - 1);
    return obj;
}

// peek函数：返回栈顶元素，不执行删除操作
public synchronized E peek() {
    int  len = size();
    if (len == 0)
        throw new EmptyStackException();
    // 返回栈顶元素，elementAt()具体实现在Vector.java中
    return elementAt(len - 1);
}

// 栈是否为空
public boolean empty() {
    return size() == 0;
}

// 查找“元素o”在栈中的位置：由栈底向栈顶方向数
public synchronized int search(Object o) {
    // 获取元素索引，elementAt()具体实现在Vector.java中
    int i = lastIndexOf(o);
    if (i >= 0) {
        return size() - i;
    }
    return -1;
}
}

public void put(E e) {
        offer(e); // never need to block
    }


 public boolean offer(E e) {
        if (e == null)
            throw new NullPointerException();
        final ReentrantLock lock = this.lock;
        lock.lock();//加锁
        int n, cap;
        Object[] array;
     	//如果元素个数大于等于数组长度，开始扩容
        while ((n = size) >= (cap = (array = queue).length))
            tryGrow(array, cap);
        try {
            //一开始构建队列的时候传入comparator
            Comparator<? super E> cmp = comparator;
            if (cmp == null)
                //使用元素自带的comparator进行比较，并排序
                siftUpComparable(n, e, array);
            else
                //使用comparator进行比较，并排序
                siftUpUsingComparator(n, e, array, cmp);
            size = n + 1;//增加元素个数
            notEmpty.signal();//唤醒take线程
        } finally {
            lock.unlock();//解锁
        }
        return true;
    }

//新元素堆内上浮实现
    private static <T> void siftUpComparable(int k, T x, Object[] array) {
        //尝试转化插入对象为Comparable实例
        Comparable<? super T> key = (Comparable<? super T>) x; 
        while (k > 0) {
            // 新元素x的数组下标为k，对应的父节点的下标为(k-1)/2
            int parent = (k - 1) >>> 1; 
            Object e = array[parent];
            //如果子节点已经比父节点还要大，不需要再跟上层节点比较，新元素上浮结束
            if (key.compareTo((T) e) >= 0) 
                break;
            //如果子节点已经比父节点小，父节点下沉，新元素上浮一次
            array[k] = e; 
            k = parent; //新元素上浮后继续与新的父节点比较大小，直到k=0或者新的父节点小于新元素
        }
        array[k] = key;//新元素在堆中插入正确的位置。
    }

 private void tryGrow(Object[] array, int oldCap) {
     	//扩容期间需要解锁，能够让其他线程继续执行
        lock.unlock(); // must release and then re-acquire main lock
        Object[] newArray = null;//新数组
     	//cas标识，如果为0，表示当前没有线程对数组扩容
        if (allocationSpinLock == 0 &&
            //cas方式设置值0->1
            UNSAFE.compareAndSwapInt(this, allocationSpinLockOffset,
                                     0, 1)) {
            try {
                //开始扩容
                //计算新的数组长度
                int newCap = oldCap + ((oldCap < 64) ?
                                       (oldCap + 2) : // grow faster if small
                                       (oldCap >> 1));
                //计算容量不能超过最大大小
                if (newCap - MAX_ARRAY_SIZE > 0) {    // possible overflow
                    int minCap = oldCap + 1;
                    if (minCap < 0 || minCap > MAX_ARRAY_SIZE)
                        throw new OutOfMemoryError();
                    newCap = MAX_ARRAY_SIZE;
                }
                if (newCap > oldCap && queue == array)
                    newArray = new Object[newCap];//创建新的数组用来保存元素
            } finally {
                allocationSpinLock = 0;//重置标识，表示扩容完毕
            }
        }
        if (newArray == null) // back off if another thread is allocating
            Thread.yield();
        lock.lock();//重新加锁
     	//如果数组还是原来的数组
        if (newArray != null && queue == array) {
            queue = newArray;//设置为新数组
            System.arraycopy(array, 0, newArray, 0, oldCap);//转移元素到新数组
        }
    }

 public E take() throws InterruptedException {
        final ReentrantLock lock = this.lock;
        lock.lockInterruptibly();//加锁
        E result;
        try {
            while ( (result = dequeue()) == null)
                notEmpty.await();
        } finally {
            lock.unlock();
        }
        return result;
    }

private E dequeue() {
        int n = size - 1;
        if (n < 0)
            return null;//队列为空
        else {
            Object[] array = queue;
            E result = (E) array[0];//取出第一个,二叉堆中第一个最小
            E x = (E) array[n];
            array[n] = null;//设置为空
            Comparator<? super E> cmp = comparator;
            if (cmp == null)
                siftDownComparable(0, x, array, n);
            else
                siftDownUsingComparator(0, x, array, n, cmp);
            size = n;
            return result;
        }
    }

//空元素堆内下沉实现
    private static <T> void siftDownComparable(int k, T x, Object[] array, int n) {
        if (n > 0) {
            Comparable<? super T> key = (Comparable<? super T>) x;
            int half = n >>> 1; // loop while a non-leaf  half最后一个有子节点的父节点下标
            while (k < half) { 
                int child = (k << 1) + 1; // assume left child is least
                Object c = array[child];
                int right = child + 1;
                if (right < n
                        && ((Comparable<? super T>) c)
                                .compareTo((T) array[right]) > 0)
                    c = array[child = right];  //比较出左右子节点更小的那个子节点
                if (key.compareTo((T) c) <= 0) //如果左右子节点的最小值大于数组末尾的值，那么数组末尾的值直接放到父节点，空节点下沉结束
                    break;
                array[k] = c; // 如果子节点最小值小于数据末尾的值，子节点上浮到父空节点
                k = child; //空节点下滑到最小子节点的位置
            }
            array[k] = key; // 最后空节点填充数组最后的值
        }
    }