单向链表的问题：

  1. 单向链表只能一个方向查找，双向链表可以向前也可以向后查找（前后两个方向查找）

  2. 单向链表不能自我删除，，需要考辅助节点。双向链表可以自我删除

    示意图

    image.png
    image.png
    image.png

    注意：

  3. 按顺序插入 ```go // newNode 应该插入 temp.next 前面， temp后面 newNode.next = temp.next newNode.pre = temp

if temp.next != nil { temp.next.pre = newNode }

temp.next = newNode

  2. 2. 删除节点
  3. ```go
  4. // 删除， 更改节点指向
  5. temp.next = temp.next.next
  6. // 判断是否是最后一个
  7. if temp.next != nil {
  8.     temp.next.pre = temp
  9. }

代码实现

  1. // 双向链表 - 增删改查
  2. package main
  4. import (
  5.     "fmt"
  6. )
  8. // 定义节点
  9. type HeroNode struct {
  10.     no       int
  11.     name     string
  12.     nickname string
  13.     pre      *HeroNode // 表示指向前一个节点
  14.     next     *HeroNode // 表示指向下一个节点
  15. }
  17. // 添加节点
  18. func insertNode(head *HeroNode, newNode *HeroNode) {
  19.     // 1. 找到链表最后的节点
  20.     // 2. 创建辅助节点， 跑龙套的
  21.     temp := head
  22.     for {
  23.         if temp.next == nil {
  24.             // 最后的节点
  25.             break
  26.         }
  27.         temp = temp.next // temp 一直后移, 直到指向链表最后的节点
  28.     }
  29.     // 3. 修改 temp 节点的 next 指向 newNode, 并将新节点的 pre 指向 temp
  30.     temp.next = newNode
  31.     newNode.pre = temp
  32. }
  34. // 根据 编号 no 插入到指定位置（从小到大）
  35. func insertNode02(head *HeroNode, newNode *HeroNode) {
  36.     // 1. 找到链表适当的节点
  37.     // 2. 创建辅助节点， 跑龙套的
  38.     temp := head
  39.     flag := true
  40.     for {
  41.         if temp.next == nil {
  42.             // 最后的节点
  43.             break
  44.         } else if temp.next.no > newNode.no {
  45.             // 升降序， 只需要修改 temp.next.no < newNode.no
  46.             break
  47.         } else if temp.next.no == newNode.no {
  48.             fmt.Println("已经存在，不允许加入")
  49.             flag = false
  50.             break
  51.         }
  52.         temp = temp.next // temp 一直后移,
  53.     }
  54.     if !flag {
  55.         fmt.Println("不能插入节点")
  56.         return
  57.     } else {
  58.         // newNode 应该插入 temp.next 前面， temp后面
  59.         newNode.next = temp.next
  60.         newNode.pre = temp
  62.         if temp.next != nil {
  63.             temp.next.pre = newNode
  64.         }
  66.         temp.next = newNode
  68.     }
  69. }
  71. // 删除节点
  72. func delNode(head *HeroNode, id int) {
  73.     // 1. 先来一个跑龙套的
  74.     temp := head
  76.     flag := false
  78.     // 2. 找到要删除的节点
  79.     for {
  80.         if temp.next == nil {
  81.             break
  82.         } else if temp.next.no == id {
  83.             // 找到了
  84.             flag = true
  85.             break
  86.         }
  87.         temp = temp.next
  88.     }
  89.     if flag {
  90.         // 删除， 更改节点指向
  91.         temp.next = temp.next.next
  92.         // 判断是否是最后一个
  93.         if temp.next != nil {
  94.             temp.next.pre = temp
  95.         }
  96.     } else {
  97.         fmt.Println("要删除的节点id不存在")
  98.     }
  99. }
  101. // 显示链表所有节点信息
  102. func showNode(head *HeroNode) {
  103.     // 1. 创建辅助节点， 跑龙套的
  104.     temp := head
  105.     // 2. 判断该链表是不是空的
  106.     if temp.next == nil {
  107.         fmt.Println("空链表")
  108.         return
  109.     }
  110.     // 2. 遍历链表
  111.     for {
  112.         fmt.Printf("[%d , %s , %s] => ", temp.next.no, temp.next.name, temp.next.nickname)
  113.         temp = temp.next
  114.         if temp.next == nil {
  115.             break
  116.         }
  117.     }
  118.     fmt.Println()
  119. }
  121. // 逆序 显示链表所有节点信息
  122. func showNode02(head *HeroNode) {
  123.     // 1. 创建辅助节点， 跑龙套的
  124.     temp := head
  126.     // 2. 判断该链表是不是空的
  127.     if temp.next == nil {
  128.         fmt.Println("空链表")
  129.         return
  130.     }
  132.     // temp 定位到最后节点
  133.     for {
  134.         if temp.next == nil {
  135.             break
  136.         }
  137.         temp = temp.next
  138.     }
  140.     // 2. 遍历链表
  141.     for {
  142.         fmt.Printf("[%d , %s , %s] => ", temp.no, temp.name, temp.nickname)
  143.         temp = temp.pre
  144.         if temp.pre == nil {
  145.             break
  146.         }
  147.     }
  148.     fmt.Println()
  149. }
  151. func main() {
  152.     // 1. 创建头节点
  153.     head := &HeroNode{}
  155.     // 2. 创建 HeroNode
  156.     hero1 := &HeroNode{
  157.         no:       1,
  158.         name:     "luffy",
  159.         nickname: "海贼王",
  160.     }
  161.     hero2 := &HeroNode{
  162.         no:       2,
  163.         name:     "索隆",
  164.         nickname: "大剑豪",
  165.     }
  166.     hero3 := &HeroNode{
  167.         no:       3,
  168.         name:     "山治",
  169.         nickname: "allblue",
  170.     }
  171.     hero4 := &HeroNode{
  172.         no:       4,
  173.         name:     "甚平",
  174.         nickname: "海侠",
  175.     }
  177.     insertNode02(head, hero1)
  178.     insertNode02(head, hero3)
  179.     insertNode02(head, hero2)
  180.     insertNode02(head, hero4)
  182.     fmt.Println("正序显示")
  183.     showNode(head)
  185.     fmt.Println("删除指定节点")
  186.     delNode(head, 3)
  188.     fmt.Println("逆序显示")
  189.     showNode02(head)
  191. }
  193. /*
  194. 正序显示
  195. [1 , luffy , 海贼王] => [2 , 索隆 , 大剑豪] => [3 , 山治 , allblue] => [4 , 甚平 , 海侠] =>
  196. 删除指定节点
  197. 逆序显示
  198. [4 , 甚平 , 海侠] => [2 , 索隆 , 大剑豪] => [1 , luffy , 海贼王] =>
  199. */