主頁 > 知識庫 > Golang中List的實現(xiàn)方法示例詳解

Golang中List的實現(xiàn)方法示例詳解

熱門標簽:惠州電銷防封電話卡 阿里云ai電話機器人 黃岡人工智能電銷機器人哪個好 濱州自動電銷機器人排名 鄭州亮點科技用的什么外呼系統(tǒng) 浙江高頻外呼系統(tǒng)多少錢一個月 建造者2地圖標注 釘釘有地圖標注功能嗎 汕頭小型外呼系統(tǒng)

前言

為了快速回顧Go基本的語法知識,打算用Go中的基本語法以及特性來實現(xiàn)一些常見的數(shù)據(jù)結(jié)構(gòu)和排序算法,通過分析如何實現(xiàn)一些基本的數(shù)據(jù)結(jié)構(gòu),可以很快學(xué)習(xí)Go的語法特性。記憶更加深刻,掌握更加迅速。這是我認為學(xué)習(xí)一門新語言入門最好的方式。這也是方便自己以后需要用Go來寫東西的一種前期準備,到時候就不用去翻一些教程了。系列博文的第一篇就從如何實現(xiàn)List開始。

需求

大家都知道基本鏈表得有以下特性:鏈表的初始化、鏈表的長度、節(jié)點的插入、刪除、查找等一些常見的基本操作,最后寫好之后,需要測試。關(guān)于測試,我之前寫過Go的系列筆記中有敘述,不再重復(fù)。

實現(xiàn)

初始化

有語言基礎(chǔ)的人都知道,鏈表是由節(jié)點連接而成,這其中在定義一個List數(shù)據(jù)結(jié)構(gòu)之外,還需要定義一個Node類型的數(shù)據(jù)結(jié)構(gòu)。先說Node類型的數(shù)據(jù)結(jié)構(gòu),首先List按照正常的設(shè)計應(yīng)該是可以存儲基本類型的數(shù)據(jù)的,這就要求Node中的Value至于的類型不能固定,此時你可能反駁道:在Java中我們不是可以傳入Int、String類型到List嗎?其實這就是在走偏了,現(xiàn)在的工作是實現(xiàn)List這種數(shù)據(jù)結(jié)構(gòu)。所以不能對其Value值域有任何類型限制,在Go中'空接口'恰好能夠滿足這種須需求。另外在List中一個Node需要兩個指針域,分別指向前后節(jié)點的地址。在Go中這種需求,可以通過 *來實現(xiàn),簡單理解為其可以存儲地址。如*Int就是int類型的地址??磳崿F(xiàn)方式:

type Node struct {
 Value interface{} 
 next, prev *Node 
}

下面就是定義List結(jié)構(gòu)體了,有了上面的分析,List結(jié)構(gòu)體的定義就很好實現(xiàn)了:

type List struct {
 root Node // 頭節(jié)點
 length int // list長度
}

那么在構(gòu)建好基本的數(shù)據(jù)結(jié)構(gòu)之后,如何去獲取一個List對象呢。先不著急實現(xiàn),想想在Java語言中怎么實現(xiàn)的:

Person p = new Man();

如上所示,首先獲取一個Man類的實例,然后p中有對象的地址/引用。從這些分析我們大概知道如何去創(chuàng)建一個list對象了,最終需要的結(jié)果就是獲取一個List的引用/地址,并且該List的長度為0。除此之外,需要處理好空List的情況:

// 返回List的指針
func New() *List {
 l := List{}// 獲取List{}的地址
 l.length = 0// list初始長度為0
 l.root.next = l.root
 l.root.prev = l.root
 return l
}

判空和長度

List的判空和獲取長度也是非常基礎(chǔ)和重要的,判斷是否為空,返回的數(shù)據(jù)類型是布爾類型的。什么情況下List是為空呢?根據(jù)前面的定義,頭節(jié)點的next指針域指向是頭結(jié)點本身的地址即為空。另外,判空函數(shù)寫好了,總不能什么類型的數(shù)據(jù)都去調(diào)用這個函數(shù),我們需要指定調(diào)用的數(shù)據(jù)類型,在本例中當(dāng)然是 List類型的了,為了方便操作,傳入一個List的地址即可。

func (l *List) IsEmpty() bool {
 return l.root.next == l.root
}

分析完畢之后,獲取list的長度就簡單很多了:

func (l *List) Length() int {
 return l.length
}

頭插和尾插

因為在定義List數(shù)據(jù)結(jié)構(gòu)的時候,就定義了一個root頭節(jié)點。所以此時,可以很方便的實現(xiàn)頭插入和尾插入??紤]能夠同時插入多個/一個Node節(jié)點,利用Go中的變長參數(shù)實現(xiàn)該特性。對插入的Node節(jié)點進行循環(huán)處理,新節(jié)點的指針域和root節(jié)點的指針域做相應(yīng)改變,具體實現(xiàn)方式以及說明在代碼中說明:

func (l *List) PushFront(elements ...interface{}) {
 for _, element := range elements {
 n := Node{Value: element} // 注釋一
 n.next = l.root.next // 新節(jié)點的next是root節(jié)點的next
 n.prev = l.root // 新節(jié)點的prev存儲的是root的地址
 l.root.next.prev = n // 原來root節(jié)點的next的prev是新節(jié)點
 l.root.next = n // 頭插法 root 之后始終是新節(jié)點
 l.length++ // list 長度加1
 }
}

注釋1處拿出來分析:結(jié)構(gòu)體初始化方式 Node{Value:element} , 是獲取結(jié)構(gòu)體地址的方式。此時需要一個地址類型的變量來存儲結(jié)構(gòu)體的地址,此時看看聲明方式為 :n這里就學(xué)習(xí)到了Go中臨時變量的聲明方式啦。并且該臨時變量不需要指明數(shù)據(jù)類型。尾插法就很簡單了,參見如下所示代碼:

func (l *List) PushBack(elements ...interface{}) {
 for _, element := range elements {
 n := Node{Value: element}
 n.next = l.root // since n is the last element, its next should be the head
 n.prev = l.root.prev // n's prev should be the tail
 l.root.prev.next = n // tail's next should be n
 l.root.prev = n // head's prev should be n
 l.length++
 }
}

查找

查找最終的效果是返回指定數(shù)值的索引,如果不存在的話返回-1即可。對于鏈表的查找是一個遍歷的過程,在此時就需要考慮遍歷的起始和終止區(qū)間了,不能越界出錯。因為是循環(huán)鏈表,終止節(jié)點也很好辦。具體代碼如下所示:

func (l *List) Find(element interface{}) int {
 index := 0
 p := l.root.next
 for p != l.root  p.Value != element {
 p = p.next
 index++
 }
 // p不是root
 if p != l.root {
 return index
 }

 return -1
}

刪除

鏈表的刪除操作邏輯很清晰,將一個Node的節(jié)點與前后節(jié)點斷開即可,同時前后節(jié)點和Node節(jié)點本身指針域也要做相應(yīng)修改,最后別忘記將鏈表的長度減少相應(yīng)長度。

func (l *List) remove(n *Node) {
 n.prev.next = n.next
 n.next.prev = n.prev
 n.next = nil
 n.prev = nil
 l.length--
}

刪除并返回List中的第一個數(shù)據(jù):

func (l *List) Lpop() interface{} {
 if l.length == 0 {
 // null的表現(xiàn)形式nil
 return nil
 }
 n := l.root.next
 l.remove(n)
 return n.Value
}

遍歷

下面normalIndex函數(shù)的作用返回一個正常邏輯的Index,例如處理好一些越界問題:

func (l *List) normalIndex(index int) int {
 if index > l.length-1 {
 index = l.length - 1
 }

 if index  -l.length {
 index = 0
 }
 // 將給定的index與length做取余處理
 index = (l.length + index) % l.length
 return index
}

如下的函數(shù)為獲取指定范圍內(nèi)的數(shù)據(jù),根據(jù)傳入的參數(shù)需要指定start和end,最后返回的應(yīng)該是一個切片或者數(shù)組,具體類型未知:

func (l *List) Range(start, end int) []interface{} {
 // 獲取正常的start和end
 start = l.normalIndex(start)
 end = l.normalIndex(end)
 // 聲明一個interface類型的數(shù)組
 res := []interface{}{}
 // 如果上下界不符合邏輯,返回空res
 if start > end {
 return res
 }
 
 sNode := l.index(start)
 eNode := l.index(end)
 // 起始點和重點遍歷
 for n := sNode; n != eNode; {
 // res的append方式
 res = append(res, n.Value)
 n = n.next
 }
 res = append(res, eNode.Value)
 return res
}

ok,以上即為Go中List的數(shù)據(jù)結(jié)構(gòu)的實現(xiàn)方式,通過本節(jié),能夠?qū)W習(xí)到許多Go的語法特性。個人認為學(xué)習(xí)編程,語法是最簡單的,應(yīng)該利用最短的時間在,最有效的掌握。

總結(jié)

以上就是這篇文章的全部內(nèi)容了,希望本文的內(nèi)容對大家的學(xué)習(xí)或者工作能帶來一定的幫助,如果有疑問大家可以留言交流,謝謝大家對腳本之家的支持。

您可能感興趣的文章:
  • 基于golang中container/list包的用法說明
  • golang使用grpc+go-kit模擬oauth認證的操作
  • golang中for range的取地址操作陷阱介紹
  • golang如何去除多余空白字符(含制表符)
  • 用golang如何替換某個文件中的字符串
  • golang正則之命名分組方式
  • 解決golang中container/list包中的坑

標簽:昭通 阿壩 駐馬店 晉中 滄州 瀘州 東營 泰安

巨人網(wǎng)絡(luò)通訊聲明:本文標題《Golang中List的實現(xiàn)方法示例詳解》,本文關(guān)鍵詞  Golang,中,List,的,實現(xiàn),方法,;如發(fā)現(xiàn)本文內(nèi)容存在版權(quán)問題,煩請?zhí)峁┫嚓P(guān)信息告之我們,我們將及時溝通與處理。本站內(nèi)容系統(tǒng)采集于網(wǎng)絡(luò),涉及言論、版權(quán)與本站無關(guān)。
  • 相關(guān)文章
  • 下面列出與本文章《Golang中List的實現(xiàn)方法示例詳解》相關(guān)的同類信息!
  • 本頁收集關(guān)于Golang中List的實現(xiàn)方法示例詳解的相關(guān)信息資訊供網(wǎng)民參考!
  • 推薦文章