go 实现双向链表

叁歲伎倆 2021-07-24 15:44 351阅读 0赞

# 一 说明 #

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

单向链表的缺点分析。

1 单向链表，查找的方向只能是一个方向，而双向链表可以向前或者向后查找。

2 单向链表不能自我删除，需要靠辅助节点，而双向链表，则可以自我删除，单链表删除时，总要找到 temp 的下一个节点来删除。

# 二 图解 #

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoZW5ncWl1bWluZw_size_16_color_FFFFFF_t_70][]

# 三 代码 #

package main
    
    import (
       "fmt"
    )
    
    // HeroNode
    type HeroNode struct {
       no       int
       name     string
       nickname string
       pre      *HeroNode // 指向前一个结点
       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
       newHeroNode.pre = temp
    }
    
    // 给双向链表插入一个结点，根据 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
          newHeroNode.pre = temp
          if temp.next != nil {
             temp.next.pre = newHeroNode
          }
          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
          if temp.next != nil {
             temp.next.pre = temp
          }
       } else {
          fmt.Println("sorry, 要删除的id不存在")
       }
    }
    
    // 显示链表的所有结点信息，仍然使用单向的链表显示方式
    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 ListHeroNode2(head *HeroNode) {
       // 1 创建一个辅助结点
       temp := head
       // 先判断该链表是不是一个空的链表
       if temp.next == nil {
          fmt.Println("空空如也。。。。")
          return
       }
    
       // 2 让 temp 定位到双向链表的最后结点
       for {
          if temp.next == nil {
             break
          }
          temp = temp.next
       }
    
       // 3 遍历这个链表
       for {
          fmt.Printf("[%d , %s , %s]==>", temp.no,
             temp.name, temp.nickname)
          // 判断是否是链表头
          temp = temp.pre
          if temp.pre == 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: "豹子头",
       }
       InsertHeroNode(head, hero1)
       InsertHeroNode(head, hero2)
       InsertHeroNode(head, hero3)
       ListHeroNode(head)
       fmt.Println("逆序打印")
       ListHeroNode2(head)
    }

# 四 测试 #

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

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoZW5ncWl1bWluZw_size_16_color_FFFFFF_t_70]: /images/20210724/438e7358954e4dba9738ebcd16ec7ef5.png