public class ArrayList<E> extends AbstractList<E>  //可以看到其父类是AbstractList

        implements List<E>, RandomAccess, Cloneable, java.io.Serializable

{

    private static final long serialVersionUID = 8683452581122892189L;

    private static final int DEFAULT_CAPACITY = ;  //默认数组长度

    
    //用于空实例的共享空数组实例。

    private static final Object[] EMPTY_ELEMENTDATA = {};  //底层是Object类型的数组

    
    //共享空数组实例用于默认大小的空实例。我们将其与EMPTY_ELEMENTDATA区别开来，以便知道当添加第一个元素时膨胀多少。

    private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

    
    //存储ArrayList元素的数组缓冲区。
    //ArrayList的容量是这个数组缓冲区的长度。
    //当添加第一个元素时，任何带有elementData==DEFAULTCAPACITY_EMPTY_ELEMENTDATA的空ArrayList将被扩展为DEFAULT_CAPACITY。

    transient Object[] elementData; // 非私有以简化嵌套类访问

    private int size;  //数组内数据元素的个数

    public ArrayList(int initialCapacity) { 
        //我们在声明实例的时候可以指定容量大小，若为0的话，则使用ELEMENTDATA作为默认数组。

        if (initialCapacity > ) {

            this.elementData = new Object[initialCapacity];

        } else if (initialCapacity == ) {

            this.elementData = EMPTY_ELEMENTDATA;

        } else {

            throw new IllegalArgumentException("Illegal Capacity: "+

                                               initialCapacity);

        }

    }

    public ArrayList() { //若不指定容量大小，则使用DEFAULTCAPACITY_EMPTY_ELEMENTDATA作为默认数组

        this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;

    }

    public ArrayList(Collection<? extends E> c) {  //也可以接收Clooection类型的变量，把里面的元素拷贝到数组里面

        elementData = c.toArray();

        if ((size = elementData.length) != ) {

            // c.toArray might (incorrectly) not return Object[] (see 6260652)

            if (elementData.getClass() != Object[].class)

                elementData = Arrays.copyOf(elementData, size, Object[].class);

        } else {

            // replace with empty array.

            this.elementData = EMPTY_ELEMENTDATA;

        }

    }

}

 public boolean add(E e) { //在存入数据前，先确保内部容量
        ensureCapacityInternal(size + );  // Increments modCount!!

        elementData[size++] = e;

        return true;

 }

 private void ensureCapacityInternal(int minCapacity) {

        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {

            minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity); // 默认容量10和当前容量取max

        }

        ensureExplicitCapacity(minCapacity); //校验当前容量是否符合要求容量

 }

 private void ensureExplicitCapacity(int minCapacity) {

        modCount++;

        // overflow-conscious code

        if (minCapacity - elementData.length > )

            grow(minCapacity); // 如果要求容量大于数组容量，就扩容

 }

 private void grow(int minCapacity) {

        // overflow-conscious code

        int oldCapacity = elementData.length;

        int newCapacity = oldCapacity + (oldCapacity >> ); // 新容量 = 旧容量+旧容量的一半

        if (newCapacity - minCapacity < )

            newCapacity = minCapacity;

        if (newCapacity - MAX_ARRAY_SIZE > )

            newCapacity = hugeCapacity(minCapacity);

        // minCapacity is usually close to size, so this is a win:

        elementData = Arrays.copyOf(elementData, newCapacity); // 把旧数据拷贝到新数组里面

 }

public class Vector<E>

    extends AbstractList<E>

    implements List<E>, RandomAccess, Cloneable, java.io.Serializable

{

    protected Object[] elementData;

    protected int elementCount;

    protected int capacityIncrement;

    private static final long serialVersionUID = -2767605614048989439L;

    public Vector(int initialCapacity, int capacityIncrement) {

        super();

        if (initialCapacity < )

            throw new IllegalArgumentException("Illegal Capacity: "+

                                               initialCapacity);

        this.elementData = new Object[initialCapacity];

        this.capacityIncrement = capacityIncrement;

    }

    public Vector(int initialCapacity) {

        this(initialCapacity, );

    }

    public Vector() {

        this();

    }

    public Vector(Collection<? extends E> c) {

        elementData = c.toArray();

        elementCount = elementData.length;

        // c.toArray might (incorrectly) not return Object[] (see 6260652)

        if (elementData.getClass() != Object[].class)

            elementData = Arrays.copyOf(elementData, elementCount, Object[].class);

    }

}

public synchronized boolean add(E e) {

        modCount++;

        ensureCapacityHelper(elementCount + ); // 先校验容量

        elementData[elementCount++] = e;

        return true;

}

private void ensureCapacityHelper(int minCapacity) {

        // overflow-conscious code

        if (minCapacity - elementData.length > )

            grow(minCapacity); //扩容

}

private void grow(int minCapacity) {

        // overflow-conscious code

        int oldCapacity = elementData.length;

        int newCapacity = oldCapacity + ((capacityIncrement > ) ?

                                         capacityIncrement : oldCapacity);

        if (newCapacity - minCapacity < )

            newCapacity = minCapacity;

        if (newCapacity - MAX_ARRAY_SIZE > )

            newCapacity = hugeCapacity(minCapacity);

        elementData = Arrays.copyOf(elementData, newCapacity);

}
private static int hugeCapacity(int minCapacity) {
        if (minCapacity < 0) // overflow
            throw new OutOfMemoryError();
        return (minCapacity > MAX_ARRAY_SIZE) ?
            Integer.MAX_VALUE :
            MAX_ARRAY_SIZE;
}

public class LinkedList<E>

    extends AbstractSequentialList<E>

    implements List<E>, Deque<E>, Cloneable, java.io.Serializable

{

    transient int size = ;

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

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

    public 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) {//add方法就是在链表的尾部加上一个结点

        linkLast(e);

        return true;

}

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 E get(int index) {

        checkElementIndex(index);

        return node(index).item;

}

private void checkElementIndex(int index) {

        if (!isElementIndex(index))

            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));

}

Node<E> node(int index) {

        // assert isElementIndex(index);

        // 若索引在链表的前半部分，就从前往后取；否则从后往前取

        if (index < (size >> )) {

            Node<E> x = first;

            for (int i = ; i < index; i++)

                x = x.next;

            return x;

        } else {

            Node<E> x = last;

            for (int i = size - ; i > index; i--)

                x = x.prev;

            return x;

        }

}