Liu Guang

链表

Go实现带头结点的链表

Liuguang   2022-07-07 13:22:49

与前期文章Go实现链表操作不同的是,本文用Go语言实现了一个带头节点的链表,通过增加头结点有一定的作用和好处:

  • 头节点的数据域,可以用来存放节点数量
  • 有了头结点,诸多操作可以统一

linklist.png

1、定义节点结构

package main

import (
    "fmt"
    "strconv"
)

type Node struct {
    data interface{}
    next *Node
}

var LinkList *Node

2、链表初始化操作

// 初始化一个带头结点的链表
// 头节点的数据域,可以用来存放节点数量
// 有了头结点,诸多操作可以统一
func InitList(L *Node) *Node {
    L = new(Node)
    L.data = 0
    L.next = nil
    return L
}

3、从尾部插入数据,尾插法

// 从尾部插入数据,尾插法
func AddAft(L *Node, data interface{}) {
    node := Node{data: data, next: nil}
    tmp := L
    for tmp.next != nil {
        tmp = tmp.next
    }
    tmp.next = &node
    //更新节点数量
    L.data = GetInterfaceToInt(L.data) + 1

}

4、头部插入数据,头插法

// 从头部插入数据,头插法
func AddPre(L *Node, data interface{}) {
    node := Node{data: data, next: nil}

    node.next = L.next
    L.next = &node
    //更新节点数量
    L.data = GetInterfaceToInt(L.data) + 1
}

5、根据索引查找数据

//根据索引查找
func Search(L *Node, index int) (interface{}, bool) {
    tmp := L
    for i := 0; i < index; i++ {
        if tmp.next != nil {
            tmp = tmp.next
        } else {
            fmt.Println("索引越界")
            return 0, false
        }
    }
    return tmp.data, true
}

6、根据索引删除数据

//根据索引删除
func Delete(L *Node, index int) bool {
    // tmp迭代使用
    tmp := L
    //定义当前节点curr,即准备删除的节点
    curr := L.next
    //定义前驱节点pre
    pre := L
    for i := 0; i < index; i++ {
        if tmp.next != nil {
            pre = tmp
            curr = tmp.next
            tmp = tmp.next
        } else {
            fmt.Println("索引越界")
            return false
        }

    }
    pre.next = curr.next
    //更新节点数量
    L.data = GetInterfaceToInt(L.data) - 1
    return true
}

7、遍历打印所有数据

func ShowAll(L *Node) {
    if L.next == nil {
        fmt.Println("no data")
    } else {
        tmp := L.next
        for tmp != nil {
            fmt.Println(tmp.data)
            tmp = tmp.next
        }
    }
}

8、interface转int函数

由于头结点中的数据域用来存放节点数量,而节点中的数据域为interface类型,因此需要interface与int型的转换

//​interface转int
func GetInterfaceToInt(t1 interface{}) int {
    var t2 int
    switch t1.(type) {
    case uint:
        t2 = int(t1.(uint))
        break
    case int8:
        t2 = int(t1.(int8))
        break
    case uint8:
        t2 = int(t1.(uint8))
        break
    case int16:
        t2 = int(t1.(int16))
        break
    case uint16:
        t2 = int(t1.(uint16))
        break
    case int32:
        t2 = int(t1.(int32))
        break
    case uint32:
        t2 = int(t1.(uint32))
        break
    case int64:
        t2 = int(t1.(int64))
        break
    case uint64:
        t2 = int(t1.(uint64))
        break
    case float32:
        t2 = int(t1.(float32))
        break
    case float64:
        t2 = int(t1.(float64))
        break
    case string:
        t2, _ = strconv.Atoi(t1.(string))
        break
    default:
        t2 = t1.(int)
        break
    }
    return t2
}

9、主函数

func main() {
    LinkList = InitList(LinkList)

    AddAft(LinkList, "hello1")
    AddAft(LinkList, "hello2")
    AddAft(LinkList, "hello3")
    AddAft(LinkList, 100)

    AddPre(LinkList, "pre data")
    fmt.Println("打印所有数据:")
    ShowAll(LinkList)

    fmt.Println("查找索引为3的数据:")
    d1, ok := Search(LinkList, 3)
    if ok {
        fmt.Println(d1)
    }
    fmt.Println("查找索引为5的数据:")
    d2, ok := Search(LinkList, 5)
    if ok {
        fmt.Println(d2)
    }
    fmt.Println("查找索引为6的数据:")
    d3, ok := Search(LinkList, 6)
    if ok {
        fmt.Println(d3)
    }
    fmt.Println("删除索引为3的数据:")
    ok2 := Delete(LinkList, 3)
    if ok2 {
        fmt.Println("删除成功")
    }
    fmt.Println("再次打印所有数据:")
    ShowAll(LinkList)
}

10、运行效果如下

打印所有数据:
pre data
hello1
hello2
hello3
100
查找索引为3的数据:
hello2
查找索引为5的数据:
100
查找索引为6的数据:
索引越界
删除索引为3的数据:
删除成功
再次打印所有数据:
pre data
hello1
hello3
100

从实验中我们可以看出,增加了头结点的链表,各种操作均更加简便快捷

链表

0 Comments

message
沪ICP备17044897号-3 © 2022 Phpangel Xu - GitHub
Login