关于go:go-链表

什么是链表

  链表是一种数据结构，链表作为一种根底的数据结构能够用来生成其它类型的数据结构。

  链表通常由一连串节点组成，节点能够在运行时动静生成，每个节点蕴含任意的实例数据（data fields）和存储下一个或下一个结点地址的指针域

  链表是有序的列表，数据元素的逻辑程序是通过链表中的指针链接秩序实现的

  应用链表构造能够防止在应用数组时须要事后晓得数据大小的毛病，链表构造能够充沛利用计算机内存空间，实现灵便的内存动静治理。然而链表失去了数组随机读取的长处，同时链表因为减少了结点的指针域，空间开销比拟大

  罕用的链表形式有三种:
  1. 单链表
  2. 双向链表
  3. 循环链表

链表的根底概念

链表蕴含头节点 (必须)、头指针、首元节点、其余节点

• 首元结点：就是链表中存储第一个元素的结点，如下图中 a1 的地位。
• 头结点：它是在首元结点之前附设的一个结点，其指针域指向首元结点。头结点的数据域能够存储链表的长度或者其它的信息，也能够为空不存储任何信息。
• 头指针：它是指向链表中第一个结点的指针。若链表中有头结点，则头指针指向头结点；若链表中没有头结点，则头指针指向首元结点。

头结点在链表中不是必须的，但减少头结点有以下几点益处:

• 减少了头结点后，首元结点的地址保留在头结点的指针域中，对链表的第一个数据元素的操作与其余数据元素雷同，无需进行非凡解决。
• 减少头结点后，无论链表是否为空，头指针都是指向头结点的非空指针，若链表为空的话，那么头结点的指针域为空

单向链表

单链表的模式如下图所示

实现一个单链表

package main

import ("fmt")

// 定义一个 HeroNode
type HeroNode struct {
    no int
    name  string
    nickname string
    next  *HeroNode // 这个示意指向下一个结点
}

// 给链表插入一个结点
// 编写第一种插入方法，在单链表的最初退出
func InsertHeroNode(head *HeroNode, newHeroNode *HeroNode) {
    //1. 先找到该链表的最初这个结点
    //2. 创立一个辅助结点
    temp := head
    for {
        if temp.next == nil { // 示意找到最初
            break
        }
        temp = temp.next //  让 temp 一直的指向下一个结点
    }

    //3. 将 newHeroNode 退出到链表的最初
    temp.next = newHeroNode
}

// 给链表插入一个结点
// 编写第 2 种插入方法，依据 no  的编号从小到大插入..【实用】func InsertHeroNode2(head *HeroNode, newHeroNode *HeroNode) {
    //1. 找到适当的结点
    //2. 创立一个辅助结点 [跑龙套, 帮忙]
    temp := head
    flag := true
    // 让插入的结点的 no，和 temp 的下一个结点的 no 比拟
    for {

        if temp.next == nil {
            // 阐明到链表的最初
            break
        } else if temp.next.no >= newHeroNode.no {
            // 阐明 newHeroNode 就应该插入到 temp 前面
            break
        } else if temp.next.no == newHeroNode.no {
            // 阐明咱们额链表中曾经有这个 no, 就不然插入. flag = false
            break
        }
        temp = temp.next
    }

    if !flag {fmt.Println("对不起，曾经存在 no=", newHeroNode.no)
        return
    } else {
        newHeroNode.next = temp.next
        temp.next = newHeroNode
    }
}

// 显示链表的所有结点信息
func ListHeroNode(head *HeroNode) {
    //1. 创立一个辅助结点
    temp := head

    // 先判断该链表是不是一个空的链表
    if temp.next == nil {fmt.Println("空洞无物。。。。")
        return
    }
    //2. 遍历这个链表
    for {fmt.Printf("[%d , %s , %s]==>", temp.next.no, temp.next.name, temp.next.nickname)
        // 判断是否链表后
        temp = temp.next
        if temp.next == nil {break}
    }
}

func main() {
    //1. 先创立一个头结点
    head := &HeroNode{}
    hero1 := &HeroNode{
        no : 1,
        name : "张三",
        nickname : "法外狂徒",
    }
    hero2 := &HeroNode{
        no : 2,
        name : "王五",
        nickname : "隔壁老王",
    }
    hero3 := &HeroNode{
        no : 3,
        name : "李四",
        nickname : "坏蛋老四",
    }
    //3. 退出
    InsertHeroNode2(head, hero3)
    InsertHeroNode2(head, hero1)
    InsertHeroNode2(head, hero2)

    // 4. 显示
    ListHeroNode(head)
}

执行输入后果

>go run main.go

[1 , 张三 , 法外狂徒]==>[2 , 王五 , 隔壁老王]==>[3 , 李四 , 坏蛋老四]==>