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

### 前言

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

## 链表

### 单链表的基本操作

##### 定义单链表基本结构
###### 定义链表结构
``````//定义结点中数据的类型为接口类型，可收任意类型数据
type Object interface {}

//定义结点的结构体
type Node struct {
Data Object
Next *Node
}

//定义链表的结构体
type List struct {
}``````
###### 判断链表是否为空
``````func (list *List) IsEmpty() bool  {
return true
}

return false
}``````
###### 获取链表的长度
``````func (list *List) Length() int {
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() {
return node
}

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

currentNode.Next = node
}
}``````
###### 向链表中指定位置添加结点
``````func (list *List) Insert(position int, data Object) {
if position <= 1 {
} else if position > list.Length() {
list.Append(data)
} else {
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
}

return currentNode.Data
}

return currentNode.Data
}``````
###### 删除链表尾部结点
``````func (list *List) RemoveLastNode() Object {
if list.IsEmpty() {
return "链表为空"
}

for currentNode.Next.Next != nil {
currentNode = currentNode.Next
}

data := currentNode.Next.Data
currentNode.Next = nil
return data
}``````
###### 删除指定值的结点
``````func (list *List) Remove(data Object)  {
if pre.Data == data{
} 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)  {
if position <= 1 {
} 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 {
for currentNode != nil {
if currentNode.Data == data {
return true
}
currentNode = currentNode.Next
}

return false
}``````
##### 遍历链表
###### 遍历
``````func (list *List) Traverse()  {
if list.IsEmpty() {
fmt.Println("链表为空")
}
for currentNode != nil {
fmt.Printf("%v\t", currentNode.Data)
currentNode = currentNode.Next
}
}``````
##### 测试
``````package main

import (
"fmt"
)

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()
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()
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)
}``````

### 实现各种类型的链表

##### 各种链表简介

###### 双向链表

• 如果存储同样多的数据，双向链表要比单链表占用更多的内存空间。虽然两个指针比较浪费存储空间，但可以支持双向遍历，这样也带来了双向链表操作的灵活性
• 双向链表的插入和删除操作更高效，因为可以很容易获取到前驱结点
• 如果有一个有序的链表，双向链表的按值查询的效率也要比单链表高一些。因为，我们可以记录上次查找的位置 p，每次查询时，根据要查找的值与 p 的大小关系，决定是往前还是往后查找，所以平均只需要查找一半的数据

##### 各种类型的链表操作

###### 循环链表

``````package loopLinkList

import "fmt"

//循环链表
type Object interface {}

type Node struct {
Data Object
Next *Node
}

type List struct {
}

//判断循环链表是否为空（与单链表的实现没有区别）
func (list *List) IsEmpty() bool {
return true
}

return false
}

//获取循环链表的长度（与单链表的获取长度区别在于循环的终止条件）
func (list *List) Length() int {
return 0
}

count := 1
count++
currentNode = currentNode.Next
}

return count
}

//向循环链头部添加结点
node := &Node{Data: data}
//链表为空的情况
if list.IsEmpty() {
} else {
for currentNode.Next != list.headNode { //需要先找到最后一个结点
currentNode = currentNode.Next
}

currentNode.Next = node //单链表没有这一步操作，将最后一个节点的next指向头结点
}
}

//向循环链表的尾部添加结点
func (list *List) Append(data Object) {
node := &Node{Data: data}

if list.IsEmpty() {
} else {
currentNode = currentNode.Next
}

currentNode.Next = node
}
}

//向循环链表的指定位置添加结点（跟单链表是一样的）
func (list *List) Insert(position int, data Object) {
if position <= 1 {
} else if position > list.Length() {
list.Append(data)
} else {
count := 1
for count < position-1 {
currentNode = currentNode.Next
count++
}

node := &Node{Data: data}
node.Next = currentNode.Next
currentNode.Next = node
}
}

//删除循环链表的头结点
if list.IsEmpty() {
fmt.Println("链表是空的")
return
}

//考虑循环链表只有一个结点的情况
return
}

lastNode = lastNode.Next
}

}

//删除循环链表的尾结点
func (list *List) RemoveLastNode() {
if list.IsEmpty() {
fmt.Println("链表是空的")
return
}

//考虑循环链表只有一个结点的情况
return
}

currentNode = currentNode.Next
}

}

//删除循环链表中指定位置的节点 (需考虑删除的结点是不是第一个或最后一个)
func (list *List) RemovePosition(position int) {
if list.IsEmpty() {
fmt.Println("链表为空")
return
}

if position <= 1 {
} else if position > list.Length() {
list.RemoveLastNode()
} else {
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
}

//删除的结点为头结点时
if currentNode.Data == data {
return
}

if currentNode.Next.Data == data {
currentNode.Next = currentNode.Next.Next
return
} else {
currentNode = currentNode.Next
}
}

list.RemoveLastNode()
}
}

//查找循环链表中指定结点
func (list *List) Contain(data Object) bool {
if list.IsEmpty() {
return false
}

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
}

if currentNode.Next == list.headNode { //兼容循环链表只有一个结点的情况
fmt.Printf("%v\t", currentNode.Data)
return
}

fmt.Printf("%v\t", currentNode.Data)
currentNode = currentNode.Next
}
fmt.Printf("%v\t", currentNode.Data)
}
``````

entry.go（测试）

``````package main

import (
"fmt"
)

fmt.Printf("链表长度：%d\n", list.Length())
fmt.Println("遍历链表所有结点：")
list.Traverse()
fmt.Println()
fmt.Println()
}

func main() {

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、向循环链头部添加结点++++++++")
print(list)

fmt.Println("++++++++4、向循环链尾部添加结点++++++++")
list.Append("lastNode")
print(list)

fmt.Println("++++++++5、向循环链指定位置添加结点++++++++")
list.Insert(1,"secondNode")
print(list)

fmt.Println("++++++++6、删除循环链的头结点++++++++")
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)

}
``````
###### 双向链表

``````package doublyLinkedList

import (
"fmt"
)

//双向链表
type Object interface {}

type Node struct {
Data Object
Prev,Next *Node
}

type List struct {
}

//说明
/**
1、如果结点的Next指向为null，则说明是最后一个结点
2、第一个结点的prev指向为空
3、双向链表和单向链表差不多，区别就是删除和添加结点的时候更方便了，因为很方便的可以获取到前一个结点
*/

//判断双向链表是否为空
func (list *List) IsEmpty() bool {
return true
}

return false
}

//遍历双向链表（跟遍历单链表一模一样）
func (list *List) Traverse() {
if list.IsEmpty() {
fmt.Println("双线链表为空")
return
}

for currentNode != nil {
fmt.Printf("%v\t", currentNode.Data)
currentNode = currentNode.Next
}
}

//获取双向链表的长度（跟获取单链表长度一模一样）
func (list *List) Length() int {
if list.IsEmpty() {
return 0
}

count := 0
for currentNode != nil {
count++
currentNode = currentNode.Next
}

return count
}

//从双向链表头部开始增加结点
node := &Node{Data: data}
if list.IsEmpty() {
return node
}

return node
}

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

currentNode.Next = node
node.Prev = currentNode
}
}

/**
* 向双向链表的指定位置插入结点
*
* 说明：在单向链表中，我是通过找到我要插入的这个结点的前一个结点，然后将要插入的结点，
* 插入到这个结点的后边（因为插入结点需要找到当前结点的前一个结点，为了避免再次遍历找前一个结点，所以采用了这种方式）
* 而双向链表就不需要这么做了，找到指定位置的结点，新的插入到它前边就可以了
*/
func (list *List) Insert(position int, data Object) {
if position <= 1 {
} else if position > list.Length() {
list.Append(data)
} else {
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
}

if currentNode.Next == nil && currentNode.Prev == nil {
return currentNode.Data
}

currentNode.Prev = nil

return currentNode.Data
}

//删除链表尾结点
func (list *List) RemoveLastNode() Object {
if list.IsEmpty() {
fmt.Println("链表为空")
return nil
}

}

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
}

}

fmt.Println(data, currentNode.Data, currentNode.Data == data)
for currentNode != nil {
if currentNode.Data == data && currentNode == list.headNode {
} 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 {
} else if position > list.Length() {
list.RemoveLastNode()
} else {
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
}

for currentNode != nil {
if currentNode.Data == data {
return true
}

currentNode = currentNode.Next
}

return false
}
``````

entry.go（测试）

``````package main

import (
"fmt"
)

fmt.Printf("链表长度%d\n", list.Length())
fmt.Println("遍历链表所有结点：")
list.Traverse()
fmt.Println()
fmt.Println()
}

func main() {

fmt.Println("++++++++1、判断链表是否为空++++++++")
fmt.Printf("链表是否为空：%v", list.IsEmpty())
fmt.Println()
fmt.Println()

fmt.Println("++++++++2、向双向链表头部添加元素++++++++")
fmt.Println()
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()
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))
}``````
###### 双向循环链表

``````package doublyLoopLinkedList

import (
"fmt"
)

type Object interface {}

type Node struct {
Data Object
Prev,Next *Node
}

type List struct {
}

//判断双向循环链表是否为空
func (list *List) IsEmpty() bool {
return true
}

return false
}

//遍历双向循环链表
func (list *List) Traverse() {
if list.IsEmpty() {
fmt.Println("链表为空")
return
}

return
}

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
count++
currentNode = currentNode.Next
}

return count
}

//从双向循环链表头部添加结点(一定一定要画图，比较好理解)
node := &Node{Data: data}
if list.IsEmpty() {
return node
}

if currentNode.Next == nil { //考虑只有一个节点的时候
node.Prev = currentNode
currentNode.Next = node
node.Next = currentNode
currentNode.Prev = node
return node
}

node.Prev = currentNode.Prev
currentNode.Prev.Next = node
currentNode.Prev = node
node.Next = currentNode

return node
}

//从双向循环链表尾部添加结点
func (list *List) Append(data Object) *Node {
node := &Node{Data: data}
if list.IsEmpty() {
return node
}

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 {
} else if position > list.Length() {
list.Append(data)
} else {
node := &Node{Data: data}
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 ""
}

if currentNode.Next == nil {//只有一个结点的情况
return currentNode.Data
}

currentNode.Prev.Next = currentNode.Next
currentNode.Next.Prev = currentNode.Prev

return currentNode.Data
}

//删除双向循环链表尾结点
func (list *List) RemoveLastNode() Object {
if list.IsEmpty() {
fmt.Println("双向循环链表为空")
return ""
}

if currentNode.Next == nil {//只有一个结点的情况
}

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
}

//如果链表只有一个节点
return true
}
return false
}

//如果值刚好等于第一个节点的值
if currentNode.Data == data {
return true
}

//如果值刚好等于最后一个结点的值
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 {
} else if position > list.Length() {
list.RemoveLastNode()
} else {
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
}

if currentNode.Data == data {
return true
}

currentNode = currentNode.Next
}

if currentNode.Data == data {
return true
}

return false
}
``````

entry.go

``````package main

import (
"fmt"
)

fmt.Printf("链表长度%d\n", list.Length())
fmt.Println("遍历链表所有结点：")
list.Traverse()
fmt.Println()
fmt.Println()
}

func main() {

fmt.Println("++++++++1、判断链表是否为空++++++++")
fmt.Printf("链表是否为空：%v", list.IsEmpty())
fmt.Println()
fmt.Println()

fmt.Println("++++++++2、向双向循环链表头部添加结点++++++++")
fmt.Println()
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()
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)
}``````

《数据结构与算法之美》

0 回复

• 请尽量让自己的回复能够对别人有帮助
• 支持 Markdown 格式, **粗体**、~~删除线~~、``单行代码``
• 支持 @ 本站用户；支持表情（输入 : 提示），见 Emoji cheat sheet
• 图片支持拖拽、截图粘贴等方式上传

### 前言

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

## 链表

### 单链表的基本操作

##### 定义单链表基本结构
###### 定义链表结构
``````//定义结点中数据的类型为接口类型，可收任意类型数据
type Object interface {}

//定义结点的结构体
type Node struct {
Data Object
Next *Node
}

//定义链表的结构体
type List struct {
}``````
###### 判断链表是否为空
``````func (list *List) IsEmpty() bool  {
return true
}

return false
}``````
###### 获取链表的长度
``````func (list *List) Length() int {
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() {
return node
}

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

currentNode.Next = node
}
}``````
###### 向链表中指定位置添加结点
``````func (list *List) Insert(position int, data Object) {
if position <= 1 {
} else if position > list.Length() {
list.Append(data)
} else {
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
}

return currentNode.Data
}

return currentNode.Data
}``````
###### 删除链表尾部结点
``````func (list *List) RemoveLastNode() Object {
if list.IsEmpty() {
return "链表为空"
}

for currentNode.Next.Next != nil {
currentNode = currentNode.Next
}

data := currentNode.Next.Data
currentNode.Next = nil
return data
}``````
###### 删除指定值的结点
``````func (list *List) Remove(data Object)  {
if pre.Data == data{
} 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)  {
if position <= 1 {
} 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 {
for currentNode != nil {
if currentNode.Data == data {
return true
}
currentNode = currentNode.Next
}

return false
}``````
##### 遍历链表
###### 遍历
``````func (list *List) Traverse()  {
if list.IsEmpty() {
fmt.Println("链表为空")
}
for currentNode != nil {
fmt.Printf("%v\t", currentNode.Data)
currentNode = currentNode.Next
}
}``````
##### 测试
``````package main

import (
"fmt"
)

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()
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()
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)
}``````

### 实现各种类型的链表

##### 各种链表简介

###### 双向链表

• 如果存储同样多的数据，双向链表要比单链表占用更多的内存空间。虽然两个指针比较浪费存储空间，但可以支持双向遍历，这样也带来了双向链表操作的灵活性
• 双向链表的插入和删除操作更高效，因为可以很容易获取到前驱结点
• 如果有一个有序的链表，双向链表的按值查询的效率也要比单链表高一些。因为，我们可以记录上次查找的位置 p，每次查询时，根据要查找的值与 p 的大小关系，决定是往前还是往后查找，所以平均只需要查找一半的数据

##### 各种类型的链表操作

###### 循环链表

``````package loopLinkList

import "fmt"

//循环链表
type Object interface {}

type Node struct {
Data Object
Next *Node
}

type List struct {
}

//判断循环链表是否为空（与单链表的实现没有区别）
func (list *List) IsEmpty() bool {
return true
}

return false
}

//获取循环链表的长度（与单链表的获取长度区别在于循环的终止条件）
func (list *List) Length() int {
return 0
}

count := 1
count++
currentNode = currentNode.Next
}

return count
}

//向循环链头部添加结点
node := &Node{Data: data}
//链表为空的情况
if list.IsEmpty() {
} else {
for currentNode.Next != list.headNode { //需要先找到最后一个结点
currentNode = currentNode.Next
}

currentNode.Next = node //单链表没有这一步操作，将最后一个节点的next指向头结点
}
}

//向循环链表的尾部添加结点
func (list *List) Append(data Object) {
node := &Node{Data: data}

if list.IsEmpty() {
} else {
currentNode = currentNode.Next
}

currentNode.Next = node
}
}

//向循环链表的指定位置添加结点（跟单链表是一样的）
func (list *List) Insert(position int, data Object) {
if position <= 1 {
} else if position > list.Length() {
list.Append(data)
} else {
count := 1
for count < position-1 {
currentNode = currentNode.Next
count++
}

node := &Node{Data: data}
node.Next = currentNode.Next
currentNode.Next = node
}
}

//删除循环链表的头结点
if list.IsEmpty() {
fmt.Println("链表是空的")
return
}

//考虑循环链表只有一个结点的情况
return
}

lastNode = lastNode.Next
}

}

//删除循环链表的尾结点
func (list *List) RemoveLastNode() {
if list.IsEmpty() {
fmt.Println("链表是空的")
return
}

//考虑循环链表只有一个结点的情况
return
}

currentNode = currentNode.Next
}

}

//删除循环链表中指定位置的节点 (需考虑删除的结点是不是第一个或最后一个)
func (list *List) RemovePosition(position int) {
if list.IsEmpty() {
fmt.Println("链表为空")
return
}

if position <= 1 {
} else if position > list.Length() {
list.RemoveLastNode()
} else {
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
}

//删除的结点为头结点时
if currentNode.Data == data {
return
}

if currentNode.Next.Data == data {
currentNode.Next = currentNode.Next.Next
return
} else {
currentNode = currentNode.Next
}
}

list.RemoveLastNode()
}
}

//查找循环链表中指定结点
func (list *List) Contain(data Object) bool {
if list.IsEmpty() {
return false
}

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
}

if currentNode.Next == list.headNode { //兼容循环链表只有一个结点的情况
fmt.Printf("%v\t", currentNode.Data)
return
}

fmt.Printf("%v\t", currentNode.Data)
currentNode = currentNode.Next
}
fmt.Printf("%v\t", currentNode.Data)
}
``````

entry.go（测试）

``````package main

import (
"fmt"
)

fmt.Printf("链表长度：%d\n", list.Length())
fmt.Println("遍历链表所有结点：")
list.Traverse()
fmt.Println()
fmt.Println()
}

func main() {

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、向循环链头部添加结点++++++++")
print(list)

fmt.Println("++++++++4、向循环链尾部添加结点++++++++")
list.Append("lastNode")
print(list)

fmt.Println("++++++++5、向循环链指定位置添加结点++++++++")
list.Insert(1,"secondNode")
print(list)

fmt.Println("++++++++6、删除循环链的头结点++++++++")
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)

}
``````
###### 双向链表

``````package doublyLinkedList

import (
"fmt"
)

//双向链表
type Object interface {}

type Node struct {
Data Object
Prev,Next *Node
}

type List struct {
}

//说明
/**
1、如果结点的Next指向为null，则说明是最后一个结点
2、第一个结点的prev指向为空
3、双向链表和单向链表差不多，区别就是删除和添加结点的时候更方便了，因为很方便的可以获取到前一个结点
*/

//判断双向链表是否为空
func (list *List) IsEmpty() bool {
return true
}

return false
}

//遍历双向链表（跟遍历单链表一模一样）
func (list *List) Traverse() {
if list.IsEmpty() {
fmt.Println("双线链表为空")
return
}

for currentNode != nil {
fmt.Printf("%v\t", currentNode.Data)
currentNode = currentNode.Next
}
}

//获取双向链表的长度（跟获取单链表长度一模一样）
func (list *List) Length() int {
if list.IsEmpty() {
return 0
}

count := 0
for currentNode != nil {
count++
currentNode = currentNode.Next
}

return count
}

//从双向链表头部开始增加结点
node := &Node{Data: data}
if list.IsEmpty() {
return node
}

return node
}

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

currentNode.Next = node
node.Prev = currentNode
}
}

/**
* 向双向链表的指定位置插入结点
*
* 说明：在单向链表中，我是通过找到我要插入的这个结点的前一个结点，然后将要插入的结点，
* 插入到这个结点的后边（因为插入结点需要找到当前结点的前一个结点，为了避免再次遍历找前一个结点，所以采用了这种方式）
* 而双向链表就不需要这么做了，找到指定位置的结点，新的插入到它前边就可以了
*/
func (list *List) Insert(position int, data Object) {
if position <= 1 {
} else if position > list.Length() {
list.Append(data)
} else {
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
}

if currentNode.Next == nil && currentNode.Prev == nil {
return currentNode.Data
}

currentNode.Prev = nil

return currentNode.Data
}

//删除链表尾结点
func (list *List) RemoveLastNode() Object {
if list.IsEmpty() {
fmt.Println("链表为空")
return nil
}

}

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
}

}

fmt.Println(data, currentNode.Data, currentNode.Data == data)
for currentNode != nil {
if currentNode.Data == data && currentNode == list.headNode {
} 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 {
} else if position > list.Length() {
list.RemoveLastNode()
} else {
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
}

for currentNode != nil {
if currentNode.Data == data {
return true
}

currentNode = currentNode.Next
}

return false
}
``````

entry.go（测试）

``````package main

import (
"fmt"
)

fmt.Printf("链表长度%d\n", list.Length())
fmt.Println("遍历链表所有结点：")
list.Traverse()
fmt.Println()
fmt.Println()
}

func main() {

fmt.Println("++++++++1、判断链表是否为空++++++++")
fmt.Printf("链表是否为空：%v", list.IsEmpty())
fmt.Println()
fmt.Println()

fmt.Println("++++++++2、向双向链表头部添加元素++++++++")
fmt.Println()
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()
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))
}``````
###### 双向循环链表

``````package doublyLoopLinkedList

import (
"fmt"
)

type Object interface {}

type Node struct {
Data Object
Prev,Next *Node
}

type List struct {
}

//判断双向循环链表是否为空
func (list *List) IsEmpty() bool {
return true
}

return false
}

//遍历双向循环链表
func (list *List) Traverse() {
if list.IsEmpty() {
fmt.Println("链表为空")
return
}

return
}

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
count++
currentNode = currentNode.Next
}

return count
}

//从双向循环链表头部添加结点(一定一定要画图，比较好理解)
node := &Node{Data: data}
if list.IsEmpty() {
return node
}

if currentNode.Next == nil { //考虑只有一个节点的时候
node.Prev = currentNode
currentNode.Next = node
node.Next = currentNode
currentNode.Prev = node
return node
}

node.Prev = currentNode.Prev
currentNode.Prev.Next = node
currentNode.Prev = node
node.Next = currentNode

return node
}

//从双向循环链表尾部添加结点
func (list *List) Append(data Object) *Node {
node := &Node{Data: data}
if list.IsEmpty() {
return node
}

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 {
} else if position > list.Length() {
list.Append(data)
} else {
node := &Node{Data: data}
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 ""
}

if currentNode.Next == nil {//只有一个结点的情况
return currentNode.Data
}

currentNode.Prev.Next = currentNode.Next
currentNode.Next.Prev = currentNode.Prev

return currentNode.Data
}

//删除双向循环链表尾结点
func (list *List) RemoveLastNode() Object {
if list.IsEmpty() {
fmt.Println("双向循环链表为空")
return ""
}

if currentNode.Next == nil {//只有一个结点的情况
}

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
}

//如果链表只有一个节点
return true
}
return false
}

//如果值刚好等于第一个节点的值
if currentNode.Data == data {
return true
}

//如果值刚好等于最后一个结点的值
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 {
} else if position > list.Length() {
list.RemoveLastNode()
} else {
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
}

if currentNode.Data == data {
return true
}

currentNode = currentNode.Next
}

if currentNode.Data == data {
return true
}

return false
}
``````

entry.go

``````package main

import (
"fmt"
)

fmt.Printf("链表长度%d\n", list.Length())
fmt.Println("遍历链表所有结点：")
list.Traverse()
fmt.Println()
fmt.Println()
}

func main() {

fmt.Println("++++++++1、判断链表是否为空++++++++")
fmt.Printf("链表是否为空：%v", list.IsEmpty())
fmt.Println()
fmt.Println()

fmt.Println("++++++++2、向双向循环链表头部添加结点++++++++")
fmt.Println()
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()
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)
}``````

《数据结构与算法之美》