(编辑:jimmy 日期: 2024/12/23 浏览:2)
目的
在刷算法题中经常遇到关于链表的操作,在使用go语言去操作链表时不熟悉其实现原理,目的是为了重温链表这一基础且关键的数据结构。
1、链表的特点和初始化
1.1、链表的特点
用一组任意的存储单元存储线性表的数据元素(这组存储单元可以是连续的,也可以是不连续的)
1.2、结点
结点(node)
首元结点 是指链表中存储的第一个数据元素的结点
头结点 是在首元结点之前附设的一个结点,其指针域指向首元结点(非必须)
头指针 是指向链表中第一个结点的指针
1.3、单链表
特点
1.4、单链表的常用操作
本文主要实现了单链表的以下操作
1.5、单链表的初始化
//定义单链表结构体 type Node struct { data interface{} //数据域 next *Node //指针域 } type List struct { length int //储存链表的长度 headNode *Node } /*单链表的初始化 1、生成新结点作为头结点,用头指针指向头结点 2、头结点的指针域置空 */ 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、生成一个新结点*s 3、将新结点*s的数据域置为e 4、将新结点*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、查找是否包含指定值
/*单链表的按值查找 1、用指针p指向首元结点 2、从首元结点开始以此顺着链域next向下查找,只要指向当前结点的指针p不为空, 并且p所指结点的数据域不等于给定值e,则执行以下操作:p指向下一个结点 3、返回p。若查找成功,p此时即为结点的地址值,若查找失败,p的值即为NULL。 */ 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、查找指定位置的值
/*单链表的取值 1、用指针P指向首元结点,用j做计数器初值赋为1 2、从首元结点开始依次顺着链域(指针域)next向下访问, 只要指向当前结点的指针P不为空,并且没有达到序号为i的结点,则循环执行以下操作: 2.1、P指向下一个结点 2.2、计数器j相应加1 3、退出循环时,如果指针P为空,或者计数器j大于i,说明指定的序号i值不合法(i大于表长n或i小于等于0), 取值失败返回ERROR;否则取值成功, 此时j==i时,P所指的结点就是要找的第i个结点,用参数e保存当前结点的数据域,返回OK */ 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 main import "fmt" //定义单链表结构体 type Node struct { data interface{} //数据域 next *Node //指针域 } type List struct { length int //储存链表的长度 headNode *Node } /* type Method interface { IsNull() bool //1、判断是否为空 GetLength() int //2、获取链表长度 InsertElem(i int, v interface{}) //3、在指定位置添加元素 AddElem(v interface{}) //4、在头部插入元素 AppendElem(v interface{}) //5、在尾部插入元素 DeleteElem(i int) //6、删除指定位置元素 RemoveElem(v interface{}) //7、删除指定值的元素 ContaineElem(v interface{}) bool //8、是否包含指定值的元素 LocateElem(i int) interface{} //9、查找指定位置元素的值 ShowList() //10、遍历链表所有结点 } */ /*单链表的初始化 1、生成新结点作为头结点,用头指针指向头结点 2、头结点的指针域置空 */ func InitList() *List { //即构造一个空的单链表L(包含头指针) node := new(Node) L := new(List) L.headNode = node return L } /*单链表的取值 1、用指针P指向首元结点,用j做计数器初值赋为1 2、从首元结点开始依次顺着链域(指针域)next向下访问,只要指向当前结点的指针P不为空, 并且没有达到序号为i的结点,则循环执行以下操作: 2.1、P指向下一个结点 2.2、计数器j相应加1 3、退出循环时,如果指针P为空,或者计数器j大于i,说明指定的序号i值 不合法(i大于表长n或i小于等于0),取值失败返回ERROR;否则取值成功, 此时j==i时,P所指的结点就是要找的第i个结点,用参数e保存当前结点的数据域,返回OK */ 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) } } /*单链表的按值查找 1、用指针p指向首元结点 2、从首元结点开始以此顺着链域next向下查找,只要指向当前结点的 指针p不为空,并且p所指结点的数据域不等于给定值e,则执行以下操作: 2.1、p指向下一个结点 3、返回p。若查找成功,p此时即为结点的地址值,若查找失败,p的值即为NULL。 */ 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、生成一个新结点*s 3、将新结点*s的数据域置为e 4、将新结点*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语言实现单链表