詳解go語言單鏈表及其常用方法的實現(xiàn)
更新時間：2020年11月30日 09:31:52 作者：Zppj
這篇文章主要介紹了詳解go語言單鏈表及其常用方法的實現(xiàn)，文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值，需要的朋友們下面隨著小編來一起學習學習吧
目的
在刷算法題中經常遇到關于鏈表的操作，在使用go語言去操作鏈表時不熟悉其實現(xiàn)原理，目的是為了重溫鏈表這一基礎且關鍵的數(shù)據(jù)結構。
1、鏈表的特點和初始化
1.1、鏈表的特點
用一組任意的存儲單元存儲線性表的數(shù)據(jù)元素(這組存儲單元可以是連續(xù)的，也可以是不連續(xù)的)
1.2、結點
結點(node)
- 數(shù)據(jù)域 => 存儲元素信息
- 指針域 => 存儲結點的直接后繼，也稱作指針或鏈
首元結點 是指鏈表中存儲的第一個數(shù)據(jù)元素的結點
頭結點 是在首元結點之前附設的一個結點，其指針域指向首元結點(非必須)
頭指針 是指向鏈表中第一個結點的指針
1.3、單鏈表
特點
- 每個結點中只包含一個指針域
- 單鏈表是非隨機存取的存儲結構，要取得第i個數(shù)據(jù)元素必須從頭指針出發(fā)，順鏈進行尋找，也稱為順序存取的存取結構
1.4、單鏈表的常用操作
本文主要實現(xiàn)了單鏈表的以下操作
- 判斷是否為空
- 獲取鏈表長度
- 在頭部插入元素
- 在尾部插入元素
- 刪除指定位置元素
- 刪除指定值的元素
- 查找是否包含指定值
- 查找指定位置元素的值
- 遍歷鏈表所有結點
1.5、單鏈表的初始化
//定義單鏈表結構體
type Node struct {
data interface{} //數(shù)據(jù)域
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、單鏈表的插入
先講單鏈表的插入有利于后續(xù)相關操作的實現(xiàn)
2.1、在指定位置插入元素
/*單鏈表的插入=>將值為e的新結點插入到表的第i個結點的位置上，即插入到結點a(i-1)與a(i)之間
1、查找結點a(i-1)并由指針p指向該結點
2、生成一個新結點*s
3、將新結點*s的數(shù)據(jù)域置為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所指結點的數(shù)據(jù)域不等于給定值e，則執(zhí)行以下操作：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做計數(shù)器初值賦為1
2、從首元結點開始依次順著鏈域(指針域)next向下訪問，
只要指向當前結點的指針P不為空，并且沒有達到序號為i的結點，則循環(huán)執(zhí)行以下操作：
2.1、P指向下一個結點
2.2、計數(shù)器j相應加1
3、退出循環(huán)時，如果指針P為空，或者計數(shù)器j大于i，說明指定的序號i值不合法(i大于表長n或i小于等于0)，
取值失敗返回ERROR；否則取值成功，
此時j==i時，P所指的結點就是要找的第i個結點，用參數(shù)e保存當前結點的數(shù)據(jù)域，返回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{} //數(shù)據(jù)域
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做計數(shù)器初值賦為1
2、從首元結點開始依次順著鏈域(指針域)next向下訪問，只要指向當前結點的指針P不為空，
并且沒有達到序號為i的結點，則循環(huán)執(zhí)行以下操作：
2.1、P指向下一個結點
2.2、計數(shù)器j相應加1
3、退出循環(huán)時，如果指針P為空，或者計數(shù)器j大于i，說明指定的序號i值
不合法(i大于表長n或i小于等于0)，取值失敗返回ERROR；否則取值成功，
此時j==i時，P所指的結點就是要找的第i個結點，用參數(shù)e保存當前結點的數(shù)據(jù)域，返回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所指結點的數(shù)據(jù)域不等于給定值e，則執(zhí)行以下操作：
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的數(shù)據(jù)域置為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、總結
本文中除了初始化時為鏈表添加了一個空的頭結點，其他情況下均無頭結點，正如書中所說，為單鏈表添加頭結點會方便很多，對鏈表進行相關操作時，不需要對首元結點做額外的處理，也便于對空表和非空表做統(tǒng)一處理
關于刪除時釋放結點空間及指針回收，我們交由go強大的垃圾回收來完成
參考博客
Golang之單鏈表實現(xiàn)
go語言實現(xiàn)單鏈表
到此這篇關于詳解go語言單鏈表及其常用方法的實現(xiàn)的文章就介紹到這了,更多相關go語言單鏈表內容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關文章希望大家以后多多支持腳本之家！
相關文章
WaitGroups是同步你的goroutines的一種有效方式。這篇文章主要來和大家聊聊Golang中WaitGroups的使用，感興趣的小伙伴可以跟隨小編一起了解一下2023-03-03
golang字符串拼接實現(xiàn)方式和區(qū)別對比
本文介紹了Go語言中字符串拼接的多種方法及其優(yōu)缺點,推薦使用strings.Builder進行頻繁拼接以優(yōu)化內存分配和性能,同時,還討論了通過sync.Pool優(yōu)化高頻創(chuàng)建的對象,以減少垃圾回收壓力,感興趣的朋友一起看看吧2025-02-02
Go類型斷言提取測試接口值動態(tài)類型及靜態(tài)轉換確保類型接口編譯安全
這篇文章主要為大家介紹了Go類型斷言提取測試接口值動態(tài)類型及靜態(tài)轉換確保類型實現(xiàn)特定接口的編譯時安全性詳解,有需要的朋友可以借鑒參考下,希望能夠有所幫助,祝大家多多進步,早日升職加薪2023-10-10
使用Go語言創(chuàng)建靜態(tài)文件服務器問題
這篇文章主要介紹了使用Go語言創(chuàng)建靜態(tài)文件服務器,本文通過試了代碼給大家介紹的非常詳細，對大家的學習或工作具有一定的參考借鑒價值，需要的朋友可以參考下2020-03-03
這篇文章主要為大家介紹了golang?gorm更新日志執(zhí)行SQL示例詳解，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進步早日升職加薪2022-04-04
本篇文章主要介紹了golang常用手冊之切片(Slice)原理，小編覺得挺不錯的，現(xiàn)在分享給大家，也給大家做個參考。一起跟隨小編過來看看吧2017-12-12
Golang中函數(shù)(Function)和方法(Method)的區(qū)別詳解
在Golang中，大家必然會頻繁使用到函數(shù)（Function）和方法（Method），但是有的同學可能并沒有注意過函數(shù)和方法的異同點，函數(shù)和方法都是用來執(zhí)行特定任務的代碼塊，雖然很相似，但也有很大的區(qū)別，所以本文將詳細講解函數(shù)和方法的定義以及它們的異同點2023-07-07
使用client-go工具調用kubernetes API接口的教程詳解(v1.17版本)
這篇文章主要介紹了使用client-go工具調kubernetes API接口(v1.17版本),本文通過圖文實例相結合給大家介紹的非常詳細，對大家的學習或工作具有一定的參考借鑒價值，需要的朋友可以參考下2021-08-08
前面我們完成了最麻煩的數(shù)據(jù)層的單元測試，今天我們來看看單元測試中最容易做的一層，數(shù)據(jù)邏輯層，也就是我們通常說的 service 或者 biz 等2023-03-03
etcd是近幾年比較火熱的一個開源的、分布式的鍵值對數(shù)據(jù)存儲系統(tǒng)，本文將介紹如何利用Etcd實現(xiàn)分布式鎖，感興趣的小伙伴可以跟隨小編一起了解一下2023-05-05