目的

在刷算法题中经常遇到关于链表的操作，在使用go语言去操作链表时不熟悉其实现原理，目的是为了重温链表这一基础且关键的数据结构。

1、链表的特点和初始化

1.1、链表的特点
用一组任意的存储单元存储线性表的数据元素(这组存储单元可以是连续的，也可以是不连续的)

1.2、结点

结点(node)

• 数据域 => 存储元素信息
• 指针域 => 存储结点的直接后继，也称作指针或链

首元结点 是指链表中存储的第一个数据元素的结点
头结点 是在首元结点之前附设的一个结点，其指针域指向首元结点(非必须)
头指针 是指向链表中第一个结点的指针

1.3、单链表
特点

• 每个结点中只包含一个指针域
• 单链表是非随机存取的存储结构，要取得第i个数据元素必须从头指针出发，顺链进行寻找，也称为顺序存取的存取结构

1.4、单链表的常用操作

本文主要实现了单链表的以下操作

• 判断是否为空
• 获取链表长度
• 在头部插入元素
• 在尾部插入元素
• 删除指定位置元素
• 删除指定值的元素
• 查找是否包含指定值
• 查找指定位置元素的值
• 遍历链表所有结点

1.5、单链表的初始化

//定义单链表结构体type Node struct { data interface{} //数据域 next *Node //指针域}type List struct { length int //储存链表的长度 headNode *Node}func InitList() *List { //即构造一个空的单链表L(包含头指针) node := new(Node) L := new(List) L.headNode = node return L}

2、单链表的插入

先讲单链表的插入有利于后续相关操作的实现

2.1、在指定位置插入元素

/*单链表的插入=>将值为e的新结点插入到表的第i个结点的位置上，即插入到结点a(i-1)与a(i)之间1、查找结点a(i-1)并由指针p指向该结点2、生成一个新结点*s3、将新结点*s的数据域置为e4、将新结点*s的指针域指向结点a(i)5、将结点*p的指针域指向新结点*s*/func (list *List) InsertElem(index int, v interface{}) { if index <= 0 || index > list.length { fmt.Println("err") } else { pre := list.headNode node := &Node{data: v} if index == 1 { node.next = pre list.headNode = node } else { for count := 1; count < index-1; count++ { pre = pre.next } node.next = pre.next pre.next = node } list.length-- }}

2.2、在头部插入元素

func (list *List) AddElem(v interface{}) { node := &Node{data: v} if list.IsNull() { //处理空表的插入，否则会导致一个空的头结点后移 list.headNode = node list.length++ return } node.next = list.headNode list.headNode = node list.length++ return}

2.3、在尾部插入元素

func (list *List) AppendElem(v interface{}) { node := &Node{data: v} if list.IsNull() { list.headNode.next = node } else { cur := list.headNode for cur.next != nil { cur = cur.next } cur.next = node } list.length++ return}

3、单链表的删除

3.1、删除指定值的元素

/*单链表的删除1、查找结点a(i-1)并由指针p指向该结点2、临时保存待删除结点a(i)的地址在q中，以备释放3、将结点*p的指针域指向a(i)的直接后继结点4、释放结点a(i)的空间*/func (list *List) DeleteElem(index int) { if index <= 0 || index > list.length { fmt.Println("删除位置不合理") return } else { pre := list.headNode if index == 1 { list.headNode = pre.next } else { pre := list.headNode for count := 1; count < index-1; count++ { pre = pre.next } pre.next = pre.next.next } list.length-- }}

3.2、删除指定位置的元素

func (list *List) RemoveElem(v interface{}) { pre := list.headNode if pre.data == v { list.headNode = pre.next fmt.Println("ok") } else { for pre.next != nil { if pre.next.data == v { pre.next = pre.next.next fmt.Println("ok") return } else { pre = pre.next } } fmt.Println("fail") return }}

4、单链表的查询

4.1、查找是否包含指定值

func (list *List) LocateElem(v interface{}) bool { if IsNull() { fmt.Println("err") } else { pre := list.headNode for pre != nil { if pre.data == v { return true } pre = pre.next } return false }}

4.2、查找指定位置的值

func (list *List) GetElem(index int) int { if index <= 0 || index > list.length { fmt.Println("err") return } else { pre := list.headNode for j := 0; j < index; j++ { if pre != nil { pre = pre.next } } return pre.data }}

4.3、遍历单链表

func (list *List) ShowList() { if !list.IsNull() { cur := list.headNode for { fmt.Printf("\t%v", cur.data) if cur.next != nil { cur = cur.next } else { break } } }}

5、完整代码及结果展示

package mainimport "fmt"//定义单链表结构体type Node struct { data interface{} //数据域 next *Node //指针域}type List struct { length int //储存链表的长度 headNode *Node}func InitList() *List { //即构造一个空的单链表L(包含头指针) node := new(Node) L := new(List) L.headNode = node return L}func (list *List) GetElem(index int) int { if index <= 0 || index > list.length { return 0 } else { pre := list.headNode for j := 0; j < index-1; j++ { if pre != nil { pre = pre.next } } return pre.data.(int) }}func (list *List) LocateElem(v interface{}) bool { if list.IsNull() { fmt.Println("err") return false } else { pre := list.headNode for pre != nil { if pre.data == v { return true } pre = pre.next } return false }}/*单链表的插入=>将值为e的新结点插入到表的第i个结点的位置上，即插入到结点a(i-1)与a(i)之间1、查找结点a(i-1)并由指针p指向该结点2、生成一个新结点*s3、将新结点*s的数据域置为e4、将新结点*s的指针域指向结点a(i)5、将结点*p的指针域指向新结点*s*/func (list *List) InsertElem(index int, v interface{}) { if index <= 0 || index > list.length { fmt.Println("err") } else { pre := list.headNode node := &Node{data: v} if index == 1 { node.next = pre list.headNode = node } else { for count := 1; count < index-1; count++ { pre = pre.next } node.next = pre.next pre.next = node } list.length-- }}/*单链表的删除1、查找结点a(i-1)并由指针p指向该结点2、临时保存待删除结点a(i)的地址在q中，以备释放3、将结点*p的指针域指向a(i)的直接后继结点4、释放结点a(i)的空间*/func (list *List) DeleteElem(index int) { if index <= 0 || index > list.length { fmt.Println("删除位置不合理") return } else { pre := list.headNode if index == 1 { list.headNode = pre.next } else { pre := list.headNode for count := 1; count < index-1; count++ { pre = pre.next } pre.next = pre.next.next } list.length-- }}func (list *List) RemoveElem(v interface{}) { pre := list.headNode if pre.data == v { list.headNode = pre.next } else { for pre.next != nil { if pre.next.data == v { pre.next = pre.next.next return } else { pre = pre.next } } fmt.Println("fail") return }}func (list *List) IsNull() bool { if list.length == 0 { return true } else { return false }}func (list *List) AddElem(v interface{}) { node := &Node{data: v} if list.IsNull() { //处理空表的插入，否则会导致一个空的头结点后移 list.headNode = node list.length++ return } node.next = list.headNode list.headNode = node list.length++ return}func (list *List) AppendElem(v interface{}) { node := &Node{data: v} if list.IsNull() { list.headNode.next = node } else { cur := list.headNode for cur.next != nil { cur = cur.next } cur.next = node } list.length++ return}func (list *List) ShowList() { if !list.IsNull() { cur := list.headNode for { fmt.Printf("\t%v", cur.data) if cur.next != nil { cur = cur.next } else { break } } fmt.Printf("\n") }}func main() { L := InitList() msg := []int{12, 5, 3, 8, 55, 13} for i := range msg { L.AddElem(msg[i]) } fmt.Println("---- 添加元素 ----") L.AppendElem(66) L.ShowList() fmt.Println("---- 按位删除元素 ----") L.DeleteElem(3) L.ShowList() fmt.Println("---- 按值删除元素 ----") L.RemoveElem(13) L.ShowList() fmt.Println("---- 插入元素 ----") L.InsertElem(1, 88) L.ShowList() fmt.Println("---- 按值寻找元素 ----") fmt.Println(L.LocateElem(88)) fmt.Println("---- 按位寻找元素 ----") fmt.Println(L.GetElem(4))}

结果
---- 添加元素 ----
13 55 8 3 5 12 66
---- 按位删除元素 ----
13 55 3 5 12 66
---- 按值删除元素 ----
55 3 5 12 66
---- 插入元素 ----
88 55 3 5 12 66
---- 按值寻找元素 ----
true
---- 按位寻找元素 ----
5

6、总结

本文中除了初始化时为链表添加了一个空的头结点，其他情况下均无头结点，正如书中所说，为单链表添加头结点会方便很多，对链表进行相关操作时，不需要对首元结点做额外的处理，也便于对空表和非空表做统一处理
关于删除时释放结点空间及指针回收，我们交由go强大的垃圾回收来完成

参考博客
Golang之单链表实现
go语言实现单链表

到此这篇关于详解go语言单链表及其常用方法的实现的文章就介绍到这了,更多相关go语言单链表内容请搜索以前的文章或继续浏览下面的相关文章希望大家以后多多支持！