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

用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
更详细版 www.jianshu.com/p/7ada92d5eeac

本作品采用《CC 协议》,转载必须注明作者和本文链接
滴水穿石,石破天惊----晓疯子
讨论数量: 0
(= ̄ω ̄=)··· 暂无内容!

讨论应以学习和精进为目的。请勿发布不友善或者负能量的内容,与人为善,比聪明更重要!