1.1.1. 一、双向链表的说明:
1、双向链表的元素,同时指向上一个元素和下一个元素。结构如下:
type Persion struct {
Pre *Persion // 上一个节点
Num int
Name string
next *Persion // 下一个节点
}
说明:
1、如果 next == nil 表示最后一个元素。
2、如果 Pre == nil 表示头一个元素。
2、单向链表只能往一个方向查找。双向链表可以向前和向后查找。
3、单向链表不能实现自我删除。双向链表可以自我删除。
1.1.2. 二、双向链表的实现如下:
// 链表
type Persion struct {
Pre *Persion // 上一个节点
Num int
Name string
next *Persion // 下一个节点
}
//增加一个节点,方式1:在单链表的最后加入
func InsertNode(head *Persion, newNode *Persion) {
//从head开始,查找最后一个结点(temp.next == nil 的节点)
temp := head
for {
if temp.next == nil { //表示找到最后
break
}
temp = temp.next //下一个结点
}
// 加入节点
temp.next = newNode
newNode.Pre = temp
}
//增加一个节点,按照num的值排序
func InsertNodeByNum(head *Persion, newNode *Persion) {
//从head开始,查找最后一个结点(temp.next == nil 的节点)
temp := head
flag := true
for {
if temp.next == nil { //表示找到最后
break
} else if temp.next.Num >= newNode.Num { //新节点在temp和temp.next之间。也就是temp后面
break
} else if temp.next.Num == newNode.Num {
//说明我们额链表中已经有这个 no,就不插入.
flag = false
break
}
temp = temp.next //下一个结点
}
if !flag {
fmt.Println("对不起,已经存在 Num=", newNode.Num)
return
} else {
newNode.Pre = temp
newNode.next = temp.next
if temp.next != nil {
temp.next.Pre = newNode
}
temp.next = newNode
}
}
//显示链表的所有结点信息
func ListNode(head *Persion) {
temp := head
// 先判断该链表是不是一个空的链表
if temp.next == nil {
fmt.Println("空空如也。。。。")
return
}
//遍历这个链表
for {
fmt.Printf("[%d , %s ]==>", temp.next.Num, temp.next.Name)
temp = temp.next
if temp.next == nil { //判断是否链表后
break
}
}
}
// 删除节点
func delNodeByNum(head *Persion,num int) {
temp := head
flag := false // 是否找到节点
for {
if temp.next == nil { //表示找到最后
break
} else if temp.next.Num == num {
flag = true
break
}
temp = temp.next //下一个结点
}
if flag { // 找到,删除节点是 temp.next
temp.next = temp.next.next
if temp.next !=nil {
temp.next.Pre = temp
}
} else {
fmt.Println("没有找到要删除的节点")
}
}
说明:整个实现和单向列表差不多。不同的是要注意设置上一个节点Pre的值。
1、实现了链表的增加。在尾部增加 InsertNode;按照num排序增加节点 InsertNodeByNum。
2、实现了根据元素的num值,删除元素delNodeByNum。
3、实现了显示链表信息ListNode。
- 测试代码如下:
func main() {
//1. 先创建一个头结点
head := &Persion{}
p1 := &Persion{Num:100,Name:"张三",}
p2 := &Persion{Num:101,Name:"李四",}
p3 := &Persion{Num:99,Name:"王五",}
// 插入链表
InsertNodeByNum(head,p1)
InsertNodeByNum(head,p2)
InsertNodeByNum(head,p3)
// 显示链表
ListNode(head)
delNodeByNum(head,101)//删除
fmt.Println()
// 显示链表
ListNode(head)
}