概述
链表是一种物理存储结构上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的 “指针” 将一组零散的内存卡串联起来实现的。
单向链表
单向链表其中有两个结点是比较特殊的，它们分别是第一个结点和最后一个结点。我们习惯性地把第一个结点叫作头结点，把最后一个结点叫作尾结点。其中，头结点用来记录链表的基地址。有了它，我们就可以遍历得到整条链表。而尾结点特殊的地方是：指针不是指向下一个结点，而是指向一个空地址 NULL，表示这是链表上最后一个结点。
插入节点
删除节点
代码实现
package main
import "fmt"
type Node struct {
id int
name string
next *Node // 指向下一个节点
}
// 往链表中插入一个节点
func InsertNode(headNode *Node, newNode *Node) {
// 创建一个辅助节点
temp := headNode
for {
if temp.next == nil {
break
}
temp = temp.next // 不断的指向下一个结点
}
temp.next = newNode
}
// 显示链表的所有结点信息
func ShowNode(headNode *Node) {
temp := headNode
// 判断该链表是不是一个空的链表
if temp.next == nil {
fmt.Println("空空如也...")
return
}
for {
fmt.Println(temp.next.id, temp.next.name)
// 判断是否到链表最后
temp = temp.next
if temp.next == nil {
break
}
}
}
// 删除链表指定的节点信息
func DelNode(headNode *Node, id int) {
temp := headNode
flag := false
for {
if temp.next == nil {
break
} else if temp.next.id == id {
flag = true
break
}
temp = temp.next
}
if flag {
temp.next = temp.next.next
} else {
fmt.Println("ID不存在")
}
}
func main() {
// 创建一个头结点
headNode := &Node{}
// 创建一个新的 Node
node1 := &Node{
id: 1,
name: "aa",
}
node2 := &Node{
id: 2,
name: "bb",
}
node3 := &Node{
id: 3,
name: "cc",
}
InsertNode(headNode, node1)
InsertNode(headNode, node2)
InsertNode(headNode, node3)
DelNode(headNode, 2) // 删除指定ID
ShowNode(headNode)
/*输出结果：
1 aa
3 cc*/
}
目前往链表中插入默认是不排序的，我们可以实现根据ID来排序，代码修改如下：
// 往链表中插入一个节点（根据ID排序）
func InsertNodeOrderByID(headNode *Node, newNode *Node) {
// 创建一个辅助节点
temp := headNode
flag := true
for {
// 让插入的结点的 no 和 temp 的下一个结点的 no 比较
if temp.next == nil {
break
} else if temp.next.id > newNode.id {
break
} else if temp.next.id == newNode.id {
flag = false
break
}
temp = temp.next // 不断的指向下一个结点
}
if flag {
newNode.next = temp.next
temp.next = newNode
} else {
fmt.Println("ID已存在")
return
}
}
双向链表
双向链表需要额外的两个空间来存储后继结点和前驱结点的地址。所以，如果存储同样多的数据，双向链表要比单链表占用更多的内存空间。虽然两个指针比较浪费存储空间，但可以支持双向遍历，这样也带来了双向链表操作的灵活性。
插入节点
删除节点
代码实现
package main
import "fmt"
type Node struct {
id int
name string
pre *Node // 指向前一个结点
next *Node // 指向下一个结点
}
// 往双向链表中插入一个节点
func InsertNode(headNode *Node, newHeroNode *Node) {
temp := headNode
for {
if temp.next == nil {
break
}
temp = temp.next
}
temp.next = newHeroNode
newHeroNode.pre = temp
}
// 往双向链表中插入一个节点（根据ID排序）
func InsertNodeOrderByID(headNode *Node, newNode *Node) {
// 创建一个辅助节点
temp := headNode
flag := true
for {
// 让插入的结点的 no 和 temp 的下一个结点的 no 比较
if temp.next == nil {
break
} else if temp.next.id > newNode.id {
break
} else if temp.next.id == newNode.id {
flag = false
break
}
temp = temp.next // 不断的指向下一个结点
}
if flag {
newNode.next = temp.next
newNode.pre = temp
if temp.next != nil {
temp.next.pre = newNode
}
temp.next = newNode
} else {
fmt.Println("ID已存在")
return
}
}
// 显示链表的所有结点信息
func ShowNode(headNode *Node) {
temp := headNode
// 判断该链表是不是一个空的链表
if temp.next == nil {
fmt.Println("空空如也...")
return
}
for {
fmt.Println(temp.next.id, temp.next.name)
// 判断是否到链表最后
temp = temp.next
if temp.next == nil {
break
}
}
}
// 删除双向链表指定的节点信息
func DelNode(headNode *Node, id int) {
temp := headNode
flag := false
for {
if temp.next == nil {
break
} else if temp.next.id == id {
flag = true
break
}
temp = temp.next
}
if flag {
temp.next = temp.next.next
if temp.next != nil {
temp.next.pre = temp
}
} else {
fmt.Println("ID不存在")
}
}
func main() {
// 创建一个头结点
headNode := &Node{}
// 创建一个新的 Node
node1 := &Node{
id: 1,
name: "aa",
}
node2 := &Node{
id: 2,
name: "bb",
}
node3 := &Node{
id: 3,
name: "cc",
}
InsertNodeOrderByID(headNode, node3)
InsertNodeOrderByID(headNode, node1)
InsertNodeOrderByID(headNode, node2)
DelNode(headNode, 2) // 删除指定ID
ShowNode(headNode)
/*输出结果：
1 aa
3 cc*/
}
环形链表
环形链表是一种特殊的单链表。实际上，环形链表也很简单。它跟单链表唯一的区别就在尾结点。我们知道，单链表的尾结点指针指向空地址，表示这就是最后的结点了。而环形链表的尾结点指针是指向链表的头结点。
插入节点
删除节点
代码实现
package main
import "fmt"
type Node struct {
id int
name string
next *Node
}
// 往环形链表中插入一个节点
func InsertNode(headNode *Node, newNode *Node) {
// 判断是否第一个节点
if headNode.next == nil {
headNode.id = newNode.id
headNode.name = newNode.name
headNode.next = headNode // 构成一个环状
return
}
// 定义一个临时变量，帮忙找到环形的最后节点
temp := headNode
for {
if temp.next == headNode {
break
}
temp = temp.next
}
// 加入到链表中
temp.next = newNode
newNode.next = headNode
}
// 显示链表的所有结点信息
func ShowNode(headNode *Node) {
temp := headNode
if temp.next == nil {
fmt.Println("空空如也...")
return
}
for {
fmt.Println(temp.id, temp.name)
if temp.next == headNode {
break
}
temp = temp.next
}
}
// 删除环形链表指定的节点信息
func DelNode(headNode *Node, id int) *Node {
temp := headNode
helper := headNode
if temp.next == nil {
fmt.Println("这是一个空的环形链表，不能删除")
return headNode
}
// 如果只有一个结点
if temp.next == headNode {
temp.next = nil
return headNode
}
// 将 helper 定位到链表最后
for {
if helper.next == headNode {
break
}
helper = helper.next
}
flag := true
for {
// 如果到这里，说明比较到最后一个（最后一个还没比较）
if temp.next == headNode {
break
}
if temp.id == id {
// 找到了可以直接删除
helper.next = temp.next
flag = false
}
temp = temp.next
helper = helper.next
}
if flag && temp.id == id {
helper.next = temp.next
fmt.Println("删除ID：", id)
} else {
fmt.Println("ID不存在")
}
return headNode
}
func main() {
// 创建一个头结点
headNode := &Node{}
// 创建一个新的 Node
node1 := &Node{
id: 1,
name: "aa",
}
node2 := &Node{
id: 2,
name: "bb",
}
node3 := &Node{
id: 3,
name: "cc",
}
InsertNode(headNode, node3)
InsertNode(headNode, node1)
InsertNode(headNode, node2)
DelNode(headNode, 2) // 删除指定ID
ShowNode(headNode)
/*输出结果：
删除ID： 2
3 cc
1 aa*/
}
约瑟夫问题
Josephu 问题为：设编号为 1，2，… n 的 n 个人围坐一圈，约定编号为 num（1<=num<=n）的人从 1 开始报数，数到 m 的那个人出列，它的下一位又从 1 开始报数，数到 m 的那个人又出列，依次类推，直到所有人出列为止，由此产生一个出队编号的序列。
实现思路
用一个不带头结点的循环链表来处理 Josephu 问题：先构成一个有 n 个结点的单循环链表，然后由 k 结点起从 1 开始计数，计到 m 时，对应结点从链表中删除，然后再从被删除结点的下一个结点又从 1 开始计数，直到最后一个结点从链表中删除算法结束。
代码实现
package main
import "fmt"
type Boy struct {
No int // 编号
Next *Boy // 指向下一个小孩的指针
}
// 编写一个函数，构成单向的环形链表
func AddBoy(num int) *Boy {
first := &Boy{}
curBoy := &Boy{}
if num < 1 {
fmt.Println("num 的值不对")
return first
}
// 循环构建环形链表
for i := 0; i <= num; i++ {
boy := &Boy{
No: i,
}
// 因为第一个Boy比较特殊
if i == 1 {
first = boy
curBoy = boy
curBoy.Next = first
} else {
curBoy.Next = boy
curBoy = boy
curBoy.Next = first // 构成环形链表
}
}
return first
}
// 显示单向的环形链表
func ShowBoy(first *Boy) {
// 处理一下如果环形链表为空
if first.Next == nil {
fmt.Println("链表为空")
return
}
// 创建一个指针，帮助遍历（至少有一个Boy）
curBoy := first
for {
fmt.Println("Boy No=", curBoy.No)
if curBoy.Next == first {
break
}
// curBoy移动到下一个
curBoy = curBoy.Next
}
}
func PlayGame(first *Boy, startNo int, countNum int) {
if first.Next == nil {
fmt.Println("链表为空")
return
}
tail := first
for {
// 说明tail到了最后的Boy
if tail.Next == first {
break
}
tail = tail.Next
}
for i := 1; i <= startNo; i++ {
first = first.Next
tail = tail.Next
}
for {
for i := 1; i <= countNum-1; i++ {
first = first.Next
tail = tail.Next
}
fmt.Println("出列的 Boy No=", first.No)
first = first.Next
tail.Next = first
if tail == first {
break
}
}
fmt.Println("最后出列的 Boy No=", first.No)
}
func main() {
first := AddBoy(30)
// ShowBoy(first)
PlayGame(first, 2, 3)
/*输出结果：
出列的 Boy No= 5
出列的 Boy No= 8
出列的 Boy No= 11
出列的 Boy No= 14
出列的 Boy No= 17
出列的 Boy No= 20
出列的 Boy No= 23
出列的 Boy No= 26
出列的 Boy No= 29
出列的 Boy No= 2
出列的 Boy No= 6
出列的 Boy No= 10
出列的 Boy No= 15
出列的 Boy No= 19
出列的 Boy No= 24
出列的 Boy No= 28
出列的 Boy No= 3
出列的 Boy No= 9
出列的 Boy No= 16
出列的 Boy No= 22
出列的 Boy No= 30
出列的 Boy No= 7
出列的 Boy No= 18
出列的 Boy No= 27
出列的 Boy No= 12
出列的 Boy No= 25
出列的 Boy No= 13
出列的 Boy No= 4
出列的 Boy No= 21
最后出列的 Boy No= 1*/
}