链表数据结构
数组需要一块连续的内存空间来存储，对内存的要求比较高。如果申请一个 100MB 大小的数组，当内存中没有连续的、足够大的存储空间时，即便内存的剩余总可用空间大于 100MB，仍然会申请失败。
（在大多数语言中）数组的大小是固定的，从数组的起点或中间插入或移除项的成本很高，因为需要移动元素。（尽管JavaScript有来自Array类的方法可以帮我们做这些事，但背后的情况同样如此。）
链表存储有序的元素集合，但不同于数组，链表中的元素在内存中并不是连续放置的，它并不需要一块连续的内存空间，通过“指针”将一组零散的内存块串联起来使用，所以如果申请的是 100MB 大小的链表，根本不会有问题。
链表 VS 数组
数组和链表是两种截然不同的内存组织方式，正是因为内存存储的区别，它们插入、删除、随机访问操作的时间复杂度正好相反。
不过，数组和链表的对比，并不能局限于时间复杂度。而且，在实际的软件开发中，不能仅仅利用复杂度分析就决定使用哪个数据结构来存储数据。
- 数组简单易用，使用的是连续的内存空间，可以借助 CPU 的缓存机制，预读数组中的数据，可以直接访问任何位置的任何元素，访问效率更高（链表在内存中并不是连续存储，所以对 CPU 缓存不友好，没办法有效预读，需要从起点开始迭代链表直到找到所需的元素）。链表好在添加或移除元素的时候不需要移动其他元素。所以数组更适合查询，链表更适合插入、删除操作频繁的场景
- 对大部分语言来说，数组的缺点是大小固定，一经声明就要占用整块连续内存空间。如果声明的数组过大，系统可能没有足够的连续内存空间分配给它，导致“内存不足（out of memory）”。如果声明的数组过小，则可能出现不够用的情况。这时只能再申请一个更大的内存空间，把原数组拷贝进去，数据拷贝非常费时。链表本身没有大小的限制，天然地支持动态扩容，这也是它与数组最大的区别。（ArrayList 容器也支持动态扩容，但如果数组中没有空闲空间也会申请空间——-> 数据拷贝）
用空间换时间思想
当内存空间充足的时候，如果更加追求代码的执行速度，就可以选择空间复杂度相对较高、但时间复杂度相对很低的算法或者数据结构。相反，如果内存比较紧缺，比如代码跑在手机或者单片机上，这个时候，就要反过来用时间换空间的设计思路。
缓存实际上就是利用了空间换时间的设计思想。如果我们把数据存储在硬盘上，会比较节省内存，但每次查找数据都要询问一次硬盘，会比较慢。但如果我们通过缓存技术，事先将数据加载在内存中，虽然会比较耗费内存空间，但是每次数据查询的速度就大大提高了。
总结一下，对于执行较慢的程序，可以通过消耗更多的内存（空间换时间）来进行优化；而消耗过多内存的程序，可以通过消耗更多的时间（时间换空间）来降低内存的消耗。链表分类
单链表
链表通过指针将一组零散的内存块串联在一起。其中，将内存块称为链表的“结点”。为了将所有的结点串起来，每个链表的结点除了存储数据之外，还需要记录链上的下一个结点的地址。如图所示，我们把这个记录下个结点地址的指针叫作后继指针 next。
其中有两个结点是比较特殊的，它们分别是头结点和尾结点。其中，头结点用来记录链表的基地址。有了它，就可以遍历得到整条链表。而尾结点特殊的地方是：指针不是指向下一个结点，而是指向一个空地址 NULL，表示这是链表上最后一个结点。
```javascript
// 定义一个单向链表的结点类
class Node {
constructor(data) {
this.data = data // 结点的数据
this.next = null // 结点的指针
}
}
// 单向链表类 class SingleLinked { constructor() { this.size = 0 // 存储链表中的元素(结点)数量 this.head = new Node(‘head’) // 链表的头结点：记录链表的起始地址 this.current = ‘’ // 用来记录当前结点 } // 采用尾插法给链表插入元素 push(element) { let current = this.findList() //找到链表的最后一个节点 let newNode = new Node(element) //创建一个新的节点 current.next = newNode newNode.next = null
this.size++
} // 获取链表的长度 getLength() { return this.size }
// 判断链表是否为空 isEmpty() { return this.size === 0 }
// 遍历链表：不重复访问链表的每个节点 displayList() { let list = ‘’ let current = this.head //指向链表的头指针 while (current) { //若当前节点不为空 list += current.data current = current.next //让指针指向下一节点 if (current) { list += ‘->’ } } console.log(list) }
// 获取链表的最后一个节点 findList() { let current = this.head while (current.next) { current = current.next } return current } }
/**
单向循环链表 / class CircularLinkTable { constructor() { this.head = null this.length = 0 } /*
- 往链表中添加数据
- @param {*} data
- @returns
*/
add(data) {
const n = new Node(data)
if (this.head === null) {
this.head = n
n.next = this.head
this.length++
return true
}
// 找到尾节点
let pre = this.head
while (pre.next !== this.head) {
pre = pre.next
}
if (pre.next === this.head) {
n.next = this.head
pre.next = n
this.length++
return true
} else {
console.error(
add error, did not find tail node!!!) return false } }
/**
- 反转链表
- @returns */ reverse() { if (this.length <= 1) { return } let pre = this.head let current = pre.next // while循环 遍历整个链表，反转next指向到父节点，并找到尾节点 while (current.next !== this.head) { const next = current.next current.next = pre // 反转next指向 // 准备进入下一次搜索，搜索下一个节点 pre = current current = next } // 此时的current就是尾节点 current.next = pre // 修正头节点的指向，修正头节点next的指向 this.head.next = current this.head = current } }
// 测试 function test() { const lt = new CircularLinkTable() lt.add(“a”) lt.add(“b”) lt.add(“c”) lt.reverse() console.log(lt) } test()
<a name="CVi4M"></a>
## 循环链表
**循环链表是一种特殊的单链表**。跟单链表唯一的区别就在尾结点。单链表的尾结点指针指向空地址，表示这就是最后的结点了。而循环链表的尾结点指针是指向链表的头结点。<br />**循环链表**的优点是从链尾到链头比较方便。当要处理的数据具有环型结构特点时，就特别适合采用循环链表。比如著名的[约瑟夫问题](https://zh.wikipedia.org/wiki/%E7%BA%A6%E7%91%9F%E5%A4%AB%E6%96%AF%E9%97%AE%E9%A2%98)。尽管用单链表也可以实现，但是用循环链表实现的话，代码就会简洁很多。
<a name="HQbOL"></a>
## 双向链表
双向链表，它支持两个方向，每个结点不止有一个后继指针 next 指向后面的结点，还有一个前驱指针 prev 指向前面的结点。<br /><br />双向链表需要额外的两个空间来存储后继结点和前驱结点的地址。所以，如果存储同样多的数据，双向链表要比单链表占用更多的内存空间。虽然两个指针比较浪费存储空间，但可以支持双向遍历，这样也带来了双向链表操作的灵活性。<br />双向链表与单向链表对比：
- **删除结点中“值等于某个给定值”的结点**：单链和双链复杂度是一样的，尽管单纯的删除操作时间复杂度是 O(1)，但遍历查找的时间是主要的耗时点，对应的时间复杂度为 O(n)，根据加法法则总时间复杂度为 O(n)。
- **删除给定指针指向的结点**：找到了要删除的结点，还要知道该结点的前驱结点，单链表不支持直接获取前驱结点，要从头结点开始遍历链表， 需要O(n) 的时间复杂度。双向链表只需要 O(1) 的时间复杂度！
- **在链表的某个指定结点前面插入一个结点**：单向链表需要 O(n) 的时间复杂度，双向链表O(1) ！
- **对于一个有序链表的查询**：双向链表的按值查询的效率也要比单链表高一些。因为以记录上次查找的位置 p，每次查询时，根据要查找的值与 p 的大小关系，决定是往前还是往后查找，所以平均只需要查找一半的数据。
以上就是为什么在实际的软件开发中，双向链表尽管比较费内存，但还是比单链表的应用更加广泛的原因。 Java的`LinkedHashMap`这个容器就用到了双向链表这种数据结构。
<a name="PoeC2"></a>
## 双向循环链表
循环链表和双向链表的整合：<br />
<a name="nUOzY"></a>
# LRU 缓存淘汰算法
缓存是一种提高数据读取性能的技术。缓存的大小有限，当缓存被用满时，哪些数据应该被清理出去，哪些数据应该被保留？这就需要缓存淘汰策略来决定。<br />常见的策略有三种：先进先出策略 FIFO（First In，First Out）、最少使用策略 LFU（Least Frequently Used）、最近最少使用策略 LRU（Least Recently Used）。<br />**LRU实现思路**：维护一个有序单链表，越靠近链表尾部的结点是越早之前访问的。当有一个新的数据被访问时，从链表头开始顺序遍历链表。
1. 如果此数据之前已经被缓存在链表中了，我们遍历得到这个数据对应的结点，并将其从原来的位置删除，然后再插入到链表的头部。
1. 如果此数据没有在缓存链表中，又可以分为两种情况：
- 如果此时缓存未满，则将此结点直接插入到链表的头部；
- 如果此时缓存已满，则链表尾结点删除，将新的数据结点插入链表的头部。
基于这种链表的实现思路，缓存访问的时间复杂度为 O(n)。实际可以继续优化这个实现思路，比如引入**散列表**（Hash table）来记录每个数据的位置，将缓存访问的时间复杂度降到 O(1)。
<a name="c8OpC"></a>
# 写好链表代码
<a name="aG2hN"></a>
## 技巧一：理解指针或引用的含义
有些语言有“指针”的概念，比如 C 语言；有些语言没有指针，取而代之的是“引用”，比如 Java、JavaScript、Python。不管是“指针”还是“引用”，实际上，它们的意思都是一样的，都是存储所指对象的内存地址。<br />在编写链表代码的时候：`p->next=q`，p 结点中的 next 指针存储了 q 结点的内存地址。更复杂的：`p->next=p->next->next`，p 结点的 next 指针存储了 p 结点的下下一个结点的内存地址。
<a name="WjHk0"></a>
## 技巧二：警惕指针丢失和内存泄漏
```c
p->next = x; // 将 p 的 next 指针指向 x 结点；ok
x->next = p->next; // 将 x 的结点的 next 指针指向 b 结点；error：此时的p->next已经指向x节点而不是b节点。所以只需要调换上下顺序即可
对C 语言来说，内存管理是由程序员负责的，如果没有手动释放结点对应的内存空间，就会产生内存泄露。所以插入结点时，一定要注意操作的顺序，要先将结点 x 的 next 指针指向结点 b，再把结点 a 的 next 指针指向结点 x，这样才不会丢失指针，导致内存泄漏。同理，删除链表结点时，也一定要记得手动释放内存空间，对于像 Java 这种虚拟机自动管理内存的编程语言来说，就不用考虑这么多。
技巧三：利用哨兵简化实现难度
if (head->next == null) { // 删除最后一个，head表示头节点
head = null;
} else { // 删除结点 p 的后继结点
p->next = p->next->next;
}
if (head == null) { // 插入第一个节点
head = new_node;
} else{ // 在结点 p 后面插入一个新节点
new_node->next = p->next;
p->next = new_node;
}
上面针对链表的插入、删除操作，需要对插入第一个结点和删除最后一个结点的情况进行特殊处理，实现起来就会很繁琐不简洁，而且也容易因为考虑不全而出错。
哨兵节点就是用来解决边界问题，引入哨兵结点，不管链表是不是空，head 指针都会一直指向这个哨兵结点。这种有哨兵结点的链表叫带头链表。相反，没有哨兵结点的链表就叫作不带头链表。
哨兵结点是不存储数据的，这种利用哨兵简化编程难度的技巧，在很多代码实现中都有用到，比如插入排序、归并排序、动态规划等
// 在数组 a 中，查找 key，返回 key 所在的位置
// 其中，n 表示数组 a 的长度
int find(char* a, int n, char key) {
// 边界条件处理，如果 a 为空，或者 n<=0，说明数组中没有数据，就不用 while 循环比较了
if(a == null || n <= 0) {
return -1;
}
int i = 0;
// 这里有两个比较操作：i<n 和 a[i]==key.
while (i < n) {
if (a[i] == key) {
return i;
}
++i;
}
return -1;
}
// 在数组 a 中，查找 key，返回 key 所在的位置
// 其中，n 表示数组 a 的长度
// a = {4, 2, 3, 5, 9, 6} n=6 key = 7
int find(char* a, int n, char key) {
if(a == null || n <= 0) {
return -1;
}
// 因为下面要将 a[n-1] 的值替换成 key，所以要提前特殊处理这个值
if (a[n-1] == key) {
return n-1;
}
// 把 a[n-1] 的值临时保存在变量 tmp 中，以便之后恢复。tmp=6
// 之所以这样做的目的是：希望 find() 代码不要改变 a 数组中的内容
char tmp = a[n-1];
// ⭐哨兵节点！把 key 的值放到 a[n-1] 中，此时 a = {4, 2, 3, 5, 9, 7}
a[n-1] = key;
int i = 0;
// while 循环，比起不引入哨兵节点，少了 i<n 这个比较操作
while (a[i] != key) {
++i;
}
// 恢复 a[n-1] 原来的值, 此时 a= {4, 2, 3, 5, 9, 6}
a[n-1] = tmp;
if (i == n-1) {
// 如果 i == n-1 说明原先整个表里就没有 key，所以返回 -1
return -1;
} else {
// 否则，返回 i
return i;
}
}
上面两段代码只是为了举例说明哨兵的作用，写代码的时候千万不要写第二段那样的代码，因为可读性太差了。大部分情况下并不需要如此追求极致的性能。
技巧四：重点留意边界条件处理
- 如果链表为空时，代码是否能正常工作？
- 如果链表只包含一个结点时，代码是否能正常工作？
- 如果链表只包含两个结点时，代码是否能正常工作？
-
技巧五：举例画图，辅助思考
五种常见链表操作
单链表反转
- 链表中环的检测
- 两个有序的链表合并
- 删除链表倒数第 n 个结点
求链表的中间结点 ```javascript // 单向链表的结点类 class Node { constructor(data) { this.data = data // 结点的数据 this.next = null // 结点的指针 } } // 单向链表类 class SingleLinked { constructor() { this.size = 0 // 用来记录链表中的结点个数 this.head = new Node(‘head’) // 链表的头指针：记录链表的起始地址 this.current = ‘’ // 用来记录当前结点 }
// 获取链表的长度 getLength() { return this.size }
// 判断链表是否为空 isEmpty() { return this.size === 0 }
// 遍历链表：不重复访问链表的每个节点 displayList() { let list = ‘’ let current = this.head //指向链表的头指针 while (current) { //若当前节点不为空
list += current.data current = current.next //让指针指向下一节点 if (current) { list += '->' }} console.log(list) }
// 获取链表的最后一个节点 findList() { let current = this.head while (current.next) {
current = current.next} return current }
// 采用尾插法给链表插入元素 appendNode(element) { let current = this.findList() //找到链表的最后一个节点 let newNode = new Node(element) //创建一个新的节点 current.next = newNode newNode.next = null
this.size++ } }
/**
单向循环链表 / class CircularLinkTable { constructor() { this.head = null this.length = 0 } /*
- 往链表中添加数据
- @param {*} data
- @returns
*/
add(data) {
const n = new Node(data)
if (this.head === null) {
this.head = n
n.next = this.head
this.length++
return true
}
// 找到尾节点
let pre = this.head
while (pre.next !== this.head) {
pre = pre.next
}
if (pre.next === this.head) {
n.next = this.head
pre.next = n
this.length++
return true
} else {
console.error(
add error, did not find tail node!!!) return false } }
/**
- 反转链表
- @returns */ reverse() { if (this.length <= 1) { return } let pre = this.head let current = pre.next // while循环 遍历整个链表，反转next指向到父节点，并找到尾节点 while (current.next !== this.head) { const next = current.next current.next = pre // 反转next指向 // 准备进入下一次搜索，搜索下一个节点 pre = current current = next } // 此时的current就是尾节点 current.next = pre // 修正头节点的指向，修正头节点next的指向 this.head.next = current this.head = current } }
// 测试 function test() { const lt = new CircularLinkTable() lt.add(“a”) lt.add(“b”) lt.add(“c”) lt.reverse() console.log(lt) } test() ```
若有收获，就点个赞吧
0 人点赞
