系列文章请查看 「数据结构&算法」必知必会系列：1. 开篇#计划路线
承接上篇请查看 「数据结构&算法」必知必会系列：5. 数组
链表
链表（Linked List）是一种常见的基础数据结构，是一种线性表，但是并不会按线性的顺序存储数据，而是在每一个结点里存到下一个结点的指针（Pointer）。
相对数组，链表的掌握会难一些，而且对应的形式也会比较多样。但无论形式是什么，核心正如其英译 LInked List，即将 数据与数据链接 起来的一种线性表数据结构。
可能初学者还是糊，继续看完，相信对「数据与数据链接」这一概念会有更为有具象的理解。
链表结构五花八门，本文介绍三种最常见的链表结构：单向链表、双向链表和循环链表。
单向链表
先来实现一个最简单最常用的链表，参考 LeetCode
个人实现用 Golang 代码如下：
package main
import (
"fmt"
)
// 结点数据
type LinkedListObject interface{}
// 结点构造
type SingleLinkNode struct {
Data LinkedListObject
NextNode *SingleLinkNode // 下一结点的指针，Golang 中用*取得指针变量指向的内存地址的值
}
func main() {
// 新的结点0
node := new(SingleLinkNode)
node.Data = 23
// 新的结点1
node1 := new(SingleLinkNode)
node1.Data = 6
node.NextNode = node1 // node1 链接到 node 结点上
// 新的结点2
node2 := new(SingleLinkNode)
node2.Data = 15
node1.NextNode = node2 // node2 链接到 node1 结点上
// 循环打印
nowNode := node
for {
if nowNode == nil {
break
}
fmt.Println(nowNode)
nowNode = nowNode.NextNode
}
}
在绝大多数情况下，我们将使用头结点(第一个结点)来表示整个列表。
代码看不懂没关系，重点在于理解结点构造，查看上述代码打印信息可加深理解。
接下来，通过对比数组，我们来看看单向链表在底层的存储结构上有什么不同。
数组需要一块连续的内存；而链表，并不需要连续的内存，它通过“指针”将一组零散的内存块串联起来使用。
使用链表结构可以克服数组需要预先知道数据大小的缺点，链表结构可以充分利用计算机内存空间，实现灵活的内存动态管理。
单向链表图中，你应该可以发现，其中有两个结点是比较特殊的，它们分别是第一个结点和最后一个结点。
习惯会把第一个结点叫作头结点，把最后一个结点叫作尾结点。
其中，头结点用来记录链表的基地址。有了它，我们就可以遍历得到整条链表。而尾结点特殊的地方是：指针不是指向下一个结点，而是指向一个空地址 NULL，表示这是链表上最后一个结点。
接下来，我们来分析下，在链表中进行查询、插入/删除操作的重要指标项「大O复杂度」。
**随机访问 **第 k 个元素，由于非连续内存，单向链表就只能轮询查找，即 O(n)
插入或删除 ？既然不关心内存连续性，随意分配内存或者删除都只要更改指针指向处理即可，量级上考虑，大O复杂度 =》O(1)。
基础的复杂度分析方法可查看系列文章 3. 时间 & 空间复杂度（下）
下文的复杂度分析也都略过，较为简单就不展开了
循环链表
直接上图，可看出和单向链表唯一的区别就在尾结点，尾结点指针是指向链表的头结点。
别小看这一差别，如果需要处理的数据具有 环形结构 特点，就很适合这个循环链表了。
双向链表
双向链表相对复杂一点，链表结点增加了一个指针和结点，还是看图 比较容易理解。
双向链表，顾名思义，它支持两个方向，每个结点不止有一个后继指针 next 指向后面的结点，还有一个前驱指针 prev 指向前面的结点。
双向链表需要额外的两个空间来存储后继结点和前驱结点的地址。所以，如果存储同样多的数据，双向链表要比单向链表占用更多的内存空间。虽然两个指针比较浪费存储空间，但可以支持双向遍历。
那相比单向链表，双向链表适合解决哪种问题呢？
之前 O(1) 的插入和删除，前提是知道结点位置为第 k 个，但是实际情况下我们往往不知道位置，而会有以下两种场景（其实重点在于 ”查找”）：
- 删除结点中“值等于某个给定值”的结点
- 删除给定指针指向的结点
第一种，无论单、双向，都还是需要遍历查找，复杂度即 O(n)
重点来看第二种，假设 b 结点的指针已知，单向链表并不知道前置结点 a 的位置（假设 a 非头结点），查找仍需要 O(n) 的时间复杂度。双向链表记录了前置指针，就简化为 O(1) 啦 (～￣▽￣)～
插入其实也是一样，如果场景是已知 c 结点，但是想要再其前面插入，单向链表就仍需遍历了。
除了以上优势，有序链表的查询，双向链表可比较大小来决定向前/向后查找，平均只需查找一半数据。
这边体现了一个 「空间换时间」的设计思想，虽然损耗了内存空间，但是代码执行速度提升了。
「空间换时间」的设计思想的典型应用还有缓存技术等等。
那如果双向+循环呢？我们把双向链表的头尾相连，就变成了双向循环链表，简单图示如下：
好了，看了那么多链表，是否对 ” 数据与数据链接 起来” 这一概念理解透了呢？
LRU 缓存淘汰算法
可能会奇怪，怎么突然提到「LRU」这个高频面试题了？
🙌 这是一个经典的链表应用场景，且有较广泛的应用。（初学者也别直接略过，可尝试着思考理解下，真不难）
LRU 是一种常见的缓存策略，通常一起提及还有两种：先进先出策略 FIFO（First In，First Out）、最少使用策略 LFU（Least Frequently Used）。
字面理解应该不难，LRU （Least Recently Used）—— 最近最少使用。
举个具体的场景 🌰，现有用户表的缓存，把缓存上限设置成 4（小一点便于理解）
- 业务方依次访问 1、2、3、4 这几个用户，你会如何设计链表？
- 现在业务方访问了 User 5，该删除哪个？User5 又该放哪？
- 此时业务方访问了 User 4，又如何处理？
先试着自己考虑并且画下吧 ~ (*´▽｀)ノノ
看下图，应该不难理解吧？我们用单链表 实现了 LRU 缓存
有人可能会想这怎么和我之前记的LRU 不大一样？（如面试准备死记硬背的 😝）
别着急，我们再来分析下 ↑ 的复杂度：插入删除O(1) 可忽略，主要在查找上 =》O(n)
继续优化，可引入散列表（Hash table）来记录每个数据的位置，这样就可将缓存访问的时间复杂度降到 O(1)。
解决了访问第一问题，我们再来想下删除（如上例 User4），位置知道了，前置指针怎么解决？
🙌 双向链表 ✅
系列之后会具体介绍「散列表」以及 「哈希算法」，之后再回过头继续优化分析 LRU缓存淘汰算法
先上张图吧
总结
Q：链表相比数组，有什么优缺点？
🙌 和数组相比，链表更适合插入、删除操作频繁的场景，查询的时间复杂度较高。
但在实际的软件开发中，并不能局限于时间复杂度分析。
数组简单易用，在实现上使用的是连续的内存空间，可以借助 CPU 缓存机制，预读数组中的数据，所以访问效率更高。而链表在内存中并不是连续存储，所以对 CPU 缓存不友好，没办法有效预读。
数组的缺点是大小固定，一经声明就要占用整块连续内存空间。如果声明的数组过大，可能会导致内存不足。如果声明的数组过小，则可能出现不够用的情况。这时只能再申请一个更大的内存空间，把原数组拷贝进去，非常费时。链表本身没有大小的限制，天然地支持动态扩容。
除此之外，如果你的代码对内存的使用非常苛刻，那数组就更适合你。因为链表中的每个结点都需要消耗额外的存储空间去存储一份指向下一个结点的指针，所以内存消耗会翻倍。而且，对链表进行频繁的插入、删除操作，还会导致频繁的内存申请和释放，容易造成内存碎片，如果是 Java 语言，就有可能会导致频繁的 GC（Garbage Collection，垃圾回收）。
Q：常用的链表你能举几个例子么？
🙌 单向链表、循环链表、双向链表（双向循环链表）
Q：如何基于链表实现 LRU 缓存淘汰算法？
🙌 我的思路是这样的：维护一个有序单链表，越靠近链表尾部的结点是越早之前访问的。当有一个新的数据被访问时，我们从链表头开始顺序遍历链表。
面试回答直接是 『哈希双向链表』 哈~（Hashmap + Double Linked List）
本系列 链表（下篇）将具体来 ”实战” —— 链表代码实现，预告如下（参考 LeetCode）：
