数组

数组性能最高，但是无法动态扩容，操作不方便。

ArrayList(jdk1.8)

实现了List 底层数据结构是一个动态数组。更适合随机读取数据。

初始化容量：10 当容量满的时候进行扩容：

private static final int DEFAULT_CAPACITY = 10;
int newCapacity = oldCapacity + (oldCapacity >> 1);

ArrayList 的底层是数组队列，相当于动态数组。与 Java 中的数组相比，它的容量能动态增长。在添加大量元素前，应用程序可以使用ensureCapacity操作来增加 ArrayList 实例的容量。这可以减少递增式再分配的数量。

它继承于 AbstractList，实现了 List, RandomAccess, Cloneable, java.io.Serializable 这些接口。

在我们学数据结构的时候就知道了线性表的顺序存储，插入删除元素的时间复杂度为O（n）,求表长以及增加元素，取第 i 元素的时间复杂度为O（1）

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

ArrayList 实现了RandomAccess 接口， RandomAccess 是一个标志接口，表明实现这个这个接口的 List 集合是支持快速随机访问的。在 ArrayList 中，我们即可以通过元素的序号快速获取元素对象，这就是快速随机访问。

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

ArrayList 实现java.io.Serializable 接口，这意味着ArrayList支持序列化，能通过序列化去传输。和 Vector 不同，ArrayList 中的操作不是线程安全的！所以，建议在单线程中才使用 ArrayList，而在多线程中可以选择 Vector 或者 CopyOnWriteArrayList。

LinkedList

实现了List, Deque两个接口

底层数据结构是一个双向链表。可以在任何位置进行高效地插入和删除操作的有序序列。

ArrayList和LinkedList区别

  1. **线程安全：**ArrayList 和 LinkedList 都是不同步的，也就是不保证线程安全；
  2. **数据结构：**ArrayList是实现了基于动态数组的数据结构，LinkedList基于双向链表的数据结构。
  3. **是否支持快速随机访问：**对于随机访问get和set，ArrayList优于LinkedList，时间复杂度位O(1)，因为LinkedList要移动指针，ArrayList口语通过下标访问。
  4. 对于新增和删除操作add和remove，LinkedList比较占优势，时间复杂度位O(1)，因为ArrayList要移动数据，而LinkedList。
  5. 内存空间占用： ArrayList的空 间浪费主要体现在在list列表的结尾会预留一定的容量空间，而LinkedList的空间花费则体现在它的每一个元素都需要消耗比ArrayList更多的空间（因为要存放直接后继和直接前驱以及数据）。