学习 Go 语言数据结构：实现双链表

作者：宇宙之一粟

2022 年 8 月 25 日
广东
本文字数：1687 字
阅读完需：约 6 分钟

双链表

双链表 （Doubly Linked List），每个节点持有一个指向列表前一个元素的指针，以及指向下一个元素的指针。

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

数据域 Value
一个 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.go1 <-> 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.go1 <-> 2 <-> 3 <-> 4 <-> 5 双链表的长度:  5

复制代码

插入

一个新节点可以很容易地插入到双向链表中。我们只需要设置指针 prev_node 和 next_node 小心地将 prev_node 和 next_node 节点与适当的指针链接起来。

如果要在节点 n1 和 n3 之间插入节点 n2，则应将 n2 的指针 prev_node 设置为 n1，将 n2 的指针 next_node 设置为 n3。

双向链表中的插入可以通过多种方式完成：

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

删除

在双向链表中可以很容易地删除节点。我们只需要将指针 prev_node 和 next_node 逻辑设置为节点。可以通过以下方式删除节点：

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

反转双链表

假设我们有四个节点 n1、n2、n3 和 n4

反转的步骤如下：

指针 head 指向最后一个节点 n4
由于 n4 现在是第一个节点，它的 prev_node 指针必须为 NULL
节点 n1 是最后一个节点，因此它的 next_node 必须为 NULL
n4 的指针 next_node 指向 n3，n3 的 next_node 指向 n2，n2 的 next_node 指向 n1
n1 的指针 prev_node 指向 n2，n2 的 prev_node 指向 n3，n3 的 prev_node 指向 n4

总结

与单链表相比，双链表具有多样性，可以从任何方向遍历双向链表，从而更方便的插入和删除元素。

但是为了维护每个节点的指针，会多一些额外的开销。

参考链接：

发布于: 刚刚阅读数: 3

原文链接:【http://xie.infoq.cn/article/c15be058a7ff4e36dfdea1511】。文章转载请联系作者。

宇宙之一粟

关注

宇宙古今无有穷期，一生不过须臾，当思奋争 2020.05.07 加入

🏆InfoQ写作平台-第二季签约作者 🏆 混迹于江湖，江湖却没有我的影子热爱技术，专注于后端全栈，轻易不换岗拒绝内卷，工作于软件工程师，弹性不加班热衷分享，执着于阅读写作，佛系不水文

发布

暂无评论

创作场景

学习 Go 语言数据结构：实现双链表

双链表

创建节点

双链表遍历

扩展功能

链表长度

插入

删除

反转双链表

总结

宇宙之一粟

评论