链表
链表(linked list)是一种线性数据结构，其中的每一个元素都是一个节点对象，各个节点通过“引用”相链接.引用记录了下一个节点的内存地址，通过它可以从当前节点访问到下一个节点。
链表的设计使得链表的各个节点可以分散存储在内存各处，他们的内存地址无需连续，这一点不同于数组。
链表定义
链表的组成单位是节点对象，每个节点包含两项：
- 节点的值
- 指向下一个节点的指针
其中，链表的首个节点称为头节点，最后一个节点被称为尾节点。
type ListNode struct {
Val int // 节点值
Next *ListNode // 指向下一个节点的指针
}
链表常用操作
1. 初始化链表
建立链表分两步，第一步是初始化各个节点对象，第二步是构建节点之间的引用关系。初始化完成后，我们就可以从链表的头节点开始，通过引用使next指向下一个节点。
/* 初始化链表 1 -> 3 -> 2 -> 5 -> 4 */
// 初始化各个节点
n0 := NewListNode(1)
n1 := NewListNode(3)
n2 := NewListNode(2)
n3 := NewListNode(5)
n4 := NewListNode(4)
// 构建节点之间的引用
n0.Next = n1
n1.Next = n2
n2.Next = n3
n3.Next = n4
2. 插入节点
在链表中插入节点非常容易，假设我们想在链表两个相邻节点n0和n1之间插入一个新节点P，则只需改变两个节点指针引用即可，时间复杂度为O(1)
func insert(n *ListNode, p *ListNode) {
// 让新节点指向原来的下一个节点n1
p.Next = n.Next
// 让原来的下一个节点指向p
n.Next = p
}
3. 删除节点
删除节点也非常容易，只需改变上一个节点的引用即可：
// 删除n之后的首个节点
func delete(n0 *ListNode) {
if n0.Next == nil {
return
}
// 链表中删除P节点
p := n0.Next
n1 := p.Next
n0.Next = n1 = n0.Next.Next
}
4. 访问节点
在链表中访问节点效率较低，程序需从头节点开始，顺序向后遍历，直至找到目标节点。时间复杂度为O(n)
func access(n *ListNode, index int) *ListNode {
if n == nil {
return nil
}
head := n
for i := 0; i < index; i ++ {
head = head.Next
}
return head
}
5. 查找节点
遍历链表，查找其中值为target的节点，输出该节点在链表中的索引。
func findNode(n *ListNode, target int) int {
var index int
head := n
for head != nil {
if head.Val = target {
return index
}
head = head.Next
index ++
}
return -1
}
数组vs.链表
| 数组 | 链表 | |
|---|---|---|
| 存储方式 | 连续内存空间 | 分散内存空间 |
| 容量扩展 | 长度不可变 | 可灵活扩展 |
| 内存效率 | 元素占用内存少，但可能浪费空间 | 元素占用内存多 |
| 访问元素 | O(1) | O(n) |
| 添加元素 | O(n) | O(1) |
| 删除元素 | O(n) | O(1) |
常见链表类型
- 单向链表：即前面介绍的普通链表。单向链表的节点包含值和指向下一节点的引用两项数据。我们将首个节点称为头节点，将最后一个节点称为尾节点，尾节点指向空 None 。
- 环形链表：如果我们令单向链表的尾节点指向头节点（首尾相接），则得到一个环形链表。在环形链表中，任意节点都可以视作头节点。
- 双向链表：与单向链表相比，双向链表记录了两个方向的引用。双向链表的节点定义同时包含指向后继节点（下一个节点）和前驱节点（上一个节点）的引用（指针）。相较于单向链表，双向链表更具灵活性，可以朝两个方向遍历链表，但相应地也需要占用更多的内存空间。
链表典型应用
单向链表通常用于实现栈、队列、哈希表和图等数据结构。
- 栈与队列：当插入和删除操作都在链表的一端进行时，它表现的特性为先进后出，对应栈；当插入操作在链表的一端进行，删除操作在链表的另一端进行，它表现的特性为先进先出，对应队列。
- 哈希表：链式地址是解决哈希冲突的主流方案之一，在该方案中，所有冲突的元素都会被放到一个链表中。
- 图：邻接表是表示图的一种常用方式，其中图的每个顶点都与一个链表相关联，链表中的每个元素都代表与该顶点相连的其他顶点。
双向链表常用于需要快速查找前一个和后一个元素的场景。
- 高级数据结构：比如在红黑树、B 树中，我们需要访问节点的父节点，这可以通过在节点中保存一个指向父节点的引用来实现，类似于双向链表。
- 浏览器历史：在网页浏览器中，当用户点击前进或后退按钮时，浏览器需要知道用户访问过的前一个和后一个网页。双向链表的特性使得这种操作变得简单。
- LRU 算法：在缓存淘汰（LRU）算法中，我们需要快速找到最近最少使用的数据，以及支持快速添加和删除节点。这时候使用双向链表就非常合适。
环形链表常用于需要周期性操作的场景，比如操作系统的资源调度。
- 时间片轮转调度算法：在操作系统中，时间片轮转调度算法是一种常见的 CPU 调度算法，它需要对一组进程进行循环y。每个进程被赋予一个时间片，当时间片用完时，CPU 将切换到下一个进程。这种循环操作可以通过环形链表来实现。
- 数据缓冲区：在某些数据缓冲区的实现中，也可能会使用环形链表。比如在音频、视频播放器中，数据流可能会被分成多个缓冲块并放入一个环形链表，以便实现无缝播放。
