对于ArrayList和LinkedList的理解

以下开始对于ArrayList和LinkedList的理解，主要从以下几点分析：

1、从继承结构上分析

从继承结构来看，ArrayList和LinkedList都是Collecttion顶级接口下的List接口的具体实现类。ArrayList继承自AbstractList抽象类，AbstractList抽象类又继承自AbstractCollection抽象类，AbstractCollection抽象类实现了Collection接口；对于LinkedList它继承自AbstractSequentialList抽象类，AbstractSequentialList抽象类又继承自AbstractList的抽象类，AbstractList有继承自AbstractCollection抽象类，最终实现Collection接口。

2、从底层数据结构分析（包括扩容机制、优缺点、应用场景）

ArrayList简介：它是一个动态数组，底层的数据结构是一个数组

ArrayList特点：对于ArrayList数组来说，它的查找效率很高，会根据数组下标索引查找对应的数值，时间复杂度是O(1)，但是对于添加和删除元素来说，性能不好时间复杂度是O(n)。

ArrayList底层原理：

    /**
     * Default initial capacity.
     */
    private static final int DEFAULT_CAPACITY = 10;

会发现它的默认容量是 10

分析构造函数：（无参构造函数）

        public ArrayList() {
        this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
    }

直接使用默认的容量10，来进行初始化。

那数据具体是存在哪里呢？

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

会发现它在底层维持了一个叫做：Object[]数组的 elementData数组。

分析有参构造函数：（还有一个参数--容量）

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

现在就开始分析，它在添加一个元素的时候是干了什么事情：

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

在添加一个元素的时候，干了两件事：第一，对容量进行管理；第二，添加元素向数组。

    // 对容量进行管理
        private void ensureCapacityInternal(int minCapacity) {
        ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
    }
        // 对容量进行计算
    private static int calculateCapacity(Object[] elementData, int minCapacity) {
        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
            return Math.max(DEFAULT_CAPACITY, minCapacity);
        }
        return minCapacity;
    }
        // 判断是不是要扩容
    private void ensureExplicitCapacity(int minCapacity) {
        modCount++;

        // overflow-conscious code
        if (minCapacity - elementData.length > 0)
            grow(minCapacity);
    }
        // 进行扩容 ， 每次扩容 1.5 倍
    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);
    }

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

private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

这里表明ArrayList在扩容的时候，当前的容量如果大于MAX_ARRAY_SIZE就将容量设置为Integer.MAX_VALUE，反之的话，容量设置为MAX_ARRAY_SIZE。

ArrayList应用场景：ArrayList更加适合查找多修改少的场景。

LinkedList的简介：LinkedList是一个双向链表，存储数据的时候在链表中存储。

LinkedList的特点：LinkedList在添加元素和删除元素的时候的性能要比ArrayList要好很多，它的时间复杂度是O(1)，但是在查找的时候，对于链表的头和尾除外的结点，是需要一个个遍历查找的，时间复杂度是O(n)。

LinkedList的底层源码：

    public class LinkedList<E>
    extends AbstractSequentialList<E>
    implements List<E>, Deque<E>, Cloneable, java.io.Serializable {

    transient int size = 0;

    /**
     * Pointer to first node.
     * Invariant: (first == null && last == null) ||
     *            (first.prev == null && first.item != null)
     */
    transient Node<E> first;

    /**
     * Pointer to last node.
     * Invariant: (first == null && last == null) ||
     *            (last.next == null && last.item != null)
     */
    transient Node<E> last;

    /**
     * Constructs an empty list.
     */
    public LinkedList() {
    }

    /**
     * Constructs a list containing the elements of the specified
     * collection, in the order they are returned by the collection's
     * iterator.
     *
     * @param  c the collection whose elements are to be placed into this list
     * @throws NullPointerException if the specified collection is null
     */
    public LinkedList(Collection<? extends E> c) {
        this();
        addAll(c);
    }

会发现源码，它里面有first结点，也有last结点，分别代表头结点和尾结点。在整个的设计中，会发现他是一个双向链表的结构。

分析它的添加一个元素的源码：

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

会发现，它调用了一个尾插法的方法，值得说的是，在源码中，他设计了两个方法进行添加值，一个是头插法一个是尾插法。

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

它和ArrayList不同的是ArrayList是有自己的扩容机制的，并且每次的扩容都是以1.5倍的方式实现扩容，但是LinkedList是不需要扩容的，因为，链表需要扩容吗？显然不需要，只要你的内存多，理论上可以是无限。

LinkedList的应用场景：LinkedList更加适合频繁的对元素进行增删，但是对查找少的场景。