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

 关注
发布于: 2020 年 10 月 22 日
前言这里不介绍链表是什么之类的概念，大家可以找一找相关的书籍或文章看看，本文主要是用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()
	fmt.Println("++++++++2、向双向链表头部添加元素++++++++")
	fmt.Println()
	list.AddFromHead(1)
	list.AddFromHead(2)
	list.AddFromHead(3)
	print(list)
	fmt.Println("++++++++3、向双向链表尾部添加元素++++++++")
	fmt.Println()
	list.Append("Golang")
	list.Append("PHP")
	list.Append("Java")
	print(list)
	fmt.Println("++++++++4、向双向链表的指定位置插入结点++++++++")
	fmt.Println("++++++++(1)向双向链表的【第一个】位置插入结点++++++++")
	list.Insert(1, "First")
	print(list)
	fmt.Println("++++++++(2)向双向链表的【第三个】位置插入结点++++++++")
	list.Insert(3, "Third")
	print(list)
	fmt.Println("++++++++(3)向双向链表的【最后】位置插入结点++++++++")
	list.Insert(list.Length()+1, "Last")
	print(list)
	fmt.Println("++++++++5、删除双向链表的头结点++++++++")
	fmt.Println()
	list.RemoveHeadNde()
	print(list)
	fmt.Println("++++++++6、删除双向链表的尾结点++++++++")
	fmt.Println()
	list.RemoveLastNode()
	print(list)
	fmt.Println("++++++++7、删除双向表中指定值的结点++++++++")
	list.Remove(3)//这里的类型要和你插入时的类型一致（弱类型语言写习惯了，很容易忘了）
	print(list)
	fmt.Println("++++++++8、删除双向表中指定位置的结点++++++++")
	fmt.Println("++++++++(1)删除双向链表的【第一个】位置结点++++++++")
	list.RemovePosition(1)
	print(list)
	fmt.Println("++++++++(2)删除双向链表的【第三个】位置结点++++++++")
	list.RemovePosition(3)
	print(list)
	fmt.Println("++++++++(3)删除双向链表的【最后】位置结点++++++++")
	list.RemovePosition(list.Length())
	print(list)
	fmt.Println("++++++++9、查询双向链表中是否包含某一个结点++++++++")
	fmt.Println()
	fmt.Printf("是否存在Golang结点：%v\n", list.Contain(2))
}
﻿
双向循环链表doublyLoopLinkedList.go
package doublyLoopLinkedList
import (
	"fmt"
)
type Object interface {}
type Node struct {
	Data Object
	Prev,Next *Node
}
type List struct {
	headNode *Node
}
//判断双向循环链表是否为空
func (list *List) IsEmpty() bool {
	if list.headNode == nil {
		return true
	}
	return false
}
//遍历双向循环链表
func (list *List) Traverse() {
	if list.IsEmpty() {
		fmt.Println("链表为空")
		return
	}
	if list.headNode.Next == nil {//兼容双向循环链表只有一个结点的情况
		fmt.Printf("%v\t", list.headNode.Data)
		return
	}
	currentNode := list.headNode
	for currentNode.Next != list.headNode {
		fmt.Printf("%v\t", currentNode.Data)
		currentNode = currentNode.Next
	}
	fmt.Printf("%v\t", currentNode.Data)
}
//获取双向循环链表的长度
func (list *List) Length() int {
	if list.IsEmpty() {
		return 0
	}
	count := 1
	currentNode := list.headNode
	for currentNode.Next != list.headNode {
		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
	}
	currentNode := list.headNode
	if currentNode.Next == nil { //考虑只有一个节点的时候
		node.Prev = currentNode
		currentNode.Next = node
		node.Next = currentNode
		currentNode.Prev = node
		list.headNode = node
		return node
	}
	node.Prev = currentNode.Prev
	currentNode.Prev.Next = node
	currentNode.Prev = node
	node.Next = currentNode
	list.headNode = node
	return node
}
//从双向循环链表尾部添加结点
func (list *List) Append(data Object) *Node {
	node := &Node{Data: data}
	if list.IsEmpty() {
		list.headNode = node
		return node
	}
	currentNode := list.headNode
	currentNode.Prev.Next = node
	node.Prev = currentNode.Prev
	currentNode.Prev = node
	node.Next = currentNode
	return node
}
//向双向循环链表的指定位置插入结点
func (list *List) Insert(position int, data Object) {
	if position <=1 {
		list.AddFromHead(data)
	} else if position > list.Length() {
		list.Append(data)
	} else {
		node := &Node{Data: data}
		currentNode := list.headNode
		count := 1
		for count != position {
			count++
			currentNode = currentNode.Next
		}
		//将待插入的节点插入到当前节点的前边即可(这块的逻辑其实和双向链表的在中间位子插入结点逻辑一样)
		currentNode.Prev.Next = node
		node.Prev = currentNode.Prev
		currentNode.Prev = node
		node.Next = currentNode
	}
}
//删除双向循环链表头结点
func (list *List) RemoveHeadNde() Object {
	if list.IsEmpty() {
		fmt.Println("双向循环链表为空")
		return ""
	}
	currentNode := list.headNode
	if currentNode.Next == nil {//只有一个结点的情况
		list.headNode = nil
		return currentNode.Data
	}
	currentNode.Prev.Next = currentNode.Next
	currentNode.Next.Prev = currentNode.Prev
	list.headNode = currentNode.Next
	return currentNode.Data
}
//删除双向循环链表尾结点
func (list *List) RemoveLastNode() Object {
	if list.IsEmpty() {
		fmt.Println("双向循环链表为空")
		return ""
	}
	currentNode := list.headNode
	if currentNode.Next == nil {//只有一个结点的情况
		list.headNode = nil
		return list.headNode.Data
	}
	lastNode := list.headNode.Prev
	lastNode.Prev.Next = currentNode
	currentNode.Prev = lastNode.Prev
	return lastNode.Data
}
//删除双向循环链表中指定值的结点
func (list *List) Remove(data Object) bool {
	if list.IsEmpty() {
		fmt.Println("双向循环链表为空")
		return false
	}
	//如果链表只有一个节点
	if list.headNode.Next == nil {
		if list.headNode.Data == data {
			list.headNode = nil
			return true
		}
		return false
	}
	currentNode := list.headNode
	//如果值刚好等于第一个节点的值
	if currentNode.Data == data {
		list.RemoveHeadNde()
		return true
	}
	//如果值刚好等于最后一个结点的值
	for currentNode.Next != list.headNode {
		if currentNode.Data == data {
			//删除中间节点
			currentNode.Prev.Next = currentNode.Next
			currentNode.Next.Prev = currentNode.Prev
			return true
		} else {
			currentNode = currentNode.Next
		}
	}
	if currentNode.Data == data { //刚好是最后一个结点的时候
		list.RemoveLastNode()
		return true
	}
	return false
}
//删除双向循环链表中指定位置的结点
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.Next != list.headNode {
		if currentNode.Data == data {
			return true
		}
		currentNode = currentNode.Next
	}
	if currentNode.Data == data {
		return true
	}
	return false
}
﻿
entry.go
package main
import (
	"fmt"
	"learnGo/linkedList/doublyLoopLinkedList"
)
func print(list doublyLoopLinkedList.List)  {
	fmt.Printf("链表长度%d\n", list.Length())
	fmt.Println("遍历链表所有结点：")
	list.Traverse()
	fmt.Println()
	fmt.Println()
}
func main() {
	list := doublyLoopLinkedList.List{}
	fmt.Println("++++++++1、判断链表是否为空++++++++")
	fmt.Printf("链表是否为空：%v", list.IsEmpty())
	fmt.Println()
	fmt.Println()
	fmt.Println("++++++++2、向双向循环链表头部添加结点++++++++")
	fmt.Println()
	list.AddFromHead(1)
	list.AddFromHead(2)
	list.AddFromHead(3)
	print(list)
	fmt.Println("++++++++3、向双向循环链表尾部添加结点++++++++")
	fmt.Println()
	list.Append("lastNode")
	print(list)
	fmt.Println("++++++++4、向双向循环链表指定位置添加结点++++++++")
	fmt.Println()
	list.Insert(1,"firstNode")
	print(list)
	fmt.Println("++++++++5、删除双向循环链表头结点++++++++")
	fmt.Println()
	list.RemoveHeadNde()
	print(list)
	fmt.Println("++++++++6、删除双向循环链表尾结点++++++++")
	fmt.Println()
	list.RemoveLastNode()
	print(list)
	fmt.Println("++++++++7、删除双向循环链表中指定值的结点++++++++")
	fmt.Println()
	list.Remove(1)
	print(list)
	fmt.Println("++++++++8、删除双向循环链表中指定位置的结点++++++++")
	fmt.Println()
	list.RemovePosition(list.Length()-1)
	print(list)
	fmt.Println("++++++++9、查询双向循环链表中是否包含某一个结点++++++++")
	fmt.Println()
	fmt.Println("是否包含值为firstNode的结点：", list.Contain("firstNode"))
	print(list)
}
﻿
﻿
参考：
《数据结构与算法之美》
﻿