每日一问：ArrayList和LinkedList的区别

---

ArrayList

• ArrayList是一个数组队列，相当于动态数组。与Java中的数组相比，它的容量能动态增长。它继承于AbstractList，实现了List，RandomAccess，Cloneable，java.io.Serializable这些接口。

• ArrayList继承了AbstractList，实现了List。它是一个数组队列，提供了相关的添加、删除、修改、遍历等功能。

• ArrayList实现了RandmoAccess接口，即提供了随机访问的功能。RandmoAccess是java中用来被List实现，为List提供快速访问功能的。在ArrayList中，我们即可以通过元素的序号快速获取元素对象；这就是快速随机访问。

• ArrayList实现了Cloneable接口，即覆盖了函数clone()，能被克隆。

• ArrayList实现了java.io.Serializable接口，这意味着ArrayList支持序列化，能通过序列化去传输。

• 注意：ArrayList中的操作不是线程安全的！所以，建议在单线程中使用，多线程情况下可以选择CopyOnWriteArrayList或者使用Collections中的synchronizedList方法将其包装成一个线程安全的List。

• ArrayList自己实现了序列化和反序列化，因为它实现了writeObject和readObject方法。

• ArrayList基于数组实现，会自动扩容。

• 添加元素时会自己判断是否需要扩容，最好指定一个大概的大小，防止后面多次扩容带来的内存消耗；删除元素时不会减少容量，删除元素时，将删除掉的位置元素置为null，下次gc就会自动回收这些元素所占的空间。

• ArrayList是线程不安全的。

• 使用iterator遍历可能会引发多线程异常。

LinkedList

LinkedList 是链表实现的线性表（双链表）。
LinkedList 特点：

• 双向链表实现
• 元素时有序的，输出顺序与输入顺序一致
• 允许元素为 null
• 要找到某个结点，必须从头开始遍历。（查询慢，增删快）
  和 ArrayList 一样，不是同步容器

链表：链表是一种重要的数据结构，有单链表和双链表之分

• 单链表（单向链表）：由两部分组成 数据域（Data）和结点域(Node),单链表就像是一条打了很多结的绳子，每一个绳结相当于一个结点，每个节结点间都有绳子连接，这样原理的实现是通过Node结点区的头指针head实现的，每个结点都有一个指针，每个节点指针的指向都是指向自身结点的下一个结点，最后一个结点的head指向为null,这样一来就连成了上述所说绳子一样的链，对单链表的操作只能从一端开始，如果需要查找链表中的某一个结点，则需要从头开始进行遍历。

• 双链表（双向链表）：双链表和单链表相比，多了一个指向尾指针（tail），双链表的每个结点都有一个头指针head和尾指针tail,双链表相比单链表更容易操作，双链表结点的首结点的head指向为null，tail指向下一个节点的tail;尾结点的head指向前一个结点的head，tail 指向为null，是双向的关系；
  在单链表中若需要查找某一个元素时，都必须从第一个元素开始进行查找，而双向链表除开头节点和最后一个节点外每个节点中储存有两个指针，这连个指针分别指向前一个节点的地址和后一个节点的地址，这样无论通过那个节点都能够寻找到其他的节点。

• 插入删除不需要移动元素外，可以原地插入删除

• 可以在结构的前后插入数据

• 可以双向遍历

ArrayList和LinkedList区别

• 底层数据结构：ArrayList底层使用的是数组；LinkedList底层使用的是双向链表；

• 插入和删除元素操作：ArrayList采用的是数组存储，所以插入和删除元素是跟元素的位置有关系。LinkedList采用的是链表存储，删除元素是不受元素位置影响的；如果是要在指定位置i插入和删除的话（（add(int index，E element））时间复杂度近似为O(n)，因为需要先移动再插入。

• 随机访问：ArrayList对于随机元素访问的效率明显比LinkedList高。随机访问就是通过元素的索引来获取元素（也就是set和get(int index)方法）。

• 线程不安全：ArrayList和LinkedList都是不同步的，也就是说都是线程不安全的。

• 接口实现：ArrayList实现了RandomAccess可以支持随机元素访问，而LinkedList实现了Deque可以当做队列使用

• 内存空间占用情况：ArrayList的空间占用主要体现在list列表的末尾会有一定的容量空间，它的优势在于内存的连续性，CPU的内部缓存结构会缓存连续的内存片段，可以大幅度降低内存的性能开销，提高效率；LinkedList的空间占用体现在每一个元素都需要消耗空间内存，要存放前驱后继等数据。

• 当操作是在一列数据的后面添加数据而不是在前面或中间,并且需要随机地访问其中的元素时,使用ArrayList会提供比较好的性能；

• 当操作是在一列数据的前面或中间添加或删除数据,并且按照顺序访问其中的元素时,使用LinkedList会更好。