双向链表

双向链表的应用实例：

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

单向链表的缺点分析：

• 单向链表，查找的方向只能是一个方向，而双向链表可以向前或者向后查找；
• 单向链表不能自我删除，需要靠辅助节点，而双向链表，则可以自我删除，所以前面我们单链表删除节点时，总是找到temp的下一个节点来删除的 。

代码实现：

package main

import "fmt"

//定义一个HeroNode
type HeroNode struct {
    no       int
    name     string
    nickname string
    next     *HeroNode //这个表示指向下一个节点；
    pre      *HeroNode //指向前一个节点
}

//给双向链表插入一个节点
//编写第一种插入方法，在双向链表的最后加入：
func AppendHeroNode(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 InsertHeroNode(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)
    } else { //在往链表中插入节点时，改变链表关系的顺序很重要，个人理解为：优先修改新节点的指向，先右后左。
        newHeroNode.next = temp.next
        newHeroNode.pre = temp
        if temp.next != nil {
            temp.next.pre = newHeroNode
        }
        temp.next = newHeroNode
    }
}

//双向链表删除一个节点
func DelHeroNode(head *HeroNode, id int) {
    temp := head
    flag := false

    //找到要删除的节点，和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("要删除的节点不存在...")
    }
}

//显示双向链表的所有节点信息：
//这里仍然使用和单向的链表一样的显示方式；
func ListHeroNode(head *HeroNode) {
    //1.创建辅助节点temp
    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
        }
    }
    fmt.Println()
}

//逆序显示：
func ListHeroNodeReverse(head *HeroNode) {
    //1.创建辅助节点temp
    temp := head

    //先判断该链表是不是一个空的链表：
    if temp.next == nil {
        fmt.Println("空空入也。。。")
        return
    }

    //2.让temp定位到双向链表的最后节点：
    for {
        if temp.next == nil {
            break
        }
        temp = temp.next
    }

    //2.遍历这个链表
    for {
        fmt.Printf("[%d, %s, %s]==>", temp.no, temp.name, temp.nickname)
        //判断是否到链表尾部；
        temp = temp.pre
        if temp.pre == nil {
            break
        }
    }
    fmt.Println()
}

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: "豹子头",
    }

    hero4 := &HeroNode{
        no:       3,
        name:     "卢俊义",
        nickname: "玉麒麟",
    }

    AppendHeroNode(head, hero1)
    AppendHeroNode(head, hero3)
    InsertHeroNode(head, hero2)
    AppendHeroNode(head, hero4)
    ListHeroNode(head)
    DelHeroNode(head, 3)
    fmt.Println("逆序打印：")
    ListHeroNodeReverse(head)
}