前言

在日常的java开发中，我们经常用到各种集合类，而List是其中最常见的一种；以前我们在使用数组的时候，无论是c++或者java，都要指定它的大小；而List居然不用指定大小，太神奇了，接下来让我们仔细分析一下它们的实现

LinkedList：

1. 主要成员变量：

transient int size = 0; //List长度
transient Node<E> first;//头指针
transient Node<E> last;//尾指针

1. add方法(将元素放入List尾部)：

public boolean add(E e) {
    linkLast(e);
    return true;
}

再看linkLast方法：

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

也就是说，每次添加一个节点到末尾时，都是新申请一个链表节点，然后再缝缝补补，把相关的链表指针接在一起；复杂度为O(1);

再看看另外一个add方法：

1. add(int index, E element)(将元素插入到某个下标位置):

public void add(int index, E element) {
    checkPositionIndex(index);

    if (index == size)
        linkLast(element);
    else
        linkBefore(element, node(index));
}

<p>
再看node()方法(找到下标对应的链表节点):

Node<E> node(int index) {
    // assert isElementIndex(index);

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

其寻址复杂度是O(n)的,唯一的优化点就在于，看下标离头指针近还是离尾指针近，复杂度做了常数上的优化，从n下降到n/2, 但还是O(n)；
剩下的删查都涉及到寻址的时间损耗，复杂度也都是O(n)，它们的实现都是类似的，就不赘诉了。

小优化：其实如果我们自己实现一个LinkedList，完全可以把指针信息加在节点上，这样就可以避免一些寻址上的时间损耗了。

ArrayList（与c++里的vector类似）

1. 成员变量：

transient Object[] elementData; // 存储元素的载体是数组
private int size;//List当前长度

1. 主构造方法：

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);
    }
}
没有什么特别的，就是申请一个定长的数组

1. add(E e)方法:

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

第一行是确保数组载体容量足够，后边就是把下标为size+1的元素赋值成e；
它调用了ensureCapacityInternal()方法：

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

    ensureExplicitCapacity(minCapacity);
}

又调用了ensureExplicitCapacity()方法：

private void ensureExplicitCapacity(int minCapacity) {
    modCount++;

    // overflow-conscious code
    if (minCapacity - elementData.length > 0)
        grow(minCapacity);
}

再看grow()方法：

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

里边关键的一句代码就是：

int newCapacity = oldCapacity + (oldCapacity >> 1);

意思就是，新的数组容量变成原数组的大约1.5倍（看不懂的可以去了解一下位运算），新的数组申请内存之后，再把老的数组里的元素全copy到新数组就完成了；
那么为什么每次容量不足的时候，要扩充到1.5倍呢？通过分析我们可以发现，每次扩充1.5倍容量，那么假设最后容量扩充为n，那么总体上的申请空间的数量近似于：f(n) = n + n * 2/3 + n * (2/3)^2 + n * (2/3)^3 + ... ，根据等比数列公式可以知道，这个表达式的值为： f(n) = 3 * n = O(n)
采用倍增的方法扩容，优点在于总体的复杂度数量级是线性的，但是也不可避免的可能会有空间浪费；在最极端的情况下，会有接近1/3的空间是没有利用上的；因此，在List会很大，且能预先大致估算出List会有多大的前提下，为了减少系统的内存消耗和频繁GC，应尽量使用以下构造方法来申请List：

public ArrayList(int initialCapacity);

1. add(int index, E element)方法（将元素插入到指定下标）:

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

跟add(E element)方法的最大的差别就在于，在赋值之前，要先把该下标以及后面的元素全都向后移一位，其复杂度为O(n);

1. 接下来看get(int index)方法：

public E get(int index) {
    rangeCheck(index);

    return elementData(index);
}

检查下标合法性，再调用elementData():

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

直接是数组的根据下标随机访问的操作，复杂度是O(1)，再强转成E类型就返回了;

1. remove(int 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;
}

在删除指定下标的元素时，如果这个元素不是最后一个，那么要将后面的元素全部向前移一位，复杂度也是O(n), 另外还有一点就是，删除了这个元素之后，要把最大下标的那个元素赋值成null，方便系统进行GC（系统GC时，会根据对象是否被引用来判断对象是否可以回收）

1. remove(Object o)方法：

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

定位到元素位置复杂度为O(n), fastRemove(index)的复杂度也是O(n);
另外，初看这段代码，感觉写得有点“啰嗦”，但实际上确实是有必要的：List元素允许为空，所以要特判该元素是否为空，为空时直接用==null来判断，而不为空时，才能调用equals方法进行比较，否则会有空指针异常；所以这段代码也是JDK严谨性的一种体现；

1. 以下表格列出了两者在各种操作下的复杂度：

| 操作\List实现类 | LinkedList | ArrayList |
| ------------- |:-------------:| -----:|
| add(E e) | O(1) | O(1) |
| add(int index, E element) | O(n) | O(n) |
| get(int index) | O(n) | O(1) |
| remove(int index) | O(n) | O(n) |
| remove(Object o) | O(n) | O(n) |

从上表看，LinkedList几乎没有比ArrayList优越的地方；另外，LinkedList相比ArrayList没有0.5倍的空间浪费，但是其每个节点都有前后指针的内存占用，且每次新增一个元素时都要新申请一个Node，而ArrayList则是一次性批量申请；所以，当List长度比较大的时候，肯定是ArrayList效率比较高。
如果说LinkedList有优点的话，可能就是它不需要申请连续的内存，所以建议大家除了极端情况，大部分时候都使用ArrayList。