链表的定义
链表是一种物理存储单元上非连续、非顺序的存储结构,数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列结点(链表中每一个元素称为结点)组成,结点可以在运行时动态生成。每个结点包括两个部分:一个是存储数据元素的数据域,另一个是存储下一个结点地址的指针域。
单链表
链表中的数据是以结点来表示的,每个结点的构成:元素(数据元素的映象) + 指针(指示后继元素存储位置),元素就是存储数据的存储单元,指针就是连接每个结点的地址数据。
以“结点的序列”表示线性表称作线性链表(单链表),单链表是链式存取的结构。
存储格式如下:
说明:一般来说,为了比较好的对单链表进行增删改查的操作,我们都会给他设置一个头结点,头结点的作用主要是用来表示链表头,本身这个节点不存放数据。
代码实现
package main import "fmt" // 定义一个 HeroNode type HeroNode struct { No int Name string NickName string Next *HeroNode } // 在链表尾部加入数据 func AddTail(head *HeroNode, newHeroNode *HeroNode) { // 找到链表的最后一个节点 tmp := head for { if tmp.Next == nil { // 表示找到最后一个节点 break } tmp = tmp.Next // 让tmp不断的指向下一个节点 } //将newHeroNode 加入到尾部 tmp.Next = newHeroNode } // 根据编号大小插入节点 func Insert(head *HeroNode, newHeroNode *HeroNode) { tmp := head flag := true for { if tmp.Next == nil { // 说明到链表的最后 break } else if tmp.Next.No > newHeroNode.No { // 说明 newHeroNode 应该插入到 head的后面 break } else if tmp.Next.No == newHeroNode.No { // 已存在no,不允许加入 flag = false break } tmp = tmp.Next } if flag == false { fmt.Println("添加失败,已存在no=", newHeroNode.No) return } newHeroNode.Next = tmp.Next tmp.Next = newHeroNode } // 显示链表所有节点信息 func List(head *HeroNode) { tmp := head if tmp.Next == nil { fmt.Println("链表为空") return } for { tmp = tmp.Next fmt.Printf("[%d, %s, %s]-->", tmp.No, tmp.Name, tmp.NickName) if tmp.Next == nil { // 判断是否到链表的最后 break } } fmt.Println() } // 删除节点 func Del(head *HeroNode, no int) { tmp := head flag := false for { if tmp.Next == nil { break } else if tmp.Next.No == no { // 说明找到了要删除的节点 flag = true break } tmp = tmp.Next } if flag == false { fmt.Println("要删除的no不存在,no=", no) return } tmp.Next = tmp.Next.Next } func main() { // 创建头节点 head := &HeroNode{} // 创建新的节点 hero1 := &HeroNode{ No: 1, Name: "宋江", NickName: "及时雨", } hero2 := &HeroNode{ No: 2, Name: "卢俊义", NickName: "玉麒麟", } hero3 := &HeroNode{ No: 3, Name: "林冲", NickName: "豹子头", } // 尾部添加节点 AddTail(head, hero1) AddTail(head, hero3) // 显示节点信息 List(head) // 中间插入节点 Insert(head, hero2) // 显示节点信息 List(head) // 删除节点 Del(head, 1) // 显示节点信息 List(head) }
运行结果:
[1, 宋江, 及时雨]-->[3, 林冲, 豹子头]--> [1, 宋江, 及时雨]-->[2, 卢俊义, 玉麒麟]-->[3, 林冲, 豹子头]--> [2, 卢俊义, 玉麒麟]-->[3, 林冲, 豹子头]-->
双向链表
双向链表也叫双链表,是链表的一种,它的每个数据结点中都有两个指针,分别指向直接后继和直接前驱。所以,从双向链表中的任意一个结点开始,都可以很方便地访问它的前驱结点和后继结点。一般我们都构造双向循环链表。
示意图:
代码实现:
package main import "fmt" // 定义一个 HeroNode type HeroNode struct { No int Name string NickName string Pre *HeroNode Next *HeroNode } // 在链表尾部加入数据 func AddTail(head *HeroNode, newHeroNode *HeroNode) { // 找到链表的最后一个节点 tmp := head for { if tmp.Next == nil { // 表示找到最后一个节点 break } tmp = tmp.Next // 让tmp不断的指向下一个节点 } //将newHeroNode 加入到尾部 tmp.Next = newHeroNode newHeroNode.Pre = tmp } // 根据编号大小插入节点 func Insert(head *HeroNode, newHeroNode *HeroNode) { tmp := head flag := true for { if tmp.Next == nil { // 说明到链表的最后 break } else if tmp.Next.No > newHeroNode.No { // 说明 newHeroNode 应该插入到 head的后面 break } else if tmp.Next.No == newHeroNode.No { // 已存在no,不允许加入 flag = false break } tmp = tmp.Next } if flag == false { fmt.Println("添加失败,已存在no=", newHeroNode.No) return } newHeroNode.Next = tmp.Next newHeroNode.Pre = tmp if tmp.Next != nil { // 判断插入是是否是尾部插入 tmp.Next.Pre = newHeroNode } tmp.Next = newHeroNode } // 显示链表所有节点信息 func List(head *HeroNode) { tmp := head if tmp.Next == nil { fmt.Println("链表为空") return } for { tmp = tmp.Next fmt.Printf("[%d, %s, %s]-->", tmp.No, tmp.Name, tmp.NickName) if tmp.Next == nil { // 判断是否到链表的最后 break } } fmt.Println() } // 逆序显示链表所有节点信息 func ListReverse(head *HeroNode) { fmt.Println("逆序显示节点信息:") tmp := head if tmp.Next == nil { fmt.Println("链表为空") return } for { if tmp.Next == nil { break } tmp = tmp.Next } for { fmt.Printf("[%d, %s, %s]-->", tmp.No, tmp.Name, tmp.NickName) tmp = tmp.Pre if tmp.Pre == nil { // 判断是否到链表的 head 节点 break } } fmt.Println() } // 删除节点 func Del(head *HeroNode, no int) { tmp := head flag := false for { if tmp.Next == nil { break } else if tmp.Next.No == no { // 说明找到了要删除的节点 flag = true break } tmp = tmp.Next } if flag == false { fmt.Println("要删除的no不存在,no=", no) return } tmp.Next = tmp.Next.Next if tmp.Next != nil { // 判断删除的是否是最后一个节点 tmp.Next.Pre = tmp } } func main() { // 创建头节点 head := &HeroNode{} // 创建新的节点 hero1 := &HeroNode{ No: 1, Name: "宋江", NickName: "及时雨", } hero2 := &HeroNode{ No: 2, Name: "卢俊义", NickName: "玉麒麟", } hero3 := &HeroNode{ No: 3, Name: "林冲", NickName: "豹子头", } // 尾部添加节点 AddTail(head, hero1) AddTail(head, hero3) // 显示节点信息 List(head) // 逆序显示节点信息 ListReverse(head) // 中间插入节点 Insert(head, hero2) // 显示节点信息 List(head) // 逆序显示节点信息 ListReverse(head) // 删除节点 Del(head, 2) // 显示节点信息 List(head) }
运行结果:
[1, 宋江, 及时雨]-->[3, 林冲, 豹子头]--> 逆序显示节点信息: [3, 林冲, 豹子头]-->[1, 宋江, 及时雨]--> [1, 宋江, 及时雨]-->[2, 卢俊义, 玉麒麟]-->[3, 林冲, 豹子头]--> 逆序显示节点信息: [3, 林冲, 豹子头]-->[2, 卢俊义, 玉麒麟]-->[1, 宋江, 及时雨]--> [1, 宋江, 及时雨]-->[3, 林冲, 豹子头]-->
环形链表
环形链表,也叫循环链表是另一种形式的链式存贮结构。它的特点是表中最后一个结点的指针域指向头结点,整个链表形成一个环。
示意图:
代码实现:
package main import "fmt" type Person struct { Id int Name string Next *Person } // 插入 func Insert(head *Person, newPerson *Person) { // 判断是不是第一个人 if head.Next == nil { head.Id = newPerson.Id head.Name = newPerson.Name head.Next = head fmt.Println("加入环形链表成功") return } // 定义一个临时变量,帮助找到环形列表的最后节点 tmp := head for { if tmp.Next == head { break } tmp = tmp.Next } // 加入到链表中 tmp.Next = newPerson newPerson.Next = head } // 输出环形链表 func List(head *Person) { fmt.Println("环形链表详情:") tmp := head if tmp.Next == nil { fmt.Println("环形链表为空") return } for { fmt.Printf("[person id=%d, name=%s] -->", tmp.Id, tmp.Name) if tmp.Next == head { break } tmp = tmp.Next } fmt.Println() } // 删除链表节点, 这里需要返回haed节点,因为删除的可能就是head节点,导致head节点变化 func Del(head *Person, id int) *Person { tmp := head helper := head // 判断是否是空链表 if tmp.Next == nil { fmt.Println("要删除的链表为空") return head } // 如果只有一个节点 if tmp.Next == head { if tmp.Id == id { tmp.Next = nil } return head } // 将helper 定位到链表的最后 for { if helper.Next == head { break } helper = helper.Next } // 如果链表是两个及两个以上的节点 flag := true for { if tmp.Next == head { // 如果到这里,说明比较到了最后一个,但是最后一个还没有比较 break } else if tmp.Id == id { if tmp == head { // 说明删除的是head节点 head = head.Next } helper.Next = tmp.Next fmt.Println("删除节点id=", id) flag = false break } tmp = tmp.Next helper = helper.Next } // 这里还需要比较一次 if flag { if tmp.Id == id { helper.Next = tmp.Next fmt.Println("删除节点id=", id) } else { fmt.Println("未找到要删除的节点") } } return head } func main() { head := &Person{} p1 := &Person{ Id: 1, Name: "tom", } p2 := &Person{ Id: 2, Name: "gopher", } p3 := &Person{ Id: 3, Name: "jackey", } Insert(head, p1) Insert(head, p2) Insert(head, p3) List(head) head = Del(head, 1) List(head) }
一条评论
好高深的内容