本文已收录到 AndroidFamily，技术和职场问题，请关注公众号 [彭旭锐] 提问。
前言
大家好，我是小彭。
在上一篇文章里，我们聊到了基于动态数组 ArrayList 线性表，今天我们来讨论一个基于链表的线性表 —— LinkedList。
小彭的 Android 交流群 02 群已经建立啦，扫描文末二维码进入~
思维导图：
1. LinkedList 的特点
1.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 在节点上增加了前驱和后继指针。
1.2 LinkedList 的多面人生
在数据结构上，LinkedList 不仅实现了与 ArrayList 相同的 List 接口，还实现了 Deque 接口（继承于 Queue 接口）。
Deque 接口表示一个双端队列（Double Ended Queue），允许在队列的首尾两端操作，所以既能实现队列行为，也能实现栈行为。
Queue 接口：
| 拒绝策略 | 抛异常 | 返回特殊值 |
|---|---|---|
| 入队（队尾） | add(e) | offer(e) |
| 出队（队头） | remove() | poll() |
| 观察（队头） | element() | peek() |
Queue 的 API 可以分为 2 类，区别在于方法的拒绝策略上：
-
抛异常：
- 向空队列取数据，会抛出 NoSuchElementException 异常；
- 向容量满的队列加数据，会抛出 IllegalStateException 异常。
-
返回特殊值：
- 向空队列取数据，会返回 null；
- 向容量满的队列加数据，会返回 false。
Deque 接口：
Java 没有提供标准的栈接口（很好奇为什么不提供），而是放在 Deque 接口中：
| 拒绝策略 | 抛异常 | 等价于 |
|---|---|---|
| 入栈 | push(e) | addFirst(e) |
| 出栈 | pop() | removeFirst() |
| 观察（栈顶） | peek() | peekFirst() |
除了标准的队列和栈行为，Deque 接口还提供了 12 个在两端操作的方法：
| 拒绝策略 | 抛异常 | 返回值 |
|---|---|---|
| 增加 | addFirst(e)/ addLast(e) | offerFirst(e)/ offerLast(e) |
| 删除 | removeFirst()/ removeLast() | pollFirst()/ pollLast() |
| 观察 | getFirst()/ getLast() | peekFirst()/ peekLast() |
2. LinkedList 源码分析
这一节，我们来分析 LinkedList 中主要流程的源码。
2.1 LinkedList 的属性
- LinkedList 底层是一个 Node 双向链表，Node 节点中会持有数据 E 以及 prev 与next 两个指针；
- LinkedList 用
first和last指针指向链表的头尾指针。
LinkedList 的属性很好理解的，不出意外的话又有小朋友出来举手提问了：