数据结构与算法系列之链表操作全集(一)(GO)

用户头像
书旅
关注
发布于: 2020 年 10 月 22 日
数据结构与算法系列之链表操作全集(一)(GO)

前言

这里不介绍链表是什么之类的概念,大家可以找一找相关的书籍或文章看看,本文主要是用GO来实现一些链表的操作



说明:刚开始学习GO,可能用到的实现方法不是最简便的,意思表达出来了就可以,大家凑合着看【手动狗头】。如有错误,欢迎指正



以下的代码均可从这里获取

https://github.com/Rain-Life/learnGo



收获:做链表的题,一定!一定!一定!要画图!要画图!要画图!不然,特别容易乱,很难一遍写出0 error,0 warning的链表代码



链表



单链表的基本操作

链表通过指针将一组零散的内存块串联在一起,这里的内存块称为链表的结点。为了将这些节点给串起来,每个链表的结点除了存储数据之外,还会记录下一个结点的指针(即下一个结点的地址),这个指针称为:后继指针



定义单链表基本结构

定义链表结构
//定义结点中数据的类型为接口类型,可收任意类型数据
type Object interface {}
//定义结点的结构体
type Node struct {
Data Object
Next *Node
}
//定义链表的结构体
type List struct {
headNode *Node
}



判断链表是否为空
func (list *List) IsEmpty() bool {
if list.headNode == nil {
return true
}
return false
}



获取链表的长度
func (list *List) Length() int {
currentNode := list.headNode
count := 0
for currentNode != nil {
count++
currentNode = currentNode.Next
}
return count
}



添加结点



向链表头部添加结点
func (list *List) AddFromHead(data Object) *Node {
node := &Node{Data:data}
if list.IsEmpty() {
list.headNode = node
return node
}
node.Next = list.headNode
list.headNode = node
return node
}



向链表尾部添加结点
func (list *List) Append(data Object) {
node := &Node{Data: data}
if list.IsEmpty() {
list.headNode = node
} else {
currentNode := list.headNode
for currentNode.Next != nil {
currentNode = currentNode.Next
}
currentNode.Next = node
}
}



向链表中指定位置添加结点
func (list *List) Insert(position int, data Object) {
if position <= 1 {
list.AddFromHead(data)
} else if position > list.Length() {
list.Append(data)
} else {
pre := list.headNode
count := 1
for count < (position-1) {
pre = pre.Next
count++
}//循环退出以后pre刚好在position-1的位置
node := &Node{Data: data}
node.Next = pre.Next
pre.Next = node
}
}



删除结点



删除链表头部结点
func (list *List) RemoveHeadNde() Object {
if list.IsEmpty() {
fmt.Println("链表为空")
return nil
}
currentNode := list.headNode
if list.headNode.Next == nil {
list.headNode = nil
return currentNode.Data
}
list.headNode = currentNode.Next
return currentNode.Data
}



删除链表尾部结点
func (list *List) RemoveLastNode() Object {
if list.IsEmpty() {
return "链表为空"
}
currentNode := list.headNode
for currentNode.Next.Next != nil {
currentNode = currentNode.Next
}
data := currentNode.Next.Data
currentNode.Next = nil
return data
}



删除指定值的结点
func (list *List) Remove(data Object) {
pre := list.headNode
if pre.Data == data{
list.headNode = pre.Next
} else {
for pre.Next != nil {
if pre.Next.Data == data {
pre.Next = pre.Next.Next
} else {
pre = pre.Next
}
}
}
}



删除指定位置的结点
func (list *List) RemovePosition(position int) {
pre := list.headNode
if position <= 1 {
list.headNode = nil
} else if position > list.Length() {
fmt.Println("超出链表长度")
} else {
count :=1
for count != position-1 && pre.Next != nil {
count++
pre = pre.Next
}
pre.Next = pre.Next.Next
}
}



查找结点



链表中是否包含某个值的节点
func (list *List) Contain(data Object) bool {
currentNode := list.headNode
for currentNode != nil {
if currentNode.Data == data {
return true
}
currentNode = currentNode.Next
}
return false
}



遍历链表



遍历
func (list *List) Traverse() {
if list.IsEmpty() {
fmt.Println("链表为空")
}
currentNode := list.headNode
for currentNode != nil {
fmt.Printf("%v\t", currentNode.Data)
currentNode = currentNode.Next
}
}



测试

package main
import (
"fmt"
"learnGo/linkedList/node"
)
func print(list node.List) {
fmt.Printf("链表长度%d\n", list.Length())
fmt.Println("遍历链表所有结点:")
list.Traverse()
fmt.Println()
fmt.Println()
}
func main() {
list := node.List{}
//向链表的尾部追加元素
fmt.Println("++++++++1、向链表尾部追加结点++++++++")
list.Append(3)
list.Append(8)
list.Append(1)
list.Append(9)
list.Append("PHP")
list.Append("Golang")
list.Append("Java")
list.Append("JavaScript")
print(list)
fmt.Println("++++++++2、判断链表是否为空++++++++")
fmt.Printf("链表是否为空:%v", list.IsEmpty())
fmt.Println()
fmt.Println()
//向链表的头部添加元素
fmt.Println("++++++++3、向链表的头部添加一个结点++++++++")
fmt.Println()
list.AddFromHead("firstNode")
print(list)
fmt.Println("++++++++4、向链表尾部添加结点++++++++")
fmt.Println()
list.Append("lastNode")
print(list)
fmt.Println("++++++++5、向链表尾部添加结点++++++++")
fmt.Println()
list.Insert(3, "thirdNode")
print(list)
fmt.Println("++++++++6、删除链表头结点++++++++")
fmt.Println()
list.RemoveHeadNde()
print(list)
fmt.Println("++++++++7、删除链表尾结点++++++++")
fmt.Println()
list.RemoveLastNode()
print(list)
fmt.Println("++++++++8、删除链表中指定值的结点++++++++")
fmt.Println()
list.Remove(9)
print(list)
fmt.Println("++++++++9、删除链表中指定位置的结点++++++++")
fmt.Println()
list.RemovePosition(3)
print(list)
fmt.Println("++++++++10、查询链表中是否包含某一个结点++++++++")
fmt.Println()
res := list.Contain("Golang")
fmt.Printf("是否存在Golang结点:%v\n", res)
print(list)
}



实现各种类型的链表

各种链表简介

循环链表

循环链表是一种特殊的单链表。循环跟单链表唯一的区别就在尾结点。单链表的尾结点指针指向空地址,表示这就是最后的结点了。而循环链表的尾结点指针是指向链表的头结点



循环链表的优点就是,从链尾到链头比较方便。当要处理的数据具有环型结构特点时,就特别适合采用循环链表



双向链表



和单向链表相比,双向链表有两个指针,指向前一个结点的指针是前驱指针(prev),指向后一个结点的是后继指针(next)



有了前驱指针,可以更加方便的获取当前结点的前一个结点。按照单链表的方式,我们如果要获取前驱结点,要么遍历的时候用一个变量来保存前驱结点,要么再次遍历获取前驱结点。而双向链表可以在O(1)复杂度下找到前驱结点



单向链表和双向链表对比



  • 如果存储同样多的数据,双向链表要比单链表占用更多的内存空间。虽然两个指针比较浪费存储空间,但可以支持双向遍历,这样也带来了双向链表操作的灵活性



  • 双向链表的插入和删除操作更高效,因为可以很容易获取到前驱结点



  • 如果有一个有序的链表,双向链表的按值查询的效率也要比单链表高一些。因为,我们可以记录上次查找的位置 p,每次查询时,根据要查找的值与 p 的大小关系,决定是往前还是往后查找,所以平均只需要查找一半的数据



双向链表尽管比较费内存,但还是比单链表的应用更加广泛的原因是空间换时间的思想

> 当内存空间充足的时候,如果我们更加追求代码的执行速度,我们就可以选择空间复杂度相对较高、但时间复杂度相对很低的算法或者数据结构。相反,如果内存比较紧缺,比如代码跑在手机或者单片机上,这个时候,就要反过来用时间换空间的设计思路

>

> 来源:数据结构与算法之美



双向循环链表



将循环链表和双向链表结合,得到的就是:双向循环链表



各种类型的链表操作

这部分直接上代码了



循环链表

这里直接放完整的各种操作的代码,重点地方会加上说明



loopLinkedList.go

package loopLinkList
import "fmt"
//循环链表
type Object interface {}
type Node struct {
Data Object
Next *Node
}
type List struct {
headNode *Node
}
//判断循环链表是否为空(与单链表的实现没有区别)
func (list *List) IsEmpty() bool {
if list.headNode == nil {
return true
}
return false
}
//获取循环链表的长度(与单链表的获取长度区别在于循环的终止条件)
func (list *List) Length() int {
if list.headNode == nil {
return 0
}
currentNode := list.headNode
count := 1
for currentNode.Next != list.headNode {
count++
currentNode = currentNode.Next
}
return count
}
//向循环链头部添加结点
func (list *List) AddFromHead(data Object) {
node := &Node{Data: data}
//链表为空的情况
if list.IsEmpty() {
list.headNode = node
list.headNode.Next = list.headNode //单链表没有这一步
} else {
currentNode := list.headNode
for currentNode.Next != list.headNode { //需要先找到最后一个结点
currentNode = currentNode.Next
}
node.Next = list.headNode
currentNode.Next = node //单链表没有这一步操作,将最后一个节点的next指向头结点
list.headNode = node
}
}
//向循环链表的尾部添加结点
func (list *List) Append(data Object) {
node := &Node{Data: data}
if list.IsEmpty() {
list.headNode = node
list.headNode.Next = node
} else {
currentNode := list.headNode
for currentNode.Next != list.headNode {
currentNode = currentNode.Next
}
currentNode.Next = node
node.Next = list.headNode //单链表没有这一步操作(让最后一个节点指向头结点)
}
}
//向循环链表的指定位置添加结点(跟单链表是一样的)
func (list *List) Insert(position int, data Object) {
if position <= 1 {
list.AddFromHead(data)
} else if position > list.Length() {
list.Append(data)
} else {
currentNode := list.headNode
count := 1
for count < position-1 {
currentNode = currentNode.Next
count++
}
node := &Node{Data: data}
node.Next = currentNode.Next
currentNode.Next = node
}
}
//删除循环链表的头结点
func (list *List) RemoveHeadNde() {
if list.IsEmpty() {
fmt.Println("链表是空的")
return
}
currentNode := list.headNode
lastNode := list.headNode
//考虑循环链表只有一个结点的情况
if currentNode.Next == list.headNode {
list.headNode = nil
return
}
for lastNode.Next != list.headNode {
lastNode = lastNode.Next
}
list.headNode = currentNode.Next
lastNode.Next = list.headNode
}
//删除循环链表的尾结点
func (list *List) RemoveLastNode() {
if list.IsEmpty() {
fmt.Println("链表是空的")
return
}
currentNode := list.headNode
//考虑循环链表只有一个结点的情况
if currentNode.Next == list.headNode {
list.headNode = nil
return
}
for currentNode.Next.Next != list.headNode {
currentNode = currentNode.Next
}
currentNode.Next = list.headNode
}
//删除循环链表中指定位置的节点 (需考虑删除的结点是不是第一个或最后一个)
func (list *List) RemovePosition(position int) {
if list.IsEmpty() {
fmt.Println("链表为空")
return
}
if position <= 1 {
list.RemoveHeadNde()
} else if position > list.Length() {
list.RemoveLastNode()
} else {
currentNode := list.headNode
count := 1
if count != position-1 && currentNode.Next != list.headNode{
count++
currentNode = currentNode.Next
}
currentNode.Next = currentNode.Next.Next
}
}
//删除循环链表中指定值的结点
func (list *List) Remove(data Object) {
if list.IsEmpty() {
fmt.Println("链表为空")
return
}
currentNode := list.headNode
//删除的结点为头结点时
if currentNode.Data == data {
list.RemoveHeadNde()
return
}
for currentNode.Next != list.headNode {
if currentNode.Next.Data == data {
currentNode.Next = currentNode.Next.Next
return
} else {
currentNode = currentNode.Next
}
}
if currentNode.Next == list.headNode {
list.RemoveLastNode()
}
}
//查找循环链表中指定结点
func (list *List) Contain(data Object) bool {
if list.IsEmpty() {
return false
}
currentNode := list.headNode
for currentNode.Next != list.headNode {
if currentNode.Data == data {
return true
}
currentNode = currentNode.Next
}
if currentNode.Data == data {
return true
}
return false
}
//遍历循环链表
func (list *List) Traverse() {
if list.IsEmpty() {
fmt.Println("循环链表为空")
return
}
currentNode := list.headNode
if currentNode.Next == list.headNode { //兼容循环链表只有一个结点的情况
fmt.Printf("%v\t", currentNode.Data)
return
}
for currentNode.Next != list.headNode {
fmt.Printf("%v\t", currentNode.Data)
currentNode = currentNode.Next
}
fmt.Printf("%v\t", currentNode.Data)
}



entry.go(测试)

package main
import (
"fmt"
"learnGo/linkedList/loopLinkList"
)
func print(list loopLinkList.List) {
fmt.Printf("链表长度:%d\n", list.Length())
fmt.Println("遍历链表所有结点:")
list.Traverse()
fmt.Println()
fmt.Println()
}
func main() {
list := loopLinkList.List{}
fmt.Println("++++++++1、判断链表是否为空++++++++")
fmt.Printf("链表是否为空:%v\n", list.IsEmpty())
print(list)
fmt.Println("++++++++2、获取链表长度++++++++")
fmt.Printf("获取链表长度:%d\n", list.Length())
print(list)
fmt.Println("++++++++3、向循环链头部添加结点++++++++")
list.AddFromHead("firstNode")
print(list)
fmt.Println("++++++++4、向循环链尾部添加结点++++++++")
list.Append("lastNode")
print(list)
fmt.Println("++++++++5、向循环链指定位置添加结点++++++++")
list.Insert(1,"secondNode")
print(list)
fmt.Println("++++++++6、删除循环链的头结点++++++++")
list.RemoveHeadNde()
print(list)
fmt.Println("++++++++7、删除循环链的尾结点++++++++")
list.RemoveLastNode()
print(list)
fmt.Println("++++++++8、查找循环链表中指定结点++++++++")
fmt.Printf("是否包含secondNode节点:%v\n", list.Contain("secondNode"))
print(list)
fmt.Println("++++++++9、删除循环链表中指定位置的结点++++++++")
list.RemovePosition(1)
print(list)
fmt.Println("++++++++10、删除循环链表中指定值的结点++++++++")
list.Remove("lastNode")
print(list)
}



双向链表

doublyLinkedList.go

package doublyLinkedList
import (
"fmt"
)
//双向链表
type Object interface {}
type Node struct {
Data Object
Prev,Next *Node
}
type List struct {
headNode *Node
}
//说明
/**
1、如果结点的Next指向为null,则说明是最后一个结点
2、第一个结点的prev指向为空
3、双向链表和单向链表差不多,区别就是删除和添加结点的时候更方便了,因为很方便的可以获取到前一个结点
*/
//判断双向链表是否为空
func (list *List) IsEmpty() bool {
if list.headNode == nil {
return true
}
return false
}
//遍历双向链表(跟遍历单链表一模一样)
func (list *List) Traverse() {
if list.IsEmpty() {
fmt.Println("双线链表为空")
return
}
currentNode := list.headNode
for currentNode != nil {
fmt.Printf("%v\t", currentNode.Data)
currentNode = currentNode.Next
}
}
//获取双向链表的长度(跟获取单链表长度一模一样)
func (list *List) Length() int {
if list.IsEmpty() {
return 0
}
count := 0
currentNode := list.headNode
for currentNode != nil {
count++
currentNode = currentNode.Next
}
return count
}
//从双向链表头部开始增加结点
func (list *List) AddFromHead(data Object) *Node {
node := &Node{Data: data}
if list.IsEmpty() {
list.headNode = node
return node
}
list.headNode.Prev = node
node.Next = list.headNode
list.headNode = node
return node
}
//从双向链表尾部添加结点
func (list *List) Append(data Object) {
node := &Node{Data: data}
if list.IsEmpty() {
list.headNode = node
} else {
currentNode := list.headNode
for currentNode.Next != nil {
currentNode = currentNode.Next
}
currentNode.Next = node
node.Prev = currentNode
}
}
/**
* 向双向链表的指定位置插入结点
*
* 说明:在单向链表中,我是通过找到我要插入的这个结点的前一个结点,然后将要插入的结点,
* 插入到这个结点的后边(因为插入结点需要找到当前结点的前一个结点,为了避免再次遍历找前一个结点,所以采用了这种方式)
* 而双向链表就不需要这么做了,找到指定位置的结点,新的插入到它前边就可以了
*/
func (list *List) Insert(position int, data Object) {
if position <= 1 {
list.AddFromHead(data)
} else if position > list.Length() {
list.Append(data)
} else {
currentNode := list.headNode
count := 1
for count != position {
currentNode = currentNode.Next
count++
}
//找到了指定位置的结点,然后将要插入的结点,插到这个节点前边即可(注意顺序,画图最容易理解)
node := &Node{Data: data}
node.Next = currentNode
node.Prev = currentNode.Prev
currentNode.Prev.Next = node
currentNode.Prev = node
}
}
//删除链表头结点
func (list *List) RemoveHeadNde() Object {
if list.IsEmpty() {
fmt.Println("链表为空")
return nil
}
currentNode := list.headNode
if currentNode.Next == nil && currentNode.Prev == nil {
list.headNode = nil
return currentNode.Data
}
list.headNode = currentNode.Next
currentNode.Prev = nil
return currentNode.Data
}
//删除链表尾结点
func (list *List) RemoveLastNode() Object {
if list.IsEmpty() {
fmt.Println("链表为空")
return nil
}
if list.headNode.Next == nil {
list.headNode = nil
}
currentNode := list.headNode
for currentNode.Next != nil {
currentNode = currentNode.Next
}
currentNode.Prev.Next = nil
return currentNode.Prev.Data
}
//删除双向表中指定值的结点
func (list *List) Remove(data Object) {
if list.IsEmpty() {
fmt.Println("链表为空")
return
}
currentNode := list.headNode
if list.headNode.Next == nil && list.headNode.Data == data {
list.headNode = nil
}
fmt.Println(data, currentNode.Data, currentNode.Data == data)
for currentNode != nil {
if currentNode.Data == data && currentNode == list.headNode {
list.headNode = currentNode.Next
} else if currentNode.Data == data && currentNode.Prev != nil {
currentNode.Prev.Next = currentNode.Next
currentNode.Next.Prev = currentNode.Prev
} else {
currentNode = currentNode.Next
}
}
}
//删除双向链表中指定位置的结点
func (list *List) RemovePosition(position int) {
if list.IsEmpty() {
fmt.Println("链表为空")
return
}
if position <=1 {
list.RemoveHeadNde()
} else if position > list.Length() {
list.RemoveLastNode()
} else {
currentNode := list.headNode
count := 1
for count != position {
count++
currentNode = currentNode.Next
}
currentNode.Prev.Next = currentNode.Next
currentNode.Next.Prev = currentNode.Prev
}
}
//查询双向链表中是否包含某一个结点(和单向链表一样)
func (list *List) Contain(data Object) bool {
if list.IsEmpty() {
fmt.Println("链表为空")
return false
}
currentNode := list.headNode
for currentNode != nil {
if currentNode.Data == data {
return true
}
currentNode = currentNode.Next
}
return false
}



entry.go(测试)

package main
import (
"fmt"
"learnGo/linkedList/doublyLinkedList"
)
func print(list doublyLinkedList.List) {
fmt.Printf("链表长度%d\n", list.Length())
fmt.Println("遍历链表所有结点:")
list.Traverse()
fmt.Println()
fmt.Println()
}
func main() {
list := doublyLinkedList.List{}
fmt.Println("++++++++1、判断链表是否为空++++++++")
fmt.Printf("链表是否为空:%v", list.IsEmpty())
fmt.Println()
fmt.Println()