集合

ArrayList和LinkedList的区别是什么？

❒ 底层数据结构
✔ ArrayList 是动态数组的数据结构实现。
✔ LinkedList 是双向链表的数据结构实现。

❒ 操作数据效率
✔ ArrayList按照下标查询的时间复杂度O(1)[内存是连续的，根据寻址公式]，LinkedList不支持下标查询。
✔ 查找(未知索引)：ArrayList需要遍历，链表也需要链表，时间复杂度都是O(n)。

❒ 新增和删除
✔ ArrayList尾部插入和删除，时间复杂度是O(1)，其他部分增删需要挪动数组，时间复杂度是O(n)。
✔ LinkedList头尾节点增删时间复杂度是0(1)，其他都需要遍历链表，时间复杂度是O(n)。

❒ 内存空间占用
✔ ArrayList底层是数组，内存连续，节省内存。
✔ LinkedList 是双向链表需要存储数据，和两个指针，更占用内存。

❒ 线程安全
✔ ArrayList和LinkedList都不是线程安全的。
✔ 使用线程安全的 ArrayList，List syncArrayList = Collections.synchronizedList(new ArrayList())。
✔ 使用线程安全的 LinkedList，List syncLinkedList = Collections.synchronizedList(new LinkedList())。

❒ 底层数据结构
✔ ArrayList 是动态数组的数据结构实现。
✔ LinkedList 是双向链表的数据结构实现。

❒ 操作数据效率
✔ ArrayList按下标查询的时间复杂度O(1)， LinkedList不支持下标查询。
✔ 查找（未知索引）： ArrayList需要遍历，链表也需要链表，时间复杂度都是O(n)。
✔ ArrayList尾部插入和删除，时间复杂度是O(1)；其他部分增删需要挪动数组，时间复杂度是O(n)。
✔ LinkedList头尾节点增删时间复杂度是O(1)，其他都需要遍历链表，时间复杂度是O(n)。

❒ 内存空间占用
✔ ArrayList底层是数组，内存连续，节省内存。
✔ LinkedList 是双向链表需要存储数据，和两个指针，更占用内存。

❒ 线程安全
✔ ArrayList和LinkedList都不是线程安全的。
✔ List syncArrayList = Collections.synchronizedList(new ArrayList())。
✔ List syncLinkedList = Collections.synchronizedList(new LinkedList())。

查多增少用数组，头尾增删用链表。 
数据固定选数组，数据狂涨选链表。 
内存连续 CPU 快，指针跳转效率低。