theme: channing-cyan
深入数据结构之「链表篇」
本文讲链表，这是算法的第二篇。
链表
上节讲了，数组是一种线性数据结构，用一段连续的存储空间，用来存储一类相同数据类型的元素。
链表相反，它并不需要一块连续的内存空间，它是通过“指针”将一组零散的内存块串联起来使用。
链表（英语：Linked list）是一种常见的基础数据结构，是一种线性表，但是并不会按线性的顺序存储数据，而是在每一个节点里存到下一个节点的指针。由于不必须按顺序存储，链表在插入的时候可以达到O(1)的复杂度，比另一种线性表顺序表“数组”快得多，但是查找一个节点或者访问特定编号的节点则需要O(n)的时间。
链表结构克服数组预先知道的数据大小的缺点，比如：现在内存空间还有10m，但是不是连续的，如果你使用数组数据结构，你要申请10m的空间是申请不到了。但如果是链表数据结构是可以的，因为它不需要连续的内存空间。
常见的链表有3种：
单链表
双向链表
循环链表
本文先讲“单链表”
单链表
单链表（又名单向链表、线性链表， 英语：singly linked list）是链表的一种，其特点是链表的链接方向是单向的，对链表的访问要通过从头部开始，依序往下读取。它包含两个域，一个信息域和一个指针域。这个链接指向列表中的下一个节点，而最后一个节点则指向一个空值。
我画的这个图中有两个节点比较特殊，第一个是头节点，第二个是尾节点。
头节点，类似于一个哨兵，记录了链表的基地址，它没有存数据，next 指向下一个节点地址，通过它可以遍历整个链表；
尾节点，指针指向了一个null地址，表示这个链表截止了。
只要提链表不得不和数组对比，数组：下标查找时间复杂度为O(1)，但，删除元素和增加元素，最坏时间复杂度是O(n)。接下来看看链表的插入和删除。
对于链表的插入和删除，我们只需要考虑几个关联的节点指针变动就可以了，并不需要把整个链表都遍历一次。
先看单链表插入，如下图：
如果要在a和b之间插入一个c，只需要把a的next指针指向c，c的next指针指向b，再把a和c之间的指向关系断开就可以了。
再看删除，假设要把a节点删除，只需要把头节点的next指针指向b，再把a的next置为null，即可。为啥要把a的指针置为null？当然是为了被垃圾回收器清理。
当然，链表有它的缺点，下标随机访问x个元素肯定就没有那么高效了。上节数组篇幅，我讲过数组的随机访问公式
address=基地址+i*type_size
因为链表的内存并不是连续的，所以失去了下标随机访问优势，无法通过寻址公式找到下一个节点的地址，只能每个节点挨着遍历了。
哨兵节点
在链表的头部和尾部其实就是哨兵节点，哨兵节点不存储数据只是辅助作用。它存在的价值。
1、 在对链表进行操作时，无需特殊处理链表为空或只有一个节点的情况。哨兵节点的存在确保了链表始终包含至少一个节点，简化了代码逻辑。
2、 可以将许多边界条件的处理逻辑合并到通用的代码路径中，使代码更加简洁和易于理解。
代码实战
先用GO展示一段单链表的代码。
package linklist
import (
"fmt"
"sync/atomic"
)
type Node[D any] struct {
val D
next *Node[D]
}
func (n *Node[D]) Val() D {
return n.val
}
func (n *Node[D]) Next() *Node[D] {
return n.next
}
type LinkList[D any] struct {
head *Node[D] // 哨兵节点
len atomic.Uint32 // 节点长度
}
// InsertAfter 某一个节点后插入
func (l *LinkList[D]) InsertAfter(n *Node[D], val D) {
if n == nil {
// 如果 n 为空，不处理
return
}
newNode := &Node[D]{
next: n.next,
val: val,
}
n.next = newNode
l.len.Add(1)
}
// InsertBefore 某一个节点前插入节点
func (l *LinkList[D]) InsertBefore(n *Node[D], val D) {
if n == nil {
return
}
var (
pre = l.head
cur = pre.next
)
for cur != nil {
if cur == n {
break
}
pre = cur
cur = cur.next
}
newNode := &Node[D]{
next: n.next,
val: val,
}
pre.next = newNode
newNode.next = cur
l.len.Add(1)
}
// Insert2Head 头节点后插入
func (l *LinkList[D]) Insert2Head(val D) {
cur := l.head
l.InsertAfter(cur, val)
}
// Insert2Tail 插入末尾节点
func (l *LinkList[D]) Insert2Tail(val D) {
cur := l.head
for cur.next != nil { // 遍历找到最后一个节点
cur = cur.next
}
l.InsertAfter(cur, val)
}
func (l *LinkList[D]) FindByIndex(index uint32) (*Node[D], bool) {
// index 输入节点不能大于总长度
if index > l.len.Load() {
return nil, false
}
if index == 0 {
return nil, false
}
var (
cur = l.head.next
i uint32
)
// 遍历是从0开始，所以i<index
for i = 1; i < index; i++ {
cur = cur.next
}
return cur, true
}
// DeleteNode 删除指定Node
func (l *LinkList[D]) DeleteNode(n *Node[D]) {
if n == nil {
return
}
var (
pre = l.head
cur = pre.next
)
for pre != nil {
if cur == n { // 首节点==n，推出。这里不能用pre节点哈，头节点只是一个哨兵。
break
}
pre = cur
cur = cur.next
}
pre.next = cur.next
n = nil
d := int32(-1)
l.len.Add(uint32(d))
}
// Print 链表打印
func (l *LinkList[D]) Print() {
var (
cur = l.head.next
out any
)
for cur != nil {
if out == nil {
out = cur.val
} else {
out = fmt.Sprintf("%v->%v", out, cur.val)
}
cur = cur.next
}
fmt.Println(out)
fmt.Printf("当前链表长度：%v", l.len.Load())
}
测试用例
func TestInsert(t *testing.T) {
list := LinkList[int]{
head: &Node[int]{},
}
list.Insert2Tail(1)
list.Insert2Tail(2)
list.Insert2Tail(3)
list.Print()
}
func TestInsertHead(t *testing.T) {
list := LinkList[int]{
head: &Node[int]{},
}
list.Insert2Tail(1)
list.Insert2Tail(2)
list.Insert2Head(3)
list.Insert2Head(4)
list.Insert2Head(5)
list.Insert2Head(6)
list.Print()
}
func TestInsertBefore(t *testing.T) {
list := LinkList[int]{
head: &Node[int]{},
}
list.Insert2Tail(1)
list.Insert2Tail(2)
list.Insert2Tail(3)
n1, ok := list.FindByIndex(2)
if ok {
list.InsertBefore(n1, 4)
}
n3, ok := list.FindByIndex(3)
if ok {
list.InsertBefore(n3, 5)
}
list.Print()
}
func TestDelete(t *testing.T) {
list := LinkList[int]{
head: &Node[int]{},
}
list.Insert2Tail(1)
list.Insert2Tail(2)
list.Insert2Tail(3)
list.Insert2Tail(4)
n4, ok := list.FindByIndex(4)
if ok {
list.DeleteNode(n4)
}
list.Print()
n1, ok := list.FindByIndex(1)
if ok {
list.DeleteNode(n1)
}
list.Print()
}
func TestFind(t *testing.T) {
list := LinkList[int]{
head: &Node[int]{},
}
for i := 1; i <= 10; i++ {
list.Insert2Tail(i)
}
list.Print()
n1, ok := list.FindByIndex(1)
if ok {
println(n1.val)
}
n2, ok := list.FindByIndex(7)
if ok {
println(n2.val)
}
n3, ok := list.FindByIndex(5)
if ok {
println(n3.val)
}
n0, ok := list.FindByIndex(0)
if ok {
println(n0.val)
} else {
fmt.Printf("%v号位不存在\n", 0)
}
n10, ok := list.FindByIndex(10)
if ok {
println(n10.val)
}
n11, ok := list.FindByIndex(11)
if ok {
println(n11.val)
} else {
fmt.Printf("%v号位不存在\n", 11)
}
}
大家可以对比测试代码和测试用例自己敲下代码。链表要写好还真不容易，我花了一下午来写它们主要边界问题需要考虑周全。
总结
1、 链表是一种常见的基础数据结构，是一种线性表，但是并不会按线性的顺序存储数据，而是在每一个节点里存到下一个节点的指针。
2、 链表查询只能遍历，并不能靠寻址法快速找到对应的节点信息。