当前位置：首页 > news >正文

Go语言中的链表与双向链表实现

news 来源：原创 2024/9/20 12:10:51

链表基础

链表是一种由有限元素组成的数据结构，其中每个元素至少使用两个内存空间：一个存储实际数据，另一个存储指向下一个元素的指针，从而形成一个元素序列构成链表。链表的第一个元素称为头结点，而最后一个元素通常被称为尾结点。为了操作链表，保持对头结点的引用非常重要，因为头结点是我们访问整个链表的唯一入口。如果丢失了指向头结点的指针，将无法再次找到链表的其他元素。

链表的操作

在链表中，移除节点时，主要操作是调整要删除节点的前一个节点的指针，使其指向要删除节点的下一个节点。

Go中的链表实现

我们通过Go语言的链表实现来更好地理解链表的操作过程。

package mainimport ("fmt"
)// 定义链表节点结构
type Node struct {Value intNext  *Node
}// 全局变量root，保存链表的头结点
var root = new(Node)

在以上代码中，定义了链表节点的结构，包含一个Value用于存储节点的值，一个Next指针指向链表的下一个节点。此外，还定义了一个全局变量root，用于保存链表的头结点。

添加节点

链表通常不允许重复元素，并且当链表未排序时，新节点通常添加到链表末尾。以下是添加节点的代码实现：

func addNode(t *Node, v int) int {if root == nil {t = &Node{v, nil}root = treturn 0}if v == t.Value {fmt.Println("节点已存在:", v)return -1}if t.Next == nil {t.Next = &Node{v, nil}return -2}return addNode(t.Next, v)
}

在addNode函数中，首先检查链表是否为空，如果为空，则将新节点作为头结点插入。接着，检查链表中是否已有待插入的值，避免重复元素。如果当前节点的Next指针为空，说明已到达链表末尾，便将新节点添加到链表的末尾。若以上情况均不满足，则递归地继续检查下一个节点。

遍历链表

遍历链表的代码如下：

func traverse(t *Node) {if t == nil {fmt.Println("-> 空链表!")return}for t != nil {fmt.Printf("%d -> ", t.Value)t = t.Next}fmt.Println()
}

traverse函数通过循环遍历链表，并输出每个节点的值，直到遍历到最后一个节点。

查找节点与计算链表长度

func lookupNode(t *Node, v int) bool {if root == nil {t = &Node{v, nil}root = treturn false}if v == t.Value {return true}if t.Next == nil {return false}return lookupNode(t.Next, v)
}func size(t *Node) int {if t == nil {fmt.Println("-> 空链表!")return 0}i := 0for t != nil {i++t = t.Next}return i
}

lookupNode用于检查链表中是否存在某个值，而size函数用于计算链表的长度，即节点的数量。通过递归或循环，分别遍历链表的每个节点，返回结果。

主函数测试

func main() {fmt.Println(root)root = niltraverse(root)addNode(root, 1)addNode(root, -1)traverse(root)addNode(root, 10)addNode(root, 5)addNode(root, 45)traverse(root)if lookupNode(root, 100) {fmt.Println("节点存在!")} else {fmt.Println("节点不存在!")}fmt.Println("链表长度:", size(root))
}

输出结果：

&{0 <nil>}
-> 空链表!
1 -> -1 ->
1 -> -1 -> 10 -> 5 -> 45 ->
节点不存在!
链表长度: 5

链表的优势

链表的优势在于其灵活性和实现的简单性，适合处理各种数据类型。链表在进行顺序查找时效率较高，特别是在动态数据管理（如插入和删除）时优于数组等静态数据结构。此外，链表可以动态增长，且删除节点的操作较为简单，尤其是有序链表。

双向链表

双向链表是一种特殊的链表结构，每个节点不仅有一个指向下一个节点的指针，还有一个指向前一个节点的指针。这样可以实现双向遍历。双向链表的头节点的前一个节点为nil，尾节点的下一个节点也为nil。

Go中的双向链表实现

双向链表的节点定义如下：

type Node struct {Value    intPrevious *NodeNext     *Node
}

该结构体中有两个指针字段：一个指向前一个节点，一个指向下一个节点。

添加节点

func addNode(t *Node, v int) int {if root == nil {t = &Node{v, nil, nil}root = treturn 0}if v == t.Value {fmt.Println("节点已存在:", v)return -1}if t.Next == nil {temp := tt.Next = &Node{v, temp, nil}return -2}return addNode(t.Next, v)
}

与单链表类似，双向链表的节点通常添加到链表末尾。

遍历与反向遍历

func traverse(t *Node) {if t == nil {fmt.Println("-> 空链表!")return}for t != nil {fmt.Printf("%d -> ", t.Value)t = t.Next}fmt.Println()
}func reverse(t *Node) {if t == nil {fmt.Println("-> 空链表!")return}temp := tfor t != nil {temp = tt = t.Next}for temp.Previous != nil {fmt.Printf("%d -> ", temp.Value)temp = temp.Previous}fmt.Printf("%d -> ", temp.Value)fmt.Println()
}