最后更新日期：2022/07/04
Golang本身自带实现list的基本库：container/list；具体使用方法，可以查看Go基础库文档：https://studygolang.com/pkgdoc
下面是不适用基础库的实现方法，优化方式有很多，实现思路仅供参考：
一、单链表
下文实现了单向链表、循环链表、双向链表，单链表是基础，其他的链表基本都是根据单链表演化的。
1. 节点（node）
- 指针域：指向下一个节点的指针
- 数据域：保存数据
2. 链表（Link list）
- 头指针：指向链表第一个节点的指针（有头节点指向的是头节点，没有头节点指向的是首元节点）
- 头节点：链表的首个节点，数据域可以是链表长度等信息，也可以什么都不保存；指针域指向第一个首元节点，头节点是为了简化链表操作而存在的，也可以不设头节点。
- 首元节点：链表的第一个有效数据节点
3.代码及解析
3.1 代码：
先把代码贴上，后续分解代码：
package main
import "fmt"
//单向链表 头指针、头节点（方便链表增删的）、首元节点（第一个有效数据节点）
type Node struct {
data int //数据域
next *Node //指针域
}
func ShowNode(p *Node) { //遍历链表值
for p != nil {
fmt.Println(*p)
p = p.next
}
fmt.Println()
}
//查找对应值的index
func Find(p *Node, obj int) int { //获取目标值obj的index(0是头节点，找到的第一个值)，没找到返回-1
head := p
if head == nil {
return -1
}
for i := 0; head != nil; i++ { //head != nil; 操作数据域
if head.data == obj {
return i
}
head = head.next
}
return -1
}
//更新数据
func Update(p *Node, val, index int) bool { //修改目标index对应节点的值
head := p
if head == nil {
return false
}
for i := 1; i <= index; i++ {
head = head.next //略过头节点
if head == nil {
return false
}
}
head.data = val
return true
}
//获取index对应的节点数据 获取失败返回-1
func GetNodeData(p *Node, index int) int {
head := p
if head == nil || index < 0 {
return -1
}
for i := 1; i <= index; i++ {
head = head.next //略过头节点
if head == nil {
return -1
}
}
return head.data
}
//获取前驱节点
func GetPreNode(p *Node, index int) *Node {
head := p
if head == nil || index < 0 {
return head
}
//找到[前驱节点] 当前链表index位置上的前一个节点
for ; index-1 > 0; index-- {
if head.next != nil {
head = head.next
} else { //没找到
return nil
}
}
return head
}
//插入节点 (0是头节点)
func Insert(p *Node, val, index int) bool {
head := p
if head == nil || index < 0 {
return false
}
preNode := GetPreNode(head, index)
if preNode == nil {
return false
}
node := Node{data: val, next: preNode.next} //即使preNode.next=nil也无所谓
preNode.next = &node
return true
}
//删除节点 (0是头节点)
func Delete(p *Node, val, index int) bool {
head := p
if head == nil || index < 0 {
return false
}
preNode := GetPreNode(head, index)
if preNode == nil {
return false
}
preNode.next = preNode.next.next //不用判断 head.next.next==nil
return true
}
func linkList(length int) *Node { // 1.尾插法 插入节点 head>>node1>>node2 <<tail
//头节点
head := Node{data: 0}
var tail *Node
tail = &head
//构造单向链表
for i := 1; i <= length; i++ {
node := Node{data: i}
tail.next = &node
tail = &node
}
//返回头节点地址
return &head
}
const LENGTH = 3
func main() {
head := linkList(LENGTH)
//遍历
ShowNode(head)
//获取某个值的索引
fmt.Println("Find0:", Find(head, 0))
fmt.Println("Find2:", Find(head, 2))
fmt.Println("Find3:", Find(head, 4))
//节点插入
if Insert(head, 10, 4) {
fmt.Println("插入数据")
ShowNode(head)
} else {
fmt.Println("插入失败")
}
//删除节点
if Delete(head, 10, 4) {
fmt.Println("删除数据")
ShowNode(head)
} else {
fmt.Println("删除失败")
}
//修改节点
if Update(head, 22, 2) {
fmt.Println("修改数据")
ShowNode(head)
} else {
fmt.Println("修改失败")
}
//获取数据
if data := GetNodeData(head, 2); data != -1 {
fmt.Println("获取数据:", data)
} else {
fmt.Println("获取数据失败")
}
//头插法
tail := linkList2(10)
ShowNode(tail)
}
func linkList2(length int) *Node { // 2.头插法 插入节点 tail>> node2<<node1<<head
head := Node{data: 0}
var tail *Node
tail = &head //tail用于记录头节点地址，首先指向头节点
for i := 1; i < length; i++ {
var node = Node{data: i}
node.next = tail //将新创建的node的next指向头节点
tail = &node //重新赋值头节点
}
return tail
}
3.2 增删改查图示：
-
链表操作主要分为：增、删、改、查； 根据实现过程，增删操作类似、改查操作类似
-
增加和删除
-
增加节点：
步骤：
① 创建插入的节点，找到前驱节点（插入位置的前一个节点）
② 新节点的next指向前驱节点的next
③ 前驱节点的next指针指向新的节点 -
删除节点：
步骤：
① 找到删除节点的前驱节点
② 改变前驱节点的next指向（略过删除节点，指向删除节点的下一个节点）
③ 删除节点操作，与其他语言不同的是，golang GC可以在②操作后，通过GC自动回收删除节点- 通过增加和删除操作流程中可以看出，本质就是一个找到前驱节点后，修改前驱节点的操作
-
-
修改和查找
- 查找 (查找给定值的 index)：
步骤：
① 遍历链表，找到需要目标节点
② 返回目标节点的index- 修改：
步骤：
① 遍历链表，找到需要目标节点
② 修改目标节点- 查找和修改过程基本一样，本质是遍历链表找目标节点本身
-
![[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-C9mTUGpQ-1656924016415)(photo/8.Golang链表操作 增 .png)]](/image/https://img-blog.csdnimg.cn/791a2119ea444b3983036579bf0b4661.png)
3.3 代码解析：
- 构造节点的结构体：
type Node struct {
data int //数据域
next *Node //指针域
}
-
生成链表：尾插法（用的比较多）
-
图示：
- ① 生成头节点，头指针(head)、尾指针(tail)同时指向头节点
- ② 修改链表指针，指向新的节点
- ③ 移动指针tail
- 重复②③，最后返回头指针head
-
代码：
-
-
生成链表：头插法
-
图示：
- ① 生成头节点，头指针(head)、尾指针(tail)同时指向头节点
- ② 修改节点指针，指向链表头节点
- ③ 移动指针tail
- 重复②③，最后返回头指针tail
-
代码：
-
-
遍历链表：
-
插入和删除节点
-
前面说到，插入和删除本质就是一个找到前驱节点后，修改前驱节点的操作
-
GetPreNode是一个获取前驱节点的函数：
-
插入节点
-
- 删除节点
- 更新和查找节点
- 通过给定值obj查找对应节点index
- main
- 结果
二、循环链表
循环链表和双向链表都是基于单向链表演化来的，所以它们的操作都大同小异。
将单向链表的最后一个节点的指针域指向链表的头节点，便可得到一个单向的循环链表
package main
import "fmt"
//单向 循环链表 （单向链表首尾相连）
type LNode struct {
Data int
next *LNode
}
func LoopList(length int) *LNode { //构造单向循环链表
head := LNode{Data: 0} //头节点,按理来说循环链表是没有明确的头的 这里添加的头节点纯属为了简化操作
var tail *LNode
tail = &head
for i := 1; i <= length; i++ { //尾插法生成单向链表
node := LNode{Data: i}
tail.next = &node
tail = &node
}
//首位相连 生成
tail.next = &head
return &head
}
func ShowLoopList(head *LNode) {
if head == nil { //如果头节点.next==nil 则判断为空链表
fmt.Println("空链表")
return
} else if head.next == nil {
fmt.Println("空链表")
return
}
tail := head.next
for tail != head {
fmt.Println(*tail)
tail = tail.next
}
fmt.Println()
}
const LENGTH = 5
func main() {
loopList := LoopList(LENGTH)
ShowLoopList(loopList)
}
三、双向链表
区别于单向链表，双向链表的节点中，指针域多一个之前前节点的指针
package main
import "fmt"
//双向链表
type DNode struct {
data int
pre *DNode
next *DNode
}
func doublyList(length int) *DNode { //创建双向链表
head := DNode{data: 0}
var tail *DNode
tail = &head
for i := 1; i <= length; i++ {
node := DNode{data: i}
tail.next = &node
node.pre = tail
tail = &node
}
return &head
}
func showList(head *DNode) {
if head == nil { //如果头节点.next==nil 则判断为空链表
fmt.Println("空链表")
return
} else if head.next == nil {
fmt.Println("空链表")
return
}
//tail := head.next //略过头节点head
tail := head //不略过头节点head
for tail != nil {
fmt.Println(*tail)
tail = tail.next
}
}
func main() {
list := doublyList(1)
showList(list)
}