arraylist和linklist原理，区别

一、ArrayList实现原理

​

ArrayList就是动态数组，ArrayList并不是线程安全的，允许 null 的存在，是有序的，初始容量大小为10，当超过容量后，会进行扩容，以原来容量的1.5倍来扩容，如之前的容量为10，下次扩容扩大到10 + 5，ArrayList的最大长度为 2^32 .当删除数组中间的元素，后面的元素都会向前移动。随着向ArrayList中不断添加元素，其容量也自动增长。自动增长会带来数据向新数组的重新拷贝，这种操作的代价是很高的，因此，如果可预知数据量的多少，可在构造ArrayList时指定其容量。在添加大量元素 前，应用程序也可以使用ensureCapacity操作来增加ArrayList实例的容量，这可以减少递增式再分配的数量。

​

注意：注释是说构造一个容量大小为 10 的空的 list 集合，但构造函数了只是给 elementData 赋值了一个空的数组，其实是在第一次添加元素时容量扩大至 10 的。

​

二、LinkedList底层实现和原理

​

LinkedList类是List接口的实现类，它是一个集合，可以根据索引来随机的访问集合中的元素，还实现了Deque接口，它还是一个队列，可以被当成双端队列来使用。虽然LinkedList是一个List集合，但是它的实现方式和ArrayList是完全不同的，ArrayList的底层是通过一个动态的Object[]数组来实现的，而LinkedList的底层是通过链表来实现的，因此它的随机访问速度是比较差的，但是它的删除，插入操作会很快。

​

实现接口

​

Serializable, Cloneable, Iterable, Collection, Deque, List, Queue

源码：

public class LinkedList<E>extends AbstractSequentialList<E>
    implements List<E>, Deque<E>, Cloneable, java.io.Serializable
{
    transient int size = 0;   //LinkedList中存放的元素个数

    transient Node<E> first;  //头节点
    
    transient Node<E> last;   //尾节点

    //构造方法，创建一个空的列表
    public LinkedList() {
    }

    //将一个指定的集合添加到LinkedList中，先完成初始化，在调用添加操作
    public LinkedList(Collection<? extends E> c) {
        this();
        addAll(c);
    }
    。。。。。。
}

构造方法：

​

LinkedList()

​

LinkedList(Collection c)

​

LinkedList没有长度的概念，所以不存在容量不足的问题，也不存在扩容的问题，因此不需要提供初始化大小的构造方法，因此值提供了两个方法，一个是无参构造方法，初始一个LinkedList对象，和将指定的集合元素转化为LinkedList构造方法。

​

添加方法：默认尾部

public boolean add(E e) {
     linkLast(e);
     return true;
}
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++;
}

删除方法：

​

先循环遍历列表，找到item == o 的节点，在调用unlink()方法删除。

​

总结：

​

LinkedList是一个功能很强大的类，可以被当作List集合，双端队列和栈来使用。LinkedList底层使用链表来保存集合中的元素，因此随机访问的性能较差，但是插入删除时性能非常的出色。

LinkList 以链表作为底层。

​

使用无参构造创建集合后，第一次添加元素会将该元素记录为first节点和last节点；

​

当不是第一次添加元素且集合中有元素时，会默认将元素添加到最后位置；

​

当插入元素时，会先判断插入的元素是否为最后一个，是最后一个则直接调用addLast，若不是则底层会先得到插入之前该位置的节点，然后创建新节点（插入的元素节点），新节点的上一节点地址记录插入之前该位置的节点的上一节点地址，新节点的下一节点地址记录插入之前该位置的节点；然后将插入之前该位置的节点的上一节点地址改为新节点；将插入之前该位置的节点的上一节点的下一节点地址改为新节点；（简单来说就是将插入位置的上一节点地址记录新的节点，将插入位置的上一个节点的下一节点地址记录新的节点，新节点的上一节点地址记录插入前该位置的上一节点地址，下一节点地址记录插入前该位置节点。）