go 实现单向链表

短命女 2021-07-24 12:00 376阅读 0赞

# 一 点睛 #

## 1 链表是有序的列表，它在内存中是存储如下。 ##

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoZW5ncWl1bWluZw_size_16_color_FFFFFF_t_70][]

## 2 单链表示意图 ##

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoZW5ncWl1bWluZw_size_16_color_FFFFFF_t_70 1][]

一般来说，为了比较好的对单链表进行增删改查的操作，都会给它设置一个头结点，头结点的作用主要是用来标识链表头，本身这个结点不存放数据。

# 二 单链表实战 #

## 1 说明 ##

使用带 head 头的单向链表实现 –水浒英雄排行榜管理。

完成对英雄人物的增删改查操作。

## 2 代码 ##

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
    }
    
    // 第二种插入方法：给链表插入一个结点，根据 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 DelHerNode(head *HeroNode, id int) {
       temp := head
       flag := false
       // 找到要删除结点的 no，和 temp 的下一个结点的 no 比较
       for {
          if temp.next == nil { // 说明到链表的最后
             break
          } else if temp.next.no == id {
             // 找到了
             flag = true
             break
          }
          temp = temp.next
       }
       if flag { // 找到,删除
          temp.next = temp.next.next
       } else {
          fmt.Println("sorry, 要删除的id不存在")
       }
    }
    
    // 显示链表的所有结点信息
    func ListHeroNode(head *HeroNode) {
       // 创建一个辅助结点
       temp := head
       // 先判断该链表是不是一个空的链表
       if temp.next == nil {
          fmt.Println("空空如也。。。。")
          return
       }
       // 遍历这个链表
       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{}
       // 2 创建一个新的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)
       // 5 删除
       fmt.Println()
       DelHerNode(head, 1)
       DelHerNode(head, 3)
       ListHeroNode(head)
    }

## 3 测试 ##

[1 , 宋江 , 及时雨]==>[2 , 卢俊义 , 玉麒麟]==>[3 , 林冲 , 豹子头]==>
    [2 , 卢俊义 , 玉麒麟]==>

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoZW5ncWl1bWluZw_size_16_color_FFFFFF_t_70]: /images/20210724/1172f5cfea1140c4b49306d5645079b3.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoZW5ncWl1bWluZw_size_16_color_FFFFFF_t_70 1]: /images/20210724/659e0bbdada7423881ebf80c07c76166.png