Go语言数据结构详解：双链表

Go语言数据结构详解：双链表

双链表是数据结构中一种重要的线性结构，相比单链表，它提供了更多的便利性和灵活性。本文将详细介绍双链表的基本概念、实现方法以及一些常见的操作，帮助读者深入理解这一数据结构。

双链表

双链表（Doubly Linked List）是一种链式数据结构，其中每个节点包含三个部分：数据域、前驱指针和后继指针。具体来说，每个节点持有一个指向列表前一个元素的指针（Prev），以及指向下一个元素的指针（Next）。

双向链表的节点中包含 3 个字段：

• 数据域：存储实际的数据
• Next指针：指向双链表中的下一个节点
• Prev指针：指向双链表中的前一个节点

结构体定义如下：

type Node struct {
    Prev  *Node
    Value int
    Next  *Node
}

实际应用：音乐播放器的播放列表就是一个很好的例子，使用双向链表可以快速访问上一个歌曲和下一首歌曲。

创建节点

创建新节点的函数如下：

func CreateNewNode(value int) *Node {
    var node Node
    node.Next = nil
    node.Value = value
    node.Prev = nil
    return &node
}

双链表遍历

双向链表的遍历与单链表类似，需要首先检查链表是否为空。之后依次访问每个节点直到结束。

func TraverseDoublyLinkedList(head *Node) {
    if head == nil {
        fmt.Println("-> Empty list!")
        return
    }
    for head != nil {
        if head.Next != nil {
            fmt.Printf("%d <-> ", head.Value)
        } else {
            fmt.Printf("%d ", head.Value)
        }
        head = head.Next
    }
    fmt.Println()
}

为了测试，完整的代码如下：

package main
import "fmt"
type Node struct {
    Prev  *Node
    Value int
    Next  *Node
}
func CreateNewNode(value int) *Node {
    var node Node
    node.Next = nil
    node.Value = value
    node.Prev = nil
    return &node
}
func TraverseDoublyLinkedList(head *Node) {
    if head == nil {
        fmt.Println("-> Empty list!")
        return
    }
    for head != nil {
        if head.Next != nil {
            fmt.Printf("%d <-> ", head.Value)
        } else {
            fmt.Printf("%d ", head.Value)
        }
        head = head.Next
    }
    fmt.Println()
}
func main() {
    // 1 <-> 2 <-> 3 <-> 4 <-> 5
    head := CreateNewNode(1)
    node_2 := CreateNewNode(2)
    node_3 := CreateNewNode(3)
    node_4 := CreateNewNode(4)
    node_5 := CreateNewNode(5)
    head.Next = node_2
    node_2.Prev = head
    node_2.Next = node_3
    node_3.Prev = node_2
    node_3.Next = node_4
    node_4.Prev = node_3
    node_4.Next = node_5
    TraverseDoublyLinkedList(head)
}

运行该程序：

$ go run main.go
1 <-> 2 <-> 3 <-> 4 <-> 5

扩展功能

双链表可以扩展多种功能，以下是一些常见的操作：

链表长度

计算链表长度的函数如下：

func size(head *Node) int {
    if head == nil {
        fmt.Println("-> Empty list!")
        return 0
    }
    count := 0
    for head != nil {
        count++
        head = head.Next
    }
    return count
}

运行程序：

$ go run main.go
1 <-> 2 <-> 3 <-> 4 <-> 5
双链表的长度: 5

插入

新节点可以很容易地插入到双向链表中。具体来说，需要设置 prev_node 和 next_node 指针，将新节点与相邻节点正确链接起来。插入方式包括：

• 在节点之间插入
• 在双链表开头插入
• 插入一个空链表
• 在双链表末尾插入

删除

在双向链表中删除节点也很容易。具体来说，需要调整 prev_node 和 next_node 指针，将目标节点从链表中移除。删除方式包括：

• 删除最后的节点
• 删除第一个节点
• 在节点之间删除

反转双链表

反转双链表的过程包括：

1. 将 head 指针指向最后一个节点
2. 将最后一个节点的 prev_node 指针设为 NULL
3. 将第一个节点的 next_node 指针设为 NULL
4. 调整各个节点的 next_node 和 prev_node 指针，使其指向正确的位置

总结

与单链表相比，双链表提供了更多的便利性，可以从任何方向遍历，更方便地进行插入和删除操作。但同时也带来了额外的存储开销，因为每个节点需要维护两个指针。