一.线性表

定义:零个或者多个元素的有限序列。
也就是说它得满足以下几个条件:
  ①该序列的数据元素是有限的。
  ②如果元素有多个，除了第一个和最后一个元素之外，每个元素只有一个前驱元素和一个后驱元素。
  ③第一元素没有前驱元素，最后一个元素没有后继元素。
  ④序列中的元素数据类型相同。
则这样的数据结构为线性结构。在复杂的线性表中，一个数据元素(对象)可以由若干个数据项组成，组成一张数据表，类似于数据库。

二.线性表的抽象数据类型

1.相关概念

抽象数据类型(abstract data type,ADT)是带有一组操作的一组对象的集合。这句话表明，线性表的抽闲数据类型主要包括两个东西:数据集合和数据集合上的操作集合。
①数据集合:我们假设型如a0,a1,a2,...an-1的表，我们说这个表的大小是N，我们将大小为0的标称为空表。
②集合上的操作:一般常用的操作包括，查找，插入，删除，判断是否为空等等。

2.线性表的顺序储存结构

线性表的顺序储存结构，指的是用一段地址连续的储存单元依次储存线性表的数据元素。我们可以用一维数组实现顺序储存结构,并且上述对表的所有操作都可由数组实现。但是一维数组有一个很大缺点就是它得长度是固定的，也就是我们创建的额时候就声明的长度，一旦我们要存储的数据超出了这个长度，我们就不得不手动的创建一个更长的新数组并将原来数组中的数据拷贝过去。

    int [] arr = new int[10]
    ......
    int [] newArr = new int[arr.length*2]
    for(int i=0;i<arr;i++){
        newArr[i] = arr[i];
    }
    arr = new Arr;

显然这样做非常的不明智，因此java中的ArrayList就应用而生了。ArrayList也就是传说中的动态数组,也就是我们可以随着我们数据的添加动态增长的数组。
  实际上不管是简单数组也好，动态数组也好，在具体的操作中都存在这样的问题:
  ①如果我们在线性表的第i个位置插入/删除一个元素，那么我们需要怎么做呢？首先我们得从最后一个元素开始遍历，到第i个位置，分辨将他们向后/前移动一个位置；在i位置处将要插入/删除的元素进行相应的插入/删除操作；整体的表长加/减1.
  ②如果我们在线性表的第一个位置插入/删除一个元素，那么整个表的所有元素都得向后/向前移动一个单位，那么此时操作的时间复杂度为O(N);如果我们在线性表的最末位置进行上面两种操作，那么对应的时间复杂度为O(1)——综合来看，在线性表中插入或者删除一个元素的平均时间复杂度为O(N/2)。
  总结一下,线性表的缺点——插入和删除操作需要移动大量的元素；造成内存空间的"碎片化"。这里有些童鞋就说了，ArrayList是一个线性表吧，我再ArrayList中添加/删除一个元素直接调用add()/remove()方法就行了啊，也是一步到位啊——这样想就不对了，如果我们看ArrayList的源码就会发现，实际上他内部也是通过数组来实现的，remove()/add()操作也要通过上面说的一系列步骤才能完成，只不过做了封装让我们用起来爽。之后我们会通过源码分析ArrayList等的内部的实现方式。
  当然了，优缺点就会有优点——由于顺序储存结构的元素数目，元素相对位置都确定的，那么我们在存取确定位置的元素数据的时候就比较方便，直接返回就行了。

3.线性表的链式储存结构

上面我们说过，顺序结构的最大不足是插入和删除时需要移动大量元素；造成内存空间的"碎片化。那么造成这中缺点的原因是什么呢？原因就在于这个线性表中相邻两元素之间的储存位置也就有相邻关系，也就是说元素的位置是相对固定的，这样就造成了"牵一发而动全身"的尴尬局面；同时，什么是"碎片化"呢？就是说上述顺序结构中，以数组为例来说，如果我们先在内存中申请一个10位长度的数组，然后隔3个位置放一个5位长度的数组，这个时候如果再来一个8位长度的数组，那么显然不能放在前两个数组之间(他们之间只有三个空位)，那只能另找地方，中间的这三个位置就空下了，久而久之类似的事情多了就发生了"碎片化"的现象。

(1)简单链表

为了解决上述两个问题，我们前辈的科学家们就发明了伟大的"链式储存结构"，也就是传说中的链表(Linked List)。链表的结构有两大特点：
  ①用一组任意的储存单元储存线性表的数据元素，这组储存单元可以是连续的，也可以是不连续的。这就意味着，这些数据元素可以存在内存中任意的未被占用的位置。
  ②在上面的顺序数据结构中，每个数据元素只要储存数据信息就可以了，但是在链表中，由于数据元素之间的位置不是固定的，因此为了保证数据元素之间能相互找到前后的位置，每个数据元素不仅需要保存自己的数据信息，还需要保存指向下一个指针位置的信息。

简单链表.png

如图，我们画出了简单链表的示意图。链表由一系列结点组成，这些结点不必再内存中相连，每个结点含有表元素(数据域)和到包含该元素后继结点的链(link)(指针域)。
  对于一个线性表来说，总得有头有尾，链表也不例外。我们把第一个链表储存的位置叫做"头指针"，整个链表的存取就是从头指针开始的。之后的每一个结点，其实就是上一个结点的指针域指向的位置。最后一个结点由于没有后继结点，因此它的指针域为NULL。
  有时我们会在第一个指针前面加上一个头结点，头结点的数据域可以不表示任何数值，也可以储存链表长度等公共信息，头结点的指针域储存指向第一个结点的位置的信息。
  需要注意的是，头结点不是链表的必要要素，但是有了头结点，在对第一个结点之前的位置添加/删除元素时，就与其他元素的操作统一了。
(1.1)简单链表的读取
  在上面的线性表的顺序储存结构中，我们知道它的一个优点就是存取确定位置的元素比较的方便。但是对于链式储存结构来说，假设我们要读取i位置上的元素信息，但是由于我们事先并不知道i元素到底在哪里，所以我们只能从头开始找，知道找到第i个元素为止。由于这个算法的时间复杂度取决于i的位置，最坏的情况就是O(n),即元素在末尾。
  由于单链表没有定义表长，所以我们没有办法使用for循环来查找。因此这里查找算法的核心思想是"工作指针后移",也就是当前的元素查完之后，移动到下一个位置，检查下一个位置的元素，以此循环，直到找到第i个位置的元素。
  可以看到，这是链表结构的一个缺点，对于确定位置的元素查找平均时间复杂度为O(N/2)。
(1.2)简单链表的插入与删除
  当然了，有缺点就有优点，我们说过链表解决了顺序表中"插入和删除时需要移动大量元素"的缺点。也就是说，链表中插入删除元素不需要移动其他的元素，那么链表是怎么做到的呢？

单链表的删除与插入.png

我们用“.next”表示一个节点的后继指针,X.next = Y表示将X的后继指针指向Y节点。这里不得不说一下,由于Java中没有指针的概念，而是引用(关于指针和引用的区别我们这里不做过多的说明，他们本质上都是指向储存器中的一块内存地址)。在java语言描述的链表中,上面所说的“指针域”更准确的说是“引用域”，也就是说，这里的x.next实际上是X的下一个节点x->next元素的引用。说的更直白一点，我们可以简单的理解为x.next = x->next,就像我们经常做的Button mbutton = new Button();一样，在实际操作中我们处理mbutton这个引用实际上就是在处理new Button()对象。
  我们先说删除的做法，如上图所示，我们假设一个x为链表节点，他的前一个结点为x->prev,后一个结点为x->next,我们用x.next表示他的后继引用。现在我们要删除x结点，需要怎么做呢？实际上很简单，直接让前一个结点元素的后继引用指向x的下一个节点元素(向后跳过x)就可以了x->prev.next = x.next。
  同理插入一个节点呢？首先我们把Node的后继节点Next的变成P的后继节点，接着将Node的后继引用指向P，用代码表示就是:P.next = Node.next; Node.next = P;。解释一下这两句代码，P.next = Node.next;实际上就是用Node.next的引用覆盖了P.next的引用，P.next的引用本来是一个空引用(刚开始还没插入链表不指向任何节点)，而Node.next本来是指向Next节点的，这一步操作完之后实际上P.next这个引用就指向了Next节点；这个时候Node.next = P;这句代码中，我们将Node.next这个引用重新赋值，也就是指向了P这个节点，这样整个插入过程就完成了。
  为什么我们啰里啰嗦的为两句代码解释了一堆内容呢？就是要强调，上面两个步骤顺序是不能颠倒的！为什么呢？我们不妨颠倒顺序看一下——我们首先进行Node.next = P;这一步，开始的时候，P的引用域是空的(或者指向无关的地址)，此时如果我们进行了这一步，那么Node.next这个引用就指向了P节点，这个时候我们再进行P.next = Node.next这一步就相当于P.next = p,p.next引用域指向自己，这没有任何意义。

(2)双链表(LinkedList)

上面我们说了简单链表的各种事项，但是在实际的运用中，为了我们的链表更加灵活(比如既可以工作指针后移向后查找，也可以指针向前移动查询)，我们运用更多的是双向链表，即每个节点持有前面节点和后面节点的引用。java的双向链表通过LinkedList类实现，通过阅读源码我们在该类中可以看到关于结点的定义:

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

Java双链表中的结点是通过一个静态内部类定义。一个结点包含自身元素(item)，该节点对后一个节点的引用(next)，该节点对前一个节点的引用(prev)。
(2.1)双链表的删除

双链表的删除.png

如图，我们假设在一个双向链表中有一个节点X，他的前继节点是prev，后继节点是next.现在我们展示删除节点X的源码（sources/ansroid-24/java/util/LinkedList）:

    public boolean remove(Object o) {         //删除分为两种情况，一种是删链表中的null元素，一种是删正常元素
        if (o == null) {    //删除的具体操作没什么区别，都是从第一个开始，向后移动工作指针，直到找到符合条件的
            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;
    }

    E unlink(Node<E> x) {   //上面是找元素，这个方法是真正删除元素
        final E element = x.item;   //x.item表示当前的x节点
        final Node<E> next = x.next;    //x.next表示x后继引用，next同
        final Node<E> prev = x.prev;    //x.prev是x的前继引用，prev同
        ......

        if (prev == null) { //如果prev为null，则表示x为第一个结点，此时删除x的做法只需要将x的
            first = next;   //下一个节点设为第一个节点即可，first表示链表的第一节点。
        } else {
     ①      prev.next = next;   //否则的话，x为普通节点。那么只要将x的前一个结点(prev)的后继引用指向x的下一个 
            x.prev = null;      //节点就行了,也就是(向后)跳过了x节点。x的前继引用删除，断开与前面元素的联系。
        }

        if (next == null) {
            last = prev;    //如果x节点后继无人，说明他是最后一个节点。直接把前一个结点作为链表的最后一个节点就行
        } else {
     ②      next.prev = prev;   //否则x为普通节点，将x的下一个节点的前继引用指向x的前一个节点，也就是(向前)跳过x.   
            x.next = null;  //x的后继引用删除，断了x的与后面元素的联系
        }

        x.item = null;  //删除x自身
        size--;     //链表长度减1
        modCount++;
        return element;
    }

我们在在上面的源码中标出了删除一个元素所需要的两个步骤，即prev节点中原本指向X节点的后继引用，现在向后越过X，直接指向next节点①(prev.next = next;)；next节点中原本指向X节点的前继引用，现在向前越过X节点，直接指向prev节点。；然后就是将X的前继引用和后继引用都设置为null，断了他与前后节点之间的联系；最后将X节点本身置为null，方便内存的释放。
(2.2)双链表的插入

双链表的添加.png

这里我们选取较为容易的，在指定位置添加一个元素的add方法分析（sources/ansroid-24/java/util/LinkedList）:

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

        if (index == size)  //size表示整个链表的长度，如果指定的索引等于链表的长度，那么就把这个元素添加到链表末尾
            linkLast(element);
        else        //否则执行linkBefore()方法，添加到末尾之前的元素前面
            linkBefore(element, node(index));
    }

这里我们看一下这个node(index)方法:

    /**
     * Returns the (non-null) Node at the specified element index.返回指定索引处的非空元素
     */
    Node<E> node(int index) {
        if (index < (size >> 1)) {  //size >> 1,表示二进制size右移一位，相当于size除以2
            Node<E> x = first;
            for (int i = 0; i < index; i++) //如果指定的索引值小于size的一般，那么从第一个元素开始，
                x = x.next;         //指针向后移动查找,一直到指定的索引处
            return x;
        } else {            //else,从最后一个元素开始，向前查找
            Node<E> x = last;
            for (int i = size - 1; i > index; i--)
                x = x.prev;
            return x;
        }
    }

    /**
     * Inserts element e before non-null Node succ.
     */
    void linkBefore(E e, Node<E> succ) {    //e为我们要插入的元素，succ为我们要插入索引处的元素

        final Node<E> pred = succ.prev;     //先将succ的前继引用(或者前一个结点的元素)保存在pred变量中
        final Node<E> newNode = new Node<>(pred, e, succ);  //创建一个新节点，也就是我们要插入的这个元素
                                    //注意new Node<>(pred, e, succ);这三个参数，可以参照(1.3)处的源码
     ① succ.prev = newNode; //succ的前继引用指向NewNode
        if (pred == null)       //如果这个前继引用为空，那就说明我们插入的元素是在最前面
            first = newNode;    //直接让newNode做第一个元素就行了
        else
    ②       pred.next = newNode;    //否则的话，在让pred的后继引用指向newNode节点
        size++;
        modCount++;
    }

可以看到这里实际上和简单链表的添加一样，也是分两步走，而且两步的顺序不能颠倒。这里需要说明的一点是，我们在图上用灰色的点线多画了两条箭头，其中①②分别表示的是新元素的前继引用和后继引用分别指向pred和succ的赋值过程。在笔者参考的《大话数据结构》中，双链表的添加算上点线的那两步一共是四步，但实际上在java中创建newNode的时候new Node<>(pred, e, succ)这句代码已经一次性做完了上述两部过程，真正做事的就是我们在图中用黑线标出的那两步。

三.JAVA中相关的collection集合

java集合主要由两个接口派生而出——Collection接口和Map接口。collection储存一组类型相同的对象，且每个位置只能保存一个元素；Map保存的是键值对(key-value)。我们本节重点来说Collection集合。
  对于collection接口中的方法，我我们可以通过他的源码来看:

public interface Collection<E> extends Iterable<E> {

    int size(); //@return the number of elements in this collection
    boolean isEmpty();  //@return <tt>true</tt> if this collection contains no elements
    boolean contains(Object o); //Returns <tt>true</tt> if this collection contains the specified element.
    Object[] toArray(); //Returns an array containing all of the elements in this collection.
    boolean remove(Object o);   //<tt>true</tt> if an element was removed as a result of this call
    boolean add(E e);   //<tt>true</tt> if this collection changed as a result of the call
    boolean containsAll(Collection<?> c);
    boolean addAll(Collection<? extends E> c);
    boolean removeAll(Collection<?> c);
    void clear();
    boolean equals(Object o);
    ......
}

上面我们列出了Collection集合的几个主要的方法，从注释中我们可以很清楚的知道他们的用途。

1.Iterable/Iterator接口

我们看上面的collection接口的时候，collection接口继承了Iterable类，我们来看看这个Iterable类:

public interface Iterable<T> {
    /**
     * Returns an iterator over elements of type {@code T}.
     *
     * @return an Iterator.
     */
     Iterator<T> iterator();

    /*
     * @param action The action to be performed for each element
     * @throws NullPointerException if the specified action is null
     * @since 1.8
     */
     default void forEach(Consumer<? super T> action) {
        Objects.requireNonNull(action);
        for (T t : this) {
            action.accept(t);
        }
    }
    ......
}

我们先看一下第二个函数forEach(Consumer<? super T> action)，在java8中，Iterator新加了这个个forEach循环(注意与java5中的foreach循环的区别，大小写，用法不同)，主要用于更加方便的循环遍历集合中的元素并对每一个元素迭代做出相应的处理，其中的参数Consumer<? super T> action就是我们对集合中的元素所施加的操作。举例说明具体的用法:
传统方式循环List:

    List<String> items = new ArrayList<>();
    items.add("A");
    items.add("B");
    items.add("C");
    items.add("D");
    items.add("E");

    for(String item : items){
        System.out.println(item);
    }

在java8中使用forEach循环+Lambda表达式遍历list：

    List<String> items = new ArrayList<>();
    items.add("A");
    items.add("B");
    items.add("C");
    items.add("D");
    items.add("E");

    //lambda
    //Output : A,B,C,D,E
    items.forEach(item->System.out.println(item));

    //Output : C
    items.forEach(item->{
        if("C".equals(item)){
            System.out.println(item);
        }
    });

回到Iterable类中，我们可以看到他还返回了一个Iterator接口的实例。而这个接口类是什么呢?

public interface Iterator<E> {
    boolean hasNext();
    E next();
    default void remove() {
        throw new UnsupportedOperationException("remove");
    }
     default void forEachRemaining(Consumer<? super E> action) {
        Objects.requireNonNull(action);
        while (hasNext())
            action.accept(next());
    }
}

可以看到，该接口类中一共有四个方法。其中forEachRemaining()方法是java8之后新增的方法，主要的作用和上面我们说过的foreach()循环是一样的，用法也基本相同。
  Iterator类的作用是一个迭代器，主要用于操作colloection集合类中的元素。Iterator类必须依附于Collection对象，Iterator本身并不提供盛装对象的能力。如果需要创建Iterator对象，则必需有一个被迭代的集合，如果没有Colletion集合，Iterator也没有存在的价值。
  Iterator类中的结果方法——hasNext()，用于判断在遍历时collection集合中是否还有剩下的元素；next()用于返回遍历时集合中的下一个元素，这两个方法很好理解。唯独这个remove()方法有一些注意事项需要说明一下:
  我们可以先看看这个方法的注释:

    /**
     * Removes from the underlying collection the last element returned
     * by this iterator (optional operation).  This method can be called
     * only once per call to {@link #next}.  
     * ......
     *
     * @throws IllegalStateException if the {@code next} method has not
     *         yet been called, or the {@code remove} method has already
     *         been called after the last call to the {@code next}
     *         method
     */

翻译一下:从底层集合中删除此迭代器返回的最后一个元素。这个方法只能在每一次调用完next()方法之后调用一次。如果next()方法没有调用，或者remove()方法在上一次next()方法调用完了之后，又调用了一次，则会抛出IllegalStateException异常。
结合这段注释，我们交代一下next()方法调用的几个注意事项:
  ①remove()只能在next()方法调用完后紧接着调用一次，此时他删除的是在他之前调用的那个next()返回的元素
  ②remove()在调用之心完之后，只能等待下一次next()方法执行完了之后，才可以调用。
同时我们还需要注意:③在使用Iterator迭代的过程中，我们不能手动修改collection集合中的元素，即不能手动调用collection类本身的remove(),add()，clear()等方法，只能调用Iterator的remove()方法。举个例子:

public class IteratorTest{
    public static void main(String[] args){
        ...
        Iterator it = books.iterator();
        while(it.hasNext()){
            String book = (String)it.next();
            if("book.equals("hhhhhh"))
                it.remove();    //删除上一次next()返回的元素，也就是"hhhhhh"
            book = "666666";  *
        }
    }
}

上面是一段"正常"的程序，这里需要说明的一点，上一段代码星号处我们将book的赋值为“666666”，但是当我们再次打印出books的集合时会发现集合中的元素没有什么改变，还是原来的值。这说明——当使用Iterator迭代器进行迭代时，Iterator并不是把集合元素本身传递给了迭代变量，而是把集合元素的额值出给了迭代变量，因此我们在后边进行的各种赋值并不影响集合本身的元素。

public class IteratorTest{
    public static void main(String[] args){
        ...
        Iterator it = books.iterator();
        while(it.hasNext()){
            String book = (String)it.next();
            if("book.equals("hhhhhh"))
                books.remove(book);     //错误，在迭代时调用了修改集合本身的方法
        }
    }
}

这是一段有问题的代码。这里还需要注意一点，这个Iterator中的remove()和collection本身的remove(o)方法是不一样的，一个有参数一个无参数。而且子删除集合中元素时，我们优先考虑用Iterator的remve()方法，因为他有更高的效率，为什么呢？这里我们先作为一个遗留问题，后面我们再详细证明。
  同样我们可以用java5中的foreach循环来遍历collection集合中的元素，这个更加简洁一些:

public class ForeachTest{
    public static void main(String[] args){
        ...
        for(Object obj : books){
            String book = (String)it.next();    //此处的book也不是变量本身
            if("book.equals("hhhhhh"))
                books.remove(book);     //错误，在迭代时调用了修改集合本身的方法
        }
    }
}
上面加注释的两个地方，是foreach循环与Iterator迭代类似的地方。

2.List接口，ArrayList类，LinkedList类

colection接口有三个子类实现接口:List(有序集合，元素可以重复)，Queue(对列)，Set(无序集合，元素不可重复)，其中List又有两个最常见的实现类：ArrayList(动态数组)和LinkedList(双向链表)，这两个也就是我们前面一直说的线性表的顺序储存结构和链式储存结构。List接口作为collection接口的子类，当然实现了collection接口中的所有方法。并且由于List是有序集合，因此List集合中增加了一些根据元素索引来操作集合的方法。

(1)List源码解析

public interface List<E> extends Collection<E> {
    ......  //省略一些collection中展示过的方法

    /**同时List接口定义了一些自己的方来实现“有序”这一功能特点*/
    /**
     *返回列表中指定索引的元素
     */
    E get(int index);
    /**
     *设定某个列表索引的值
     */
    E set(int index, E element);
    /**
     *在指定位置插入元素，当前元素和后续元素后移
     *这是可选操作，类似于顺序表的插入操作
     */
    void add(int index, E element);
    /**
     * 删除指定位置的元素(可选操作)
     */
    E remove(int index);
    /**
     * 获得指定对象的最小索引位置，没有则返回-1
     */
    int indexOf(Object o);
    /**
     * 获得指定对象的最大索引位置
     * 可以知道的是若集合中无给定元素的重复元素下
     * 其和indexOf返回值是一样的
     */
    int lastIndexOf(Object o);
    /**
     *一种更加强大的迭代器，支持向前遍历，向后遍历插入删除操作
     */
    ListIterator<E> listIterator();          *
    ListIterator<E> listIterator(int index);    *
    /**
     * 返回索引fromIndex(包括)和toIndex(不包括)之间的视图。
     */
    List<E> subList(int fromIndex, int toIndex);
}

这里解释一下ListIterator类，该类继承自Iterator类，提供了专门操作List的方法。ListIterator接口在Iterator接口的基础上增加了洗下面几个关键的方法:

public interface ListIterator<E> extends Iterator<E> {

    boolean hasNext();
    E next();
    void remove();

    /**下面是在Iterator基础上增加的方法*/
    boolean hasPrevious();  //是否还有前继元素
    E previous();   //返回前一个元素
    int nextIndex();    //返回下一个元素的索引
    int previousIndex();    //返回前一个元素的索引
    void set(E e);  //替换由上一次next()或者previous()方法返回的元素.
    void add(E e);  //在上一次由next()方法返回的元素之前，或者在上一次previous()方法返回的元素之后，添加一个元素
}

可以看到，ListIterator增加了向前迭代的功能(Iterator只能向后迭代)，而且ListIterator可以通过add()方法向List中添加元素(Iterator只能删除)。

(2)ArrayList源码解析

(2.1)ArrayList类的头部:

public class ArrayList<E> extends AbstractList<E>
        implements List<E>, RandomAccess, Cloneable, java.io.Serializable{

RandomAccess：RandmoAccess是一个标记接口，用于被List相关类实现。他主要的作用表明这个相关类支持快速随机访问。在ArrayList中，我们即可以通过元素的序号快速获取元素对象——这就是快速随机访问。稍后，我们会比较List的“快速随机访问”和“通过Iterator迭代器访问”的效率。
Cloneable:实现该接口的类可以对该类的实例进行克隆（按字段进行复制）
Serializable：ArrayList支持序列化，能通过序列化去传输。
(2.2)ArrayList属性

    private static final long serialVersionUID = 8683452581122892189L;
    private static final int DEFAULT_CAPACITY = 10;     //默认的初始容量
    private static final Object[] EMPTY_ELEMENTDATA = {};   //共享的空数组实例
    /**
     * 储存ArrayList元素的数组缓冲区。ArrayList的容量就是该缓冲数组的长度。任何以EMPTY_ELEMENTDATA作为
     * 数据元素的空ArrayList，在他们添加第一个元素的时候，都将被扩展至DEFAULT_CAPACITY(默认为10)长度。
     */
    transient Object[] elementData;
    private int size;   //ArrayList的大小,即他所包含的元素的个数

从ArrayList的属性元素我们可以看出，他的内部是由一个数组(elementData)实现的。这里需要说明一下transient Object[] elementData;这句中的transient关键字：
  我们都知道一个对象只要实现了Serilizable接口，这个对象就可以被序列化，java的这种序列化模式为开发者提供了很多便利，我们可以不必关系具体序列化的过程，只要这个类实现了Serilizable接口，这个类的所有属性和方法都会自动序列化。
  然而在实际开发过程中，我们常常会遇到这样的问题，这个类的有些属性需要序列化，而其他属性不需要被序列化，打个比方，如果一个用户有一些敏感信息（如密码，银行卡号等），为了安全起见，不希望在网络操作（主要涉及到序列化操作，本地序列化缓存也适用）中被传输，这些信息对应的变量就可以加上transient关键字。换句话说，这个字段的生命周期仅存于调用者的内存中而不会写到磁盘里持久化。
  总之，java 的transient关键字为我们提供了便利，你只需要实现Serilizable接口，将不需要序列化的属性前添加关键字transient，序列化对象的时候，这个属性就不会序列化到指定的目的地中。
(3.1)ArrayList构造方法

    public ArrayList(int initialCapacity) {
        super();
        if (initialCapacity < 0)
            throw new IllegalArgumentException("Illegal Capacity: "+
                                               initialCapacity);
        this.elementData = new Object[initialCapacity];
    }

    public ArrayList() {
        super();
        this.elementData = EMPTY_ELEMENTDATA;   //EMPTY_ELEMENTDATA等于10，前面说过
    }

    public ArrayList(Collection<? extends E> c) {
        elementData = c.toArray();
        size = elementData.length;
        // c.toArray might (incorrectly) not return Object[] (see 6260652)
        if (elementData.getClass() != Object[].class)
            elementData = Arrays.copyOf(elementData, size, Object[].class);
    }

可以看到ArrayList有三种构造方法:
  ①指定长度的初始化
  ②初始化一个空ArrayList,此时会自动将该初始化的ArrayList长度变为默认长度10。
  ③将指定的集合作为参数提供给初始化的ArrayList，并在该构造函数内部，先通过toArray将该集合强制转化为Object类型，然后通过Arrays.copyOf方法将其赋给elementData，也就是ArrayList缓存元素的地方。
(3.4)ArrayList的增加

    public boolean add(E e) {
        ensureCapacityInternal(size + 1);  //   扩容检查，确保当前数组在扩容之后可以容纳它的参数个大小的元素
        elementData[size++] = e;    // 将e增加至list的数据尾部，容量+1
        return true;
    }

    public void add(int index, E element) {     //在指定位置添加一个元素
        if (index > size || index < 0)      //判断是否越界
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
        // 对数组进行复制处理，目的就是空出index的位置插入element，并将index后的元素位移一个位置
        ensureCapacityInternal(size + 1);  // 扩容检查
        System.arraycopy(elementData, index, elementData, index + 1,size - index);
        elementData[index] = element;   //将元素添加到指定的位置
        size++;         //容量+1
    }

    public boolean addAll(Collection<? extends E> c) {  //将整个collection集合和添加到List结尾
        Object[] a = c.toArray();   //将c转化成Object类数组
        int numNew = a.length;
        ensureCapacityInternal(size + numNew);  //扩容检查
        System.arraycopy(a, 0, elementData, size, numNew);  //将c添加到list尾部
        size += numNew;     //更新当前容器大小
        return numNew != 0;
    }

    public boolean addAll(int index, Collection<? extends E> c) {   //在指定额索引处添加整个集合
        if (index > size || index < 0)
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));

        Object[] a = c.toArray();
        int numNew = a.length;
        ensureCapacityInternal(size + numNew);  // 扩容检查

        int numMoved = size - index;
        if (numMoved > 0)
            System.arraycopy(elementData, index, elementData, index + numNew,numMoved);

        System.arraycopy(a, 0, elementData, index, numNew);
        size += numNew;
        return numNew != 0;
    }

这里我们需要注意的是~~在数组的增加过程中，有两个过程是是比较耗费性能的：数组扩容(ensureCapacityInternal)与数组复制(System.arraycopy),这两个步骤在上面四个添加方法中都存在，待会我们会详细分析。
(3.5)ArrayList的删除

    public E remove(int index) {    //根据索引位置删除元素
        if (index >= size)      //越界检查
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));

        modCount++;
        E oldValue = (E) elementData[index];    //去除要删除的元素，该方法最终会返回这个值

        int numMoved = size - index - 1;    //计算数组要复制的值的数量
        if (numMoved > 0)
            System.arraycopy(elementData, index+1, elementData, index,numMoved);    //复制数组
        //数组最后一个元素置空，让垃圾回收器工作。因为删了一个元素，index之后的元素都往前移动了一个位置
        elementData[--size] = null; // clear to let GC do its work

        return oldValue;
    }

    public boolean remove(Object o) {   //根据内容删除，只删除匹配的那个
        if (o == null) {    //对要删除的元素进行是否为null的判断
            for (int index = 0; index < size; index++)  //遍历数组，掘地三尺找这个要删除的null元素
                if (elementData[index] == null) {   //找到null值了.(注意这个null值需要用"=="判断)
                    fastRemove(index);
                    return true;
                }
        } else {
            for (int index = 0; index < size; index++)
                if (o.equals(elementData[index])) { //非null是用.equals()比较
                    fastRemove(index);
                    return true;
                }
        }
        return false;
    }

    private void fastRemove(int index) {
        modCount++;
        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
    }

增加和删除使我们在ArrayLisy中比较常用的两个方法。下面我们来说说上面遗留的那个关于扩容和复制的问题。首先我们来看看ensureCapacityInternal方法的源码:

    private void ensureCapacityInternal(int minCapacity) {  //minCapacity就是我们需要的最小容量
        if (elementData == EMPTY_ELEMENTDATA) { //如果此时elementData等于空数组
            minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);  //如果minCapacity比默认值10小，则
                                //minCapacity为10，否则为他自己。
        }

        ensureExplicitCapacity(minCapacity);
    }

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

        // overflow-conscious code
        //如果当前的数组长度小于我们所需要的minCapacity值(当前数组长度不够)，则进行扩容
        if (minCapacity - elementData.length > 0)
            grow(minCapacity);
    }

    private void grow(int minCapacity) {
        // overflow-conscious code
        int oldCapacity = elementData.length;   //oldCapacity等于当前数组的长度
        //oldCapacity >> 1，表示二进制的向右移一位，相当于十进制的除以2
        int newCapacity = oldCapacity + (oldCapacity >> 1); //newCapacity = 1.5 * oldCapacity
        if (newCapacity - minCapacity < 0)
            newCapacity = minCapacity;  //如果此时newCapacity还是小于我们所需要的minCapacity，那就让他等于minCapacity
        if (newCapacity - MAX_ARRAY_SIZE > 0)
            newCapacity = hugeCapacity(minCapacity);
        // minCapacity is usually close to size, so this is a win:
        //以这个新的长度为标准重新创建，将原来数组中的元素拷贝一份到新的数组中去。Arrays.copyOf底层实现是System.arrayCopy()
        elementData = Arrays.copyOf(elementData, newCapacity);
    }

扩容的方法中包含三个个过程:
  ①判断需要的大小(minCapacity)是否超出了默认长度10.
  ②超出了就开始扩容，用他的1.5倍长度去和minCapacity作比较(有些java版本是2.5倍)。
  ③如果1.5倍大小还是小于所需要的minCapacity大小，那就将原来的元素复制到一个以minCapacity为长度的新数组中，并将elementData引用指向这个新数组。
  可以看到，扩容的过程伴随着数组的复制。如果数组初试容量过小，假设为默认的10个大小，而我们使用ArrayList的操作时需要不断的增加元素。在这种场景下，不断的增加，意味着数组需要不断的进行扩容，扩容的过程就是数组拷贝System.arraycopy的过程，每一次扩容就会开辟一块新的内存空间和数据的复制移动(但是数组复制不需要开辟新内存空间，只需将数据进行复制)，这样势必对性能造成影响。那么在这种以写为主（写会扩容，删不会缩容）场景下，提前预知性的设置一个大容量，便可减少扩容的次数，提高了性能。需要注意一点的是ensureCapacity()方法是public的，我们可以通过它手动的增加容量。
  增加元素可能会进行扩容，而删除元素却不会进行缩容，如果在以删除为主的场景下使用list，一直不停的删除而很少进行增加，或者数组进行一次大扩容后，我们后续只使用了几个空间，那就会造成控件的极大浪费。这个时候我们就可以将底层的数组elementData的容量调整为当前实际元素的大小(缩容)，来释放空间。

    public void trimToSize() {
        modCount++;
        if (size < elementData.length) {
            elementData = Arrays.copyOf(elementData, size);
        }
    }

总结一下:
  ArrayList底层以数组实现，允许重复，默认第一次插入元素时创建数组的大小为10，超出限制时会增加50%的容量，每次扩容都底层采用System.arrayCopy()复制到新的数组，初始化时最好能给出数组大小的预估值(采用给定值初始化)。
(3.6)ArrayList的遍历方式
ArrayList支持三种遍历方式
①通过迭代器Itertor去遍历
②随机访问，通过索引值去遍历,由于ArrayList实现了RandomAccess接口，它支持通过索引值去随机访问元素。
③foreach循环遍历
  下面我们用三段程序来测试这三种遍历方法哪一个效率最高，同时展示三种遍历的写法。为了测量更为精准,我们新建三个类分别测试——randomAccessTest.java；iteratorTest.java；foreachTest.java。同时我们采用多次测量(笔者用的eclipse测试时，测试结果经常跳票)并采用纳秒计时(毫秒误差惨不忍睹)。

public class randomAccessTest {
    private static long startTime;
    private static long endTime;

    public static void main(String[] args){
        List list  = new ArrayList();
        for(int i=0; i<1000; i++){
            list.add(i);
        }
        startTime = System.nanoTime();
        randomAccess(list);
        endTime = System.nanoTime();
        long time = endTime - startTime;
        System.out.println("randomAccessTime = " + time + "ns");
    }

    public static void randomAccess(List list){
        for(int i=0; i<list.size(); i++){

        }
    }
}

public class iteratorTest {
    private static long startTime;
    private static long endTime;

    public static void main(String[] args){
        List list  = new ArrayList();
        for(int i=0; i<1000; i++){
            list.add(i);
        }
        startTime = System.nanoTime();
        iterator(list);
        endTime = System.nanoTime();
        long time = endTime - startTime;
        System.out.println("iteratorTime = " + time + "ns");
    }

    public static void iterator(List list){
        Iterator iter = list.iterator();
        while( iter.hasNext()) {
            iter.next();
        }
    }
}

public class foreachTest {
    private static long startTime;
    private static long endTime;

    public static void main(String[] args){
        List list  = new ArrayList();
        for(int i=0; i<1000; i++){
            list.add(i);
        }
        startTime = System.nanoTime();
        foreach(list);
        endTime = System.nanoTime();
        long time = endTime - startTime;
        System.out.println("foreachTime = " + time + "ms");
    }

    public static void foreach(List list){
        for(Object obj:list) {

        }
    }
}

最终的结果大致稳定为:

randomAccessTime = 7x10^5 ns
iteratorTime = 6x10^6ns
foreachTime = 5x10^6ns

可以看到，虽然结果经常跳票，但八九不离十，randomAccessTime显然是用时最快的，毕竟少了一个数量级，这点机器还是没有算错的。也就是说遍历ArrayList时，使用随机访问(即，通过索引序号访问)效率最高,这点毋庸置疑，使用迭代器遍历的效率最低(这点是网上的答案，由于两者的测试结果处于同一个数量级，加上机器误差，这点笔者很难证实，读者可以自行验证)。
  其实产生上面结果，我们并不感到意外，因为关于randomAccessTime这个接口的注释中就已经很明确的说明了这个问题:

/**
 * ......
 * As a rule of thumb, a
 * <tt>List</tt> implementation should implement this interface if,
 * for typical instances of the class, this loop:
 * <pre>
 *     for (int i=0, n=list.size(); i < n; i++)
 *         list.get(i);
 * </pre>
 * runs faster than this loop:
 * <pre>
 *     for (Iterator i=list.iterator(); i.hasNext(); )
 *         i.next();
 * </pre>
 * /
 * 根据经验，一个list类的实现类应当实现这个接口，对于典型的该类的实例，上面的循环快于下面的循环。

(3)LinkedList源码解析

上面我们在讲双链表的时候已经讲了linkedList的remove(),add()等关键方法，以及LinkedList的一个结点(Node)的构成。下面我们来讲一下LinkedList剩余的一些知识点:
(3.1)LinkedList的头

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

可以看到LinkedList是一个继承自AbstractSequentialList的双链表，他可以被当做堆栈，队列(实现了List接口)，
双端队列(实现了Deque接口)使用。同时LinkedList 实现了Cloneable接口，即覆盖了函数clone()，能克隆。LinkedList 实现java.io.Serializable接口，这意味着LinkedList支持序列化，能通过序列化去传输。
(3.2)LinkedList的属性元素

    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;

其中size就是list的数量，和ArrayList一样。这个Node<E> first和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;
        }
    }

(3.3)LinkedList的构造函数

    /**构造一个空的构造函数，这个构造函数，也真够空的**/
    public LinkedList() {
    }

    /**构造一个包含指定collection元素的表，这些元素按照collection的迭代器返回的顺序排列**/
    public LinkedList(Collection<? extends E> c) {
        this();
        addAll(c);
    }

LinkedList就两个构造函数，一个空构造函数，一个包含指定collection的构造函数。
(3.4)LinkedList的增加方法
上面我们在讲双链表的时候讲过在指定位置插入元素的add(int index, E element)方法，现在我们补充一下其他几种添加方法:
①在双链表的尾部添加一个元素:

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

    void linkLast(E e) {
        final Node<E> l = last; //last表示双链表中的最后一个元素，l表示指向最后一个元素的引用
        final Node<E> newNode = new Node<>(l, e, null); //新建一个后继引用为空的新节点，后继为空，意味着他是最后一个元素
        last = newNode; //直接让这个新建的元素作为链表的最后一个元素就行了
        if (l == null)  //指向原本链表最后一个元素的引用l为空，说明原来的链表是一个空链表。
            first = newNode;    //此时让这个新建的结点元素最为第一个结点(就他一个啊)
        else
            l.next = newNode;   //否则的话，让原链表的后继引用指向我们新建的这个节点，插入完成
        size++;
        modCount++;
    }

②在指定索引处插入一个集合

    public boolean addAll(int index, Collection<? extends E> c) {
        checkPositionIndex(index);  //越域判断

        Object[] a = c.toArray();
        int numNew = a.length;      // 要插入元素的个数
        if (numNew == 0)
            return false;

        Node<E> pred, succ;     //申明两个节点类的前继，后继引用(这个循环就是在找出原列表中插入索引处的前后引用)
        if (index == size) {    //索引等于链表的长度，说明是要求插在链表的最后面
            succ = null;
            pred = last;        //此时后继引用为空，前继引用指向原链表的最后一个元素
        } else {
            succ = node(index); //否则后继引用指向原链表索引处的元素。node()方法我们之前讲过，二分法查找索引处元素
            pred = succ.prev;   //前继引用指向原链表索引处元素的前一个元素，完成插入
        }

        for (Object o : a) {    //遍历我们要插入的这个集合
            E e = (E) o;
            //新建一个结点，以pred作为前继引用，该for循环中每次遍历得到的collection集合中的e作为结点本身元素，
            //null作为后继引用。在第一次进行该循环时，通过上一个if的赋值，pred指向原链表中指定索引处的前一个元素。
            Node<E> newNode = new Node<>(pred, e, null);    //在第一次循环遍历的时候，这个新节点就是collection集合的第一个元素
            if (pred == null)   //如果pred为空，说明原链表为空
                first = newNode;    //新节点等于第一个节点
            else
                pred.next = newNode;    //否则，原链表中指定索引处的前一个元素 的后继引用指向这个新节点。
            pred = newNode; //然后将这个pred指向这个新的节点(在第一次循环中，这个新节点表示collection集合中的第一个元素)，相当于工作指针后移，然后重复上述过程。
        }

        //上述循环结束后，pred指针已经指向了collection集合的最后一个元素，此时由于succ没动过，因此他还是指向原链表中指定索引处的后一个元素
        if (succ == null) { //如果succ为null，和第一个if中的情况一样，说明这是在原链表的末尾插入元素
            last = pred;    //直接让此时的pred也就是collection中的最后一个元素作为插入后链表的最后一个元素就可以了
        } else {        //否则的话说明是在原链表中间插入元素
            pred.next = succ;   //此时让collection中最后一个元素的后继指针指向 原链表索引处的后一个元素，完成差诶工作
            succ.prev = pred;   //同时让succ的前继指针指向collection的最后一个元素，完成双向链表的建立
        }

        size += numNew; //增加链表长度
        modCount++;
        return true;
    }

这段代码中，注释已经写的很详细了，难点就是for (Object o : a)这个foreach循环中,我们插入的collection元素是如何建立双链表联系的，读者务必要仔细分析流程。
(3.5)LinkedList的删除方法
  删除的方法我们上面讲双链表的时候已经说的很详细了，这个没有什么好说的，大家可以翻上去复习一下。这里我们通过LinkedList的remove()方法的几种形式，来讲一下算法选型的问题。
  这个例子的来源于《数据结构与算法分析(java语言描述)》这本书，笔者觉得很典型。题目的要求是，给出一个线性表，将表中所有偶数项全部删除。
①首先第一种算法，使用普通for循环:

public class usuallyforTest {
    private static long startTime;
    private static long endTime;
    private static final int SIZE = 10000;

    public static void main(String[] args){

        List<Integer> arraylist = new ArrayList<Integer>(SIZE);
        List<Integer> linkedlist  = new LinkedList<Integer>();
        for(int i=0; i<SIZE; i++){
            linkedlist.add(i);
            arraylist.add(i);
        }
        startTime = System.currentTimeMillis();
        usuallyfor(linkedlist);
        endTime = System.currentTimeMillis();
        long linkedlistTime = endTime - startTime;
        System.out.println("usuallyforLinkedlistTime = " + linkedlistTime + "ms");

        startTime = System.currentTimeMillis();
        usuallyfor(arraylist);
        endTime = System.currentTimeMillis();
        long arraylistTime = endTime - startTime;
        System.out.println("usuallyforArraylistTime = " + arraylistTime + "ms");
    }

    public static void usuallyfor(List<Integer> list){
        for(int i=0; i<list.size(); i++){
            if(list.get(i) % 2 == 0){
                list.remove(i);
            }
        }
    }
}

运行的结果是:

usuallyforLinkedlistTime = 57ms
usuallyforArraylistTime = 7ms

如果我们将其中的线性表大小SIZE改为20000(扩大两倍)，得到结果为:

usuallyforLinkedlistTime = 232ms
usuallyforArraylistTime = 29ms

很显然，对于ArrayList和LinkedList而言，这个算法都是时间复杂度为O(N^2)的二次算法。

    public static void usuallyfor(List<Integer> list){
        for(int i=0; i<list.size(); i++){
            if(list.get(i) % 2 == 0){
                list.remove(i);
            }
        }
    }

这段代码中，对于LinkedList而言，list.get(i)方法是O(N)时间，慢在寻址；而他的remove()方法确实O(1)的。对于ArrayList而言，他的get(i)方法是O(1)的，但是remove(i)方法却是O(N)的，因为只要删除一个元素，后面的元素都要跟着向前移位，并伴随着数组的复制拷贝等耗时操作；但是他的get(i)却是O(1)的。
  所以无论对谁，这种算法都不是明智的选择。但是整体上来看，ArrayList用时更少一些(1/8的量)。
②使用迭代器Iterator

public class iteratorTest {
    private static long startTime;
    private static long endTime;
    private static final int SIZE = 10000;

    public static void main(String[] args){

        List<Integer> arraylist = new ArrayList<Integer>(SIZE);
        List<Integer> linkedlist  = new LinkedList<Integer>();
        for(int i=0; i<SIZE; i++){
            linkedlist.add(i);
            arraylist.add(i);
        }
        startTime = System.currentTimeMillis();
        iterator(linkedlist);
        endTime = System.currentTimeMillis();
        long linkedlistTime = endTime - startTime;
        System.out.println("iteratorLinkedlistTime = " + linkedlistTime + "ms");

        startTime = System.currentTimeMillis();
        iterator(arraylist);
        endTime = System.currentTimeMillis();
        long arraylistTime = endTime - startTime;
        System.out.println("iteratorArraylistTime = " + arraylistTime + "ms");
    }

    public static void iterator(List<Integer> list){
        Iterator<Integer> iter = list.iterator();
        while( iter.hasNext()) {
            if(iter.next() % 2 == 0){
                iter.remove();
            }
        }
    }
}

结果为:

iteratorLinkedlistTime = 2ms
iteratorArraylistTime = 10ms

将其中的线性表大小SIZE改为20000(扩大两倍)，得到结果为:

iteratorLinkedlistTime = 4ms
iteratorArraylistTime = 34ms

显然，此时LikedList变成了O(N)一次时间，而ArrayList变成了O(N^2)二次时间，并且LinkedList所用的时间大大小于ArrayList所用的时间。为什么呢？因为此时用迭代器循环遍历时，对于linkdList的next()方法，是O(1)时间关系，remove()也是一次时间关系；但是对于ArrayList而言，rwmove()仍然是O(N)时间关系。
  从这两个例子中我们可以体验到，算法的强大之处，实现同样功能，采用不同的算法，成败异变，功业相反~~妙哉！

3.总结——ArrayList和LinkedList的比较

写的太多了，不知道该怎么总结，这里直接照搬一下Java集合干货系列-（二）LinkedList源码解析这篇文章最后的总结，这篇文章写得很好，推荐读者去看一下
  (1)顺序插入速度ArrayList会比较快，因为ArrayList是基于数组实现的，数组是事先new好的，只要往指定位置塞一个数据就好了；LinkedList则不同，每次顺序插入的时候LinkedList将new一个对象出来，如果对象比较大，那么new的时间势必会长一点，再加上一些引用赋值的操作，所以顺序插入LinkedList必然慢于ArrayList
  (2)基于上一点，因为LinkedList里面不仅维护了待插入的元素，还维护了Entry的前置Entry和后继Entry，如果一个LinkedList中的Entry非常多，那么LinkedList将比ArrayList更耗费一些内存
  (3)数据遍历的速度，看最后一部分，这里就不细讲了，结论是：使用各自遍历效率最高的方式，ArrayList的遍历效率会比LinkedList的遍历效率高一些
  (4)有些说法认为LinkedList做插入和删除更快，这种说法其实是不准确的：
  ①LinkedList做插入、删除的时候，慢在寻址，快在只需要改变Node前后引用
  ②ArrayList做插入、删除的时候，慢在数组元素的批量copy，快在寻址
  所以，如果待插入、删除的元素是在数据结构的前半段尤其是非常靠前的位置的时候，LinkedList的效率将大大快过ArrayList，因为ArrayList将批量copy大量的元素；越往后，对于LinkedList来说，因为它是双向链表，所以在第2个元素后面插入一个数据和在倒数第2个元素后面插入一个元素在效率上基本没有差别，但是ArrayList由于要批量copy的元素越来越少，操作速度必然追上乃至超过LinkedList。

从这个分析看出，如果你十分确定你插入、删除的元素是在前半段，那么就使用LinkedList；如果你十分确定你删除、删除的元素在比较靠后的位置，那么可以考虑使用ArrayList。如果你不能确定你要做的插入、删除是在哪儿呢？那还是建议你使用LinkedList吧，因为一来LinkedList整体插入、删除的执行效率比较稳定，没有ArrayList这种越往后越快的情况；二来插入元素的时候，弄得不好ArrayList就要进行一次扩容，记住，ArrayList底层数组扩容是一个既消耗时间又消耗空间的操作。

站在巨人的肩膀上摘苹果:
Java集合干货系列-（一）ArrayList源码解析
Java集合干货系列-（二）LinkedList源码解析
《大话数据结构》
《数据结构与算法分析(java语言描述)》
《疯狂java讲义》