双链表算法
双链表最大的优势就是可以双向遍历
package main
import “fmt”
type Node struct {
num intname stringpre *Nodenext *Node
}
// 末尾插入
func insert(head Node, newNode Node) {tmp := headfor {// 插入末尾，先连接左边，后连接右边if tmp.next == nil {tmp.next = newNodenewNode.pre = tmpbreak}tmp = tmp.next}
}
// 正向遍历
func list(head *Node) {tmp := headif tmp.next == nil {fmt.Printf("link is null")}for {if tmp.next != nil {// 第一个tmp代表head的下一个fmt.Printf("[%d] = %s \n", tmp.next.num, tmp.next.name)} else {break}tmp = tmp.next}
}
// 反向遍历
func reverselist(head *Node) {tmp := headif tmp.next == nil {fmt.Printf("link is null")}// 先将tmp指向链表末尾for {if tmp.next == nil {break}tmp = tmp.next}for {// 注意头节点并不是空的，里面还有mext和preif tmp.pre != nil {fmt.Printf("[%d] = %s \n", tmp.num, tmp.name)} else {break}tmp = tmp.pre}
}
func main() {
// head是随机位置的指针head := &Node{ }// 插入数据不需传递下一个node地址node := &Node{num: 1,name: "amber",}node2 := &Node{num: 2,name: "alice",}node3 := &Node{num: 3,name: "necy",}node4 := &Node{num: 4,name: "bella",}insert(head, node)insert(head, node2)insert(head, node3)insert(head, node4)list(head)fmt.Println()reverselist(head)
}
输出结果：
双链表有序插入和删除
package main
import “fmt”
type Node struct {
num intname stringpre *Nodenext *Node
}
func orderInsert(head Node, newNode Node) {
tmp := headfor {// 必须放在前面，防止在末尾nil，被插在最后if newNode.num == tmp.num {fmt.Printf("node has already in link\n")break}// 放在第二顺位，当未找到插入最后if tmp.next == nil {tmp.next = newNodenewNode.pre = tmpbreak}// 遍历是从前往后，判断条件tmp.next是保证在tmp后面插入前插入if newNode.num < tmp.next.num {// 先关联右边，再关联左边newNode.next = tmp.nextnewNode.pre = tmptmp.next.pre = newNodetmp.next = newNodebreak}tmp = tmp.next}
}
func list(head *Node) {
tmp := headif tmp.next == nil {fmt.Printf("link is null")}for {if tmp.next != nil {// 第一个tmp代表head的下一个fmt.Printf("[%d] = %s \n", tmp.next.num, tmp.next.name)} else {break}tmp = tmp.next}
}
func delete(head *Node, num int) {
tmp := headfor {if tmp == nil {fmt.Printf("link is null")break}// 注意这里要找到tmp.next，因为找到tmp是要删除节点无法删除if tmp.num == num {if tmp.next == nil {tmp.pre.next = nilbreak} else {tmp.next.pre = tmp.pretmp.pre.next = tmp.nextbreak}}tmp = tmp.next}
}
func main() {
// head是随机位置的指针head := &Node{ }// 插入数据不需传递下一个node地址node := &Node{num: 1,name: "amber",}node2 := &Node{num: 2,name: "alice",}node3 := &Node{num: 3,name: "necy",}node4 := &Node{num: 3,name: "zoe",}orderInsert(head, node4)orderInsert(head, node2)orderInsert(head, node)orderInsert(head, node3)list(head)fmt.Printf("****************\n")delete(head, 2)list(head)
}
输出结果：
PS：这里演示的是重复插入在最后的情况，所以要将重复判断放在末尾插入之前
总结：
1、无论单链表还是双链表插入一定定位在tmp和tmp.next之间
2、头节点数据是空的，但不代表头节点=nil
3、删除和插入是一定要考虑删除的恰好是最后的节点或者插入到最后的情况
深碍√TFBOYSˉ_
╰+哭是因爲堅強的太久メ
亦凉
àì夳堔傛蜴生んèń
小灰灰
还没有评论，来说两句吧...