Go?語言數(shù)據(jù)結(jié)構(gòu)如何實現(xiàn)抄一個list示例詳解
前言
閑來無事，自己實現(xiàn)一個 Go提供的list包
- list是Go提供的一個內(nèi)置的包
- 內(nèi)部就是實現(xiàn)了一個雙向循環(huán)鏈表以及各種API
目標明確：就是實現(xiàn)一個雙向循環(huán)鏈表
list是個啥
在開始做之前，還是要先了解一下鏈表這個數(shù)據(jù)結(jié)構(gòu) ，長話短說：
- 線性表的鏈式存儲結(jié)構(gòu)稱為鏈表，如:
a.next = b a.prev = c b.next = c b.prev = a c.next = a c.prev = b
這就是一個雙向循環(huán)鏈表
- 鏈表可以提升存儲空間的利用率，實現(xiàn)了存儲空間動態(tài)管理的鏈式存儲結(jié)構(gòu)
接下來，我們來看看Go官方都為這個list提供了哪些操作，我們逐一實現(xiàn)
- New：創(chuàng)建一個鏈表
- Init：初始化一個鏈表
- Back：返回鏈表中的最后一個元素
- Front：返回鏈表中的第一個元素
- InsertAfter(e,at)：將e加入at元素后
- InsertBefore(e,at)：將e加入at元素前
- Len：返回list的長度
- PushBack(e)：將e成為鏈表的最后一個元素
- PushFront(e)：將e成為鏈表的第一個元素
- Remove(e)：將list上的e刪除
list結(jié)構(gòu)
定義list結(jié)構(gòu)，以及l(fā)ist內(nèi)部node節(jié)點的結(jié)構(gòu)，這里采用struct實現(xiàn)
type Element struct {
prev, next *Element
Value any
}
type List struct {
root Element
len int
}
Init & New
Init就是提供初始化一個環(huán)鏈表的方法，并返回這個環(huán)形鏈表
之所以把 Init 和 New 放在一起，是因為在 New 函數(shù)中其實就是對 Init 的一層包裝，這樣就可以實現(xiàn)Go中的包名.New方法，比如：errors.New()
// 初始化一個 環(huán)list
func (list *List) Init() *List {
// 形成環(huán)
list.root.next = &list.root
list.root.prev = &list.root
list.len = 0
return list
}
func NewList() *List {
return new(List).Init()
}
InsertAfter & InsertBefore & PushBack & PushFront
這兩個方法的作用類似，就是將 e 插入到 at 的后/前位置
這里我們先看一個圖：
這個圖片就是一個雙向環(huán)形鏈表，我們要在這個里面進行插入元素操作，比如，我們要插入 e 到 e1 前面我們應(yīng)該怎么做？
- 將e的下一個變?yōu)閑1：e.next = e1
- 將e的上一個變?yōu)閑1的上一個：e.prev = e1.prev
- 將e的上一個的下一個變?yōu)樽约海篹.prev.next = e
- 將e的下一個的上一個變?yōu)樽约海篹.next.prev = e
這樣就完成了插入，回到方法實現(xiàn)上，一個是插入之后，一個插入之前，那么我們是不是可以看作是相同操作，其實都已插入操作，只是位置的變化。
這時候想象一下，比如讓你 e 插入 at 之前，但是只提供了，參數(shù)1插入?yún)?shù)2后面的操作，如何辦到呢？
將 e 插入到 at 的前一個的后面，是不是就ok了，就相當于自己讓別人插個隊，你在我前面的后面站就行了
// Insert 插入：將 currentElement 插入至 originElement 后
func (list *List) Insert(currentElement, originElement *Element) *Element {
currentElement.next = originElement.next
currentElement.prev = originElement
currentElement.prev.next = currentElement
currentElement.next.prev = currentElement
list.len++
return currentElement
}
// InsertAfter 插入在之后
func (list *List) InsertAfter(currentElement, originElement *Element) *Element {
return list.Insert(currentElement, originElement)
}
// InsertBefore 插入在之前
func (list *List) InsertBefore(currentElement, originElement *Element) *Element {
return list.Insert(currentElement, originElement.prev)
}
這樣一來，好像把 PushBack 和 PushFront都實現(xiàn)了，這就是封裝的好處
// PushBack 插入一個元素在最后
func (list *List) PushBack(originElement *Element) *Element {
list.InsertBefore(originElement, &list.root)
return originElement
}
// PushFront 插入一個元素在最前
func (list *List) PushFront(originElement *Element) *Element {
list.InsertAfter(originElement, &list.root)
return originElement
}
Back & Front
這兩個方式抽象上說，也是一樣的功能，一個是返回鏈表最后一個，另一個是返回鏈表第一個，因為這里提供了頭結(jié)點，所以特別簡單
最后一個節(jié)點 = 頭結(jié)點.prev
第一個節(jié)點 = 頭結(jié)點.next
// Back 返回最后一個元素
func (list *List) Back() *Element {
if list.len == 0 {
return nil
}
// 頭結(jié)點的上一個就是最后一個
return list.root.prev
}
// Front 返回第一個元素
func (list *List) Front() *Element {
if list.len == 0 {
return nil
}
// 頭結(jié)點的下一個就是第一個元素
return list.root.next
}
Remove
Remove方法就是提供了，刪除鏈表上的某個元素，怎么樣才能刪除某個節(jié)點呢，本質(zhì)也就是讓前后的節(jié)點相互鏈表，我就被排擠出來了，這樣就可以實現(xiàn)刪除
- 將要刪除的元素 e.next.prev = e.prev
- 將要刪除的元素 e.prev.next = e.next
// Remove 刪除某個元素
func (list *List) Remove(originElement *Element) (any,error) {
if originElement == &list.root {
return nil, errors.New("the origin Element can not be list.root")
}
for e := list.root.next; e != &list.root; e = e.next {
if e == originElement {
e.prev.next = e.next
e.next.prev = e.prev
return e.Value, nil
} else {
continue
}
}
return nil, errors.New("the origin Element dose not belong to the list")
}
總結(jié)
- 鏈表可以實現(xiàn)存儲空間動態(tài)管理，它是一個鏈式存儲結(jié)構(gòu)
- 封裝的代碼更具靈活性
以上就是Go 語言數(shù)據(jù)結(jié)構(gòu)如何實現(xiàn)抄一個list示例詳解的詳細內(nèi)容，更多關(guān)于Go 語言數(shù)據(jù)結(jié)構(gòu)list的資料請關(guān)注腳本之家其它相關(guān)文章！
- go?sync?Waitgroup數(shù)據(jù)結(jié)構(gòu)實現(xiàn)基本操作詳解
- Golang迭代如何在Go中循環(huán)數(shù)據(jù)結(jié)構(gòu)使用詳解
- Go 語言數(shù)據(jù)結(jié)構(gòu)之雙鏈表學習教程
- Go語言數(shù)據(jù)結(jié)構(gòu)之希爾排序示例詳解
- Go 數(shù)據(jù)結(jié)構(gòu)之堆排序示例詳解
- Go語言數(shù)據(jù)結(jié)構(gòu)之選擇排序示例詳解
- Go語言數(shù)據(jù)結(jié)構(gòu)之插入排序示例詳解
- go數(shù)據(jù)結(jié)構(gòu)和算法BitMap原理及實現(xiàn)示例
相關(guān)文章
這篇文章主要介紹了學習GO編程必備知識匯總的相關(guān)資料,需要的朋友可以參考下2016-07-07
本文主要介紹了golang redis中Pipeline通道的使用詳解，文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值，需要的朋友們下面隨著小編來一起學習學習吧2022-06-06
這篇文章主要介紹了Go語言中的range用法,實例分析了range的功能與使用技巧,具有一定參考借鑒價值,需要的朋友可以參考下2015-02-02
這篇文章主要為大家詳細介紹了Golang實現(xiàn)斷點續(xù)傳、復制文件功能，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下2022-07-07
GoFrame的gdb對查詢結(jié)果的緩存處理是不是非常的優(yōu)雅。尤其是*gcache.Cache對象采用了適配器設(shè)計模式，可以輕松實現(xiàn)從單進程內(nèi)存緩存切換為分布式的Redis緩存，本文重點給大家介紹GoFrame 如何優(yōu)雅的緩存查詢結(jié)果，感興趣的朋友一起看看吧2022-06-06
RPC指(Remote Procedure Call Protocol)遠程過程調(diào)用協(xié)議。本文將實現(xiàn)利用Golang進行rpc調(diào)用(只實現(xiàn)一個rpc框架基本的功能，不對性能做保證)，需要的可以參考一下2023-03-03
這篇文章主要為大家介紹了Go語言如何處理HTTP身份驗證教程示例,有需要的朋友可以借鑒參考下,希望能夠有所幫助,祝大家多多進步,早日升職加薪2024-01-01
這篇文章主要給大家介紹了關(guān)于golang模擬實現(xiàn)帶超時的信號量的相關(guān)資料，文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值，需要的朋友們下面跟著小編來一起學習學習吧。2017-09-09
go-micro集成RabbitMQ實戰(zhàn)和原理詳解
本文主要介紹go-micro使用RabbitMQ收發(fā)數(shù)據(jù)的方法和原理，文中通過示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下2022-05-05
這篇文章主要介紹了Go實現(xiàn)線程池(工作池)的兩種方式實例詳解,需要的朋友可以參考下2022-04-04