数据结构 - 链表 Linked list - 《数据结构与算法》

举个例子
对数据的操作
分类
操作链表的注意事项

通过指针将一组零散的内存块串联在一起，链表一般的使用场景为缓存的处理，如缓存写满之后如何清理：

先进先出（FIFO）
最少使用策略（LFU）
最少最近使用策略（LRU）

链表的基本存储单元为结点，结点可以简单划分为数据单元和指向单元。指向单元数据结构的差异，衍生出不同的链表结构。
链表 Linked list - 图1

举个例子

例如：一个歌单，上一首歌指向下一首歌，而歌单的第一首歌被叫做头结点，最后一首歌被叫做尾结点。

对数据的操作

优点

与数组相比，对链表数据的插入和删除操作不存在数据的搬移，其时间复杂度为链表 Linked list - 图3 。

缺点

由于链表中数据的存储空间是内存不连续的，因此其随机访问性能比数组差，时间复杂度为链表 Linked list - 图4 。

分类

在此主要讨论的链表结构为：单链表、双链表、循环链表

1. 单链表 Singly linked list

如上举例的歌单，我们可以从将不同风格的歌曲组建成一个自定义的歌单，用播放器打开这个歌单，我们便可以顺序播放每首歌直到所有歌曲被播放完。

// Node 结点
type Node struct {
    data string            // 用于存储数据
    next *Node            // 指向下一个结点，后继指针
}
// List 单链表
type SinglyList struct {
    head *Node
}
// Append 向链表添加新结点
func (l *SinglyList) Append(newNode *Node) {
    // 链表为空，新添加的结点为该链表的头结点
    if l.head == nil {
        l.head = newNode
        return
    }
    currentNode := l.head
    // 遍历链表，在尾结点后添加新结点
    for currentNode.next != nil {
        currentNode = currentNode.next
    }
    currentNode.next = newNode
}

2. 循环链表 Circular linked list

上述歌单中的所有歌曲全都播放完了，但是很喜欢这个歌单中的所有歌曲，怎么办，于是给播放器添加一个循环播放的功能：最后一首歌曲播放完毕后再继续从头按序播放所有歌曲——首尾相连，组成循环链表。
单链表尾结点的后继指针为空，而循环链表尾结点的后继指针为头结点：即循环链表不存在头、尾结点。

使用单向循环列表解决约瑟夫环问题：

3. 双向链表 Doubly linked list

顾名思义，在单向链表的基础上，添加一个前向指针，用于指明结点所对应的上一个结点信息。
例如上面的歌单，听完某一首歌之后还想再听一遍，则可以使用“上一曲”的功能。

// Node 结点
type Node struct {
    data string            // 用于存储数据
    next *Node            // 指向下一个结点，后继指针
    prev *Node             // 指向前驱结点
}

与单链表相比，双向链表的删除操作更为高效，时间复杂度为O(1)，但是双向链表比单链表更费内存（加入了指向前驱结点的指针）。

操作链表的注意事项

1. 利用哨兵简化实现难度

2. 注意边界条件

如果链表为空时，代码是否能正常工作？
如果链表只包含一个结点时，代码是否能正常工作？
如果链表只包含两个结点时，代码是否能正常工作？
代码逻辑在处理头结点和尾结点的时候，是否能正常工作？

3. 常见的操作
单链表反转
链表中环的检测

环形链表
 环形链表II

两个有序的链表合并
删除链表倒数第 n 个结点
求链表的中间结点

回文链表

链表 Linked list