ArrayList和LinkList都是一种单列集合，他们都实现了List接口，List提供了增删改查等一系列处理有序化可冗余集合，因此ArrayList跟LinkList共同特点是有序性，可冗余性。这里的有序性指的是加入元素顺序跟取出的顺序的有序而非元素大小或其他属性的有序性。
首先来了解一下ArrayList。ArrayList底层通过Object数组实现，因此我们可以认为ArrayList里面的元素逻辑相邻同时物理相邻，便于读取操作而不利于插入操作。下面是ArrayList的继承关系。
Java.util.AbstractCollection
java.util.AbstractList
java.util.ArrayList
下面通过源代码来了解一下ArrayList的底层实现原理。

一、ArrayList

通过JAVA提供的API我们可以看到ArrayList提供了三种构造方法，无参数时使用默认Object数组大小 10 。带一个单列集合的构造方法，Coolection是所有单列集合的根接口它提供了单列集合的所有特性方法。带一个整形的构造方法在使用时创建提供的initialCapacity大小的数组。

1、属性

1、在JDK12.0.1中定义了下面这一个属性没有任何备注，明明是静态公有，API也没有进行说明。有人说他是相当于java类的身份证，主要用于版本控制，serialVersionUID作用是序列化时保持版本的兼容性，即在版本升级时反序列化仍保持对象的唯一性。暂且就这么理解吧。

 private static final long serialVersionUID = 8683452581122892189L;

2、顾名思义默认容量，初始化为10，私有。

private static final int DEFAULT_CAPACITY = 10;

3、注释为Shared empty array instance used for empty instances用于空实例的共享空数组实例。私有属性理解为空元素Object集。

private static final Object[] EMPTY_ELEMENTDATA = {};

4、共享的空数组实例，用于默认大小的空实例（10）。我们将其与EMPTY_ELEMENTDATA区别开来，以了解添加第一个元素时需要填充多少。

 private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

5、存储ArrayList元素的数组缓冲区。ArrayList的容量是此数组缓冲区的长度。添加第一个元素时，任何具有elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA 的空ArrayList都将扩展为DEFAULT_CAPACITY。简而言之就是为了在添加时扩充数组如何实现数组扩充等会再谈。非私有是为了简化嵌套类的访问，提高效率。

 transient Object[] elementData;

6、size一般都是指大小的意思此处也不列外它表示ArrayList元素的个数，同时它也是私有的增加了安全性。

  private int size;

7、API中有一个modCount翻译为模数它是ArrayList的父类中定义的protected类型的成员变量，表示为此表被结构修改的次数，也就是改变大小等扰乱方式是的正常迭代发生错误。

2、方法

1、带参数的构造方法，如果创建大小 > 0 则新建initialCapacity个Object数组，等于0使用默认大小的数组(10)，< 0 则抛出不合法参数异常。

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

2、无参数构造方法，创建默认大小的Object素组（10）。

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

3、首先将集合转换成数组赋值给elemDate，然后判断集合元素的数量是否等于0，若等于0 ，再判断格式是否正确，不正确的话修改为正确格式，否者将赋值为空数组。

public ArrayList(Collection<? extends E> c) {
        elementData = c.toArray();
        if ((size = elementData.length) != 0) {
            if (elementData.getClass() != Object[].class)
                elementData = Arrays.copyOf(elementData, size, Object[].class);
        } else {
            this.elementData = EMPTY_ELEMENTDATA;
        }
    }

4、可以调用的方法、返回值类型、使用方式。其中重点了解一下add get remove set的实现原理，以及部分方法的的作用。 QQ图片20191107201026.png
5、add方法，我们先前说了，ArrayList是一个可以扩容的集合，具体是怎么进行扩容的在add方法中可以体现出来。首先在源代码496实现了像集合添加一个元素的操作如下：

public boolean add(E e) {
        modCount++;
        add(e, elementData, size);
        return true;
    }

modCount表示的修改次数加1，理解为烦是改变当前集合特性的都会视为对集合的一次修改，然后调用 add(e, elementData, size)方法具体再来看一下源代码

 private void add(E e, Object[] elementData, int s) {
        if (s == elementData.length)
            elementData = grow();
        elementData[s] = e;
        size = s + 1;
    }

通过代码能够发现add(e, elementData, size)是一个私有的方法意味着只能对当前对象使用Object[] elementData是当前对象数组s是元素个数如果s=对象数组个数的话会调用 grow()方法此方法是ArrayList继承过来的父类方法，也就是将新开辟一个对象实例用来数组存放一个对象从而实现扩容添加元素（因为之前已经进行过删除操作做造成s != length）。
6、remove是进行删除操作其底层通过删除一个对象然后将其余的数组移动从而实现元素之间的逻辑相邻以及物理相邻。set方法的实现原理跟上一篇文章讲提到的顺序表数据结构相似具体参考上篇文章

3、ArrayList扩容

在源代码的属性里面有一行定义了pravite静态变量

 private static final int DEFAULT_CAPACITY = 10;

此处我们说他是默认的容量，有一个概念必须要清楚的是，容量和他的元数量是两个完全不一样的概念，元素的数量用size来表示容量是必须大于等于元素的数量，在无参构造方法里面我们还不能准确的看出来具体的扩容原理另外值得注意的是private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};这个数组，他就是一个长度为0 的Object 数组这是一个默认的静态final修饰的空数组实例每一个ArrayList实例被new出来之后一开始都是共享这个空数组实例的。
在add方法里面

 private void add(E e, Object[] elementData, int s) {
        if (s == elementData.length)
            elementData = grow();
        elementData[s] = e;
        size = s + 1;
    }

他首先判断长度跟添加最小需要的容量是否匹配由于长度是小于等于容量的，所以只需判断s是否等于elementData.length就能确定是否需要扩容，需要则扩容，不需要则直接在尾部添加，同时size+1，grow就是一个扩容方法，具体是实现参见

private Object[] grow(int minCapacity) {
        return elementData = Arrays.copyOf(elementData,
                                           newCapacity(minCapacity));
    }
    private Object[] grow() {
        return grow(size + 1);
    }

解释一下copyOf就是将当前的引用空间指向一个另外一个属更大的引用空间。而 newCapacity方法就是具体的扩容空间，该空间容量就是 newCapacity里面的newCapacity大小。

 private int newCapacity(int minCapacity) {
        // overflow-conscious code
        int oldCapacity = elementData.length;
        int newCapacity = oldCapacity + (oldCapacity >> 1);
        if (newCapacity - minCapacity <= 0) {
            if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA)
                return Math.max(DEFAULT_CAPACITY, minCapacity);
            if (minCapacity < 0) // overflow
                throw new OutOfMemoryError();
            return minCapacity;
        }
        return (newCapacity - MAX_ARRAY_SIZE <= 0)
            ? newCapacity
            : hugeCapacity(minCapacity);
    }

由第4行可知江原长度左移一位在二进制里面相当于乘以 ArrayList与LinkedList - 图3 ，也就是说以1.5倍扩增具体是否是1.5倍还要看后面的判断取最小扩容值。几个参数了解一下：oldCapacity 代表数组圆肉容量大小，newCapacity 代表原有容量扩大1.5倍之后的大小，第一个判断表示原有容量扩充1.5倍之后任然小于最小扩充要求那么newCapacity将被指定为最小扩充要求，之后如果需求值小于0 抛出异常。由此可以得知ArrayList的最大容量是有上限的，上限就是int的最大值。但其实但定义MAX_ARRAY_SIZE的时候将它设置为Integer.Max_VALUE - 8，因此它的最大容量应该是int的最大值减8。

4、综上

ArrayList是一个通过数组实现的数据集合，由于数组访问的快速特点为了程序的效率更高通常适用于访问添加，因为插入删除会移动其他元素从而会造成时间复杂度过高因而为不适用于插入删除。另外由于在JDK1.2之前没有ArrayList通常会用它与vector进行比较，vector同样是通过数组实现组要区别在以下方面vector慢、安全、提供了线程同步，在多线程应用程序中是安全的；ArrayList主要是快程序效率高，但是在多线程情况下ArrayList安全性得不到保障。

二、LinkedList

LinkedList底层是通过node节点实现，它是一个链式存储结构通常说成是双向循环链表，它也是一个有序的集合，但是是一个逻辑相邻物理不相邻的一个集合体，由于具有双向循环链表的物理特性有利于数据的增加删除操作，下面是它的继承关系：

  - [java.util.AbstractCollection](../../java/util/AbstractCollection.html)<E>
     - [java.util.AbstractList](../../java/util/AbstractList.html)<E>
           - [java.util.AbstractSequentialList](../../java/util/AbstractSequentialList.html)<E>
              - java.util.LinkedList<E>

双链表实现了List和Deque接口。实现所有可选列表操作，并允许所有元素（包括null ），所有的操作都能像双向列表一样预期。索引到列表中的操作将从开始或结束遍历列表，以更接近指定的索引为准。

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

这是LinkedList的节点，他是LinkedList的是由类中类节点，其构造方法实现原理跟我们自己写的双向循环链表差不多，具体看一下数据结构里面写到的双向循环链表的文档。

 transient Node<E> first;
 transient Node<E> last;

在属性里面看到了它为了增加LinkedList 的使用效率加了一个第一个节点和最后一个节点。

LinkedList方法

LinkedList为我们提供了很多的方法，具体实现跟数据结构里面的增加删除节点操作相差无几，暂且就不介绍以后需要时在做补充。

三、区别

通过上面对ArrayList和LinkedList的理解，他们的区别在于ArrayList通过数组实现更方便查找，而LinkedList通过节点来实现，更方便插入删除，所以我们在使用他们的时候在不考虑多线程条件下，视开发环境来合理选择使用哪一个，同时由于他们都是实现了的List接口所以在开发中需要交替使用时可以用List接口定义视情况选择。