一、OverView
快速预览：
- 首先要和上一节的数组进行横向对比，来看一下链表独有的特性
- 第二小节会介绍一下常见的几种链表，以及为什么要衍生出这些链表
- 第三小节主要关注于链表的基操，
(勿6)以及在链表中的一些注意事项，如何保持链表不断链，为什么要引入哨兵 - 最后一个小节主要结合 Java 中的链表 LinkedList 来加深对链表的理解
二、特性
在上一节中已经介绍过数组了，可以将数组和链表在结构上进行对比：
- 在数组中，是需要一块
连续且足够存储所有数据的内存空间。如果你的数据大小是 1MB，但是你的内存空间中可能只有两个大内存块，且大小分别为 512 KB，还有若干小内存块，那么这块数据是不能存储在内存中的 - 在链表中，是通过 next 指针将
离散的内存空间全部利用起来，例如上面的情况中，就可以将这 1MB 大小的数据全部装入内存中
注：在实际的应用层开发中，是不用在乎那一点的空间换时间；但是在底层开发中，这种对空间要求非常高的开发中，就要考虑到多方面了
对比：
| 时间复杂度 | 数组 | 链表 |
|---|---|---|
| 查询 | O(1) | O(n) |
| 插入、删除 | O(n) | O(1) |
三、几种常规链表
3.1 单链表
- 指向 w 的结点的结点称为
头结点 - 指向 NULL 的结点 g 称为
尾结点 - 每一个结点需要额外的空间存储下一个结点的地址
3.2 循环链表
- 不仅具有单链表的特点，且加上它的尾结点指向的不是 NULL，而是指向了头结点
- 相比单链表的优点：可以通过尾结点找到头结点
3.3 双向链表
- 每一个结点除了需要额外的空间存储下一个结点的地址，还需要额外的空间指向前一个结点的地址
- 相比单链表的优点：可以通过任一结点可以找到上一个结点和下一个结点
3.4 双向循环链表
- 不仅具有双向链表的特点，且加上头结点的 pre 指针指向尾结点，尾结点的 next 指针指向头结点
- 相比双向链表的优点：可以通过头结点找到尾结点，也可以通过尾结点找到头结点
四、链表的基操和注意事项
这里对于链表的操作只在单链表中进行，其余的链表同理：
增
前提：在 a 结点后面增加一个 x 结点，p 指向 a 结点
- 第一步：x –> next = p –> next
- 第二步：p –> next = x
注：
此时就要注意 “链不断” 理论：在上面的例子中就是，第一步和第二步的顺序不能颠倒，不然就会出现下面这种情况：
- 第一步：p –> next = x
- 第二步：x –> next = p –> next
如果 p –> next 指向了 x，那么在第二步中，x –> next 指向了自己
删
删除操作的话，就只需要：p –> next = p –> next –> next 即可
注：删除结点要记得释放内存，除了一些自带垃圾回收的语言外，例如 Java、python、Go等
哨兵模式
既然在链表中出现了这个模式，那必然是有运用的场景的，看个例子：
在上面单链表中增加一个结点时
1 | x --> next = p --> next |
如果出现下面几种情况：
- 空链表，插入第一个结点
- 删除最后一个结点
- 又或是 p 指针指向的是两个结点的前一个结点 (在上面的例子中是 a)，但是如果出现要插入的是头结点前面 (也就是说没有前面那个结点了) 呢？
此时就可以发现，p 指针无处可指，这时候就可以引入”哨兵”了。(虽然在双向链表中可以轻易解决这个问题)
也就是说不管在什么情况下，都有一个哨兵的存在，其主要目的就是简化代码，不需要考虑带很多情况，可以看一下下面的例子：
首先需要的前提就是：head 指针是永远指向哨兵的
- 空链表中插入第一个结点，就可以：
1 | if (head -> next == null) { |
只需要判断哨兵指针的 next 是否为空，如果为空的的话，只需要将 p = head，就可以进行和上面一样的插入代码了
四、Java中的链表
首先来回忆一下在 Java 中对数组的操作，直接分配一块连续的内存给数组，这种情况的不好之处就是需要连续且内存足够的空间；随后又提出了 Java 中动态数组 ArrayList ，这个类的确可以进行动态的自动扩容，但是它不能进行自动缩容 (注：ArrayList 是支持手动扩容、缩容)，而且它的扩容是将原来所有的数据复制一份到已经进行扩容到原来 1.5 倍的新数组中，当数据量过大时，这种操作可能就需要大量时间来进行了
而在这一小节中，可以看一下，在 Java 中链表类：LinkedList，它的底层是基于双向链表的，日常开发很少使用
首先看一下，继承关系：
可以和上一节 ArrayList 类的继承图进行对比，可以发现：
- 少了：LinkedList 少实现了 RandomAccess 接口，具体看参考RandomAccess 这个空架子有何用？
- 改了：ArrayList 是继承了 AbstractList，而 LinkedList 继承了 AbstractSequentialList (它是 AbstractList 的子类)
- 多了：LinkedList 还实现了 Deque 接口 ====> 因为实现 Deque 即可以作为队列使用，也可以作为栈使用。当然，作为双端队列，也是可以的。
由于源码过多，此内容将放在 JDK 源码分析系列中。