本文已收录到 GitHub · AndroidFamily，有 Android 进阶知识体系，欢迎 Star。技术和职场问题，请关注公众号 [彭旭锐] 加入 Android 交流群。
前言
大家好，我是小彭。
在前面的文章里，我们学习了很多数据结构与算法思想。在实际的业务开发中，往往不需要我们手写数据结构，而是直接使用标准库的数据结构 / 容器类。
在后续的文章里，我们将以 Java 语言为例，分析从 ArrayList 到 LinkedHashMap 等一系列标准库容器类，最后再有一篇总结回顾，请关注。
学习路线图：
1. 说一下 ArrayList 和 LinkedList 的区别？
-
1、数据结构： 在数据结构上，ArrayList 和 LinkedList 都是 “线性表”，都继承于 Java 的
List接口。另外 LinkedList 还实现了 Java 的Deque接口，是基于链表的栈或队列，与之对应的是ArrayDeque基于数组的栈或队列； -
2、线程安全： ArrayList 和 LinkedList 都不考虑线程同步，不保证线程安全；
-
3、底层实现： 在底层实现上，ArrayList 是基于动态数组的，而 LinkedList 是基于双向链表的。事实上，它们很多特性的区别都是因为底层实现不同引起的。比如说：
-
在遍历速度上： 数组是一块连续内存空间，基于局部性原理能够更好地命中 CPU 缓存行，而链表是离散的内存空间对缓存行不友好；
-
在访问速度上： 数组是一块连续内存空间，支持 O(1) 时间复杂度随机访问，而链表需要 O(n) 时间复杂度查找元素；
-
在添加和删除操作上： 如果是在数组的末尾操作只需要 O(1) 时间复杂度，但在数组中间操作需要搬运元素，所以需要 O(n)时间复杂度，而链表的删除操作本身只是修改引用指向，只需要 O(1) 时间复杂度（如果考虑查询被删除节点的时间，复杂度分析上依然是 O(n)，在工程分析上还是比数组快）；
-
额外内存消耗上： ArrayList 在数组的尾部增加了闲置位置，而 LinkedList 在节点上增加了前驱和后继指针。
-
2. ArrayList 源码分析
这一节，我们来分析 ArrayList 中主要流程的源码。
2.1 ArrayList 的属性
ArrayList 的属性很好理解，底层是一个 Object 数组，我要举手提问：