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

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

article 2024/11/15 23:50:31

链表基础

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

链表的操作

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

Go中的链表实现

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

package main

import (
    "fmt"
)

// 定义链表节点结构
type Node struct {
    Value int
    Next  *Node
}

// 全局变量root，保存链表的头结点
var root = new(Node)

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

添加节点

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

func addNode(t *Node, v int) int {
    if root == nil {
        t = &Node{v, nil}
        root = t
        return 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 = t
        return 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 := 0
    for t != nil {
        i++
        t = t.Next
    }
    return i
}

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

主函数测试

func main() {
    fmt.Println(root)
    root = nil
    traverse(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    int
    Previous *Node
    Next     *Node
}

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

添加节点

func addNode(t *Node, v int) int {
    if root == nil {
        t = &Node{v, nil, nil}
        root = t
        return 0
    }
    if v == t.Value {
        fmt.Println("节点已存在:", v)
        return -1
    }
    if t.Next == nil {
        temp := t
        t.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 := t
    for t != nil {
        temp = t
        t = t.Next
    }
    for temp.Previous != nil {
        fmt.Printf("%d -> ", temp.Value)
        temp = temp.Previous
    }
    fmt.Printf("%d -> ", temp.Value)
    fmt.Println()
}