/**

* The array buffer into which the elements of the ArrayList are stored.

* The capacity of the ArrayList is the length of this array buffer. Any

* empty ArrayList with elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA

* will be expanded to DEFAULT_CAPACITY when the first element is added.

存储arrayList数组的缓冲区

*/

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

/**

* The size of the ArrayList (the number of elements it contains).

*

* @serial

*/

private int size;

构造方法

public ArrayList(int initialCapacity) {

    if (initialCapacity > 0) {

        this.elementData = new Object[initialCapacity];

    } else if (initialCapacity == 0) {

        this.elementData = EMPTY_ELEMENTDATA;

    } else {

        throw new IllegalArgumentException("Illegal Capacity: "+

                                           initialCapacity);

    }

}

add元素到尾部

public boolean add(E e) {

    ensureCapacityInternal(size + 1);  // Increments modCount!! 判断数组的大小，不够的话，自动扩容

    elementData[size++] = e;

    return true;

}

add元素到指定位置

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; // 扩容后，将插入点后面的元素往后移动一个位置，通过System.arraycopy复制方式实现

    size++;

}

remove移除

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;

}

链表

任何的数据类型都可以通过最基本的数组和指针构造。链表也不例外，相比于数组，数组则是定长的，不管存储的满否，都申请了一定大小的内存空间，而链表则不是，链表的空间是随用随申请，数据的位置相比于数组，其实不连续的，一般来说，需要在元素上指定下一个元素的指针，来达成链接关系。

说明：每个元素上都有一块位置用于指向下一个元素（指针）

链表还是比较适合于快速增加、删除、不适合于索引。因为需要全盘遍历

下面就是一个单项链表

链表在JAVA 当中最具代表性的就是 LinkedList(双向链表)，就是每个元素会带有它的上一个节点和下一个节点的指针

三个重要的属性

transient int size = 0;

/**

* Pointer to first node.

* Invariant: (first == null && last == null) ||

* (first.prev == null && first.item != null)

*/

transient Node<E> first; // 集合的第1个节点

/**

* Pointer to last node.

* Invariant: (first == null && last == null) ||

* (last.next == null && last.item != null)

*/

transient Node<E> last; // 集合的最后一个节点

单个节点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;

    }

}

头部插入和尾部插入一个节点

/**

* Links e as first element.

*/

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

}

/**

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

}

指定位置插入新的节点

/**

* Inserts element e before non-null Node succ.

*/

void linkBefore(E e, Node<E> succ) {

    // assert succ != null;

    final Node<E> pred = succ.prev;

    final Node<E> newNode = new Node<>(pred, e, succ);

    succ.prev = newNode;

    if (pred == null)

        first = newNode;

    else

        pred.next = newNode;

    size++;

    modCount++;

}