数据结构基础入门——链表

用Go来实现链表、栈、队列、散列表、树、二叉树、堆、图

算法基础概念

时间维度：是指执行当前算法所消耗的时间，我们通常用「时间复杂度」来描述。
空间维度：是指执行当前算法需要占用多少内存空间，我们通常用「空间复杂度」来描述。
两者（时间和空间复杂度）经常不可兼得

数组是几乎主流都有的数据结构就不去实现了，实现第一个链表

链表认识

链表由一系列结点（每一个元素称为结点）组成，结点可以在运行时动态生成。每个结点包括两个部分：一个是存储数据元素的数据域，另一个是存储下一个结点地址的指针域。链表允许插入和移除表上任意位置上的结点，但是不允许随机存取。

优势：使用链表结构可以避免在使用数组时需要预先知道数据大小的缺点，链表结构可以充分利用计算机内存空间，实现灵活的内存动态管理。
缺点：链表失去了数组随机读取的优点，同时链表由于增加了结点的指针域，空间开销比较大。
分类：主要三种类型，单向链表、双向链表以及循环链表。

应用场景

支持循环播放的音乐列表其实就是个双向循环链表结构

实现单向链表

定义：单向链表中每个结点包含两部分，分别是数据域和指针域，上一个结点的指针指向下一结点，依次相连，形成链表。

Go 实现：

package main

import (
    "fmt"
)

// 定义节点 
type Node struct {
    Value int     //定义数据域
    Next  *Node   //定义地址域(指向下一个表的地址)
}

// 初始化头节点
var head = new(Node)

// 添加节点
func addNode(t *Node, v int) int {
    if head == nil {
        t = &Node{v, nil} //取地址
        head = t  //存入到head 
        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)
}

// 遍历链表
func traverse(t *Node) {
    if t == nil {
        fmt.Println("-> 空链表!")
        return
    }
    //单个循环条件 
    for t != nil {
        fmt.Printf("%d -> ", t.Value)
        t = t.Next
    }

    fmt.Println()
}

// 递归查找查找节点
func lookupNode(t *Node, v int) bool {
    if head == nil {
        t = &Node{v, nil}
        head = t
        return false
    }

    if v == t.Value {
        return true
    }
   //如果下一个节点为空就返回false 
    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
}

// 入口函数
func main() {
    fmt.Println(head)
    head = nil 
    // 遍历链表
    traverse(head) 
    // 添加节点 
    addNode(head, 1)
    addNode(head, -1)
    // 再次遍历
    traverse(head)
    // 添加更多节点
    addNode(head, 10)
    addNode(head, 5)
    addNode(head, 45)
    // 添加已存在节点
    addNode(head, 5)
    // 再次遍历
    traverse(head)

   // 查找已存在节点 
    if lookupNode(head, 5) {
        fmt.Println("该节点已存在!")
    } else {
        fmt.Println("该节点不存在!")
    }

   // 查找不存在节点  
    if lookupNode(head, -100) {
        fmt.Println("该节点已存在!")
    } else {
        fmt.Println("该节点不存在!")
    }
}

执行结果：go run xxxx

&{0 <nil>}
-> 空链表
1 ->-1 ->
该节点已存在
节点已存在 5
1 ->-1 ->10 ->5 ->45 ->
该节点不存在

学习警告：

学习需要趁热打铁，先定好学习路线再坚持不懈，切忌三心二意，学习完一个模块再到第二个模块，深入一门语言，再到第二门语言！必须在白板编辑器自己写出来的才是自己的，一遍不行，第二遍，第三遍，第四遍、至会方休、至死方休

参考站点：

www.cnblogs.com/lonely-wolf/p/1567...

geekr.dev/golang-tutorial#toc-7

数据结构基础 入门——链表