一、什麼是迴圈鏈表 迴圈鏈表的節點形成一個圈。把單鏈表的尾巴指向開頭形成單迴圈鏈表。把雙向鏈表的尾巴與開頭鏈接起來就形成雙向迴圈鏈表。使用迴圈鏈表可以不斷的繞圈尋找所需要的數據,而不需要像單鏈表那樣每次都從開頭開始尋找,可以提高查詢的效率。 今天大衛哥先實現一個單向迴圈鏈表,雙向迴圈鏈表的實現就交給 ...
一、什麼是迴圈鏈表
迴圈鏈表的節點形成一個圈。把單鏈表的尾巴指向開頭形成單迴圈鏈表。把雙向鏈表的尾巴與開頭鏈接起來就形成雙向迴圈鏈表。使用迴圈鏈表可以不斷的繞圈尋找所需要的數據,而不需要像單鏈表那樣每次都從開頭開始尋找,可以提高查詢的效率。
今天大衛哥先實現一個單向迴圈鏈表,雙向迴圈鏈表的實現就交給大家了。
二、單向迴圈鏈表的Go實現
1、節點
單向迴圈鏈表的節點和單鏈表的實現是類似的,不過為了區別,我們取了不同名字。
type CNode struct {
data Object
next *CNode
}
2、單向迴圈鏈表
單向迴圈鏈表車隊由5節車廂組成,1號車是車頭。為了表示這種關係,大衛哥用下麵的結構體來承載。
type CList struct {
size uint64 // 車廂數量
head *CNode // 車頭
}
三、介面說明及實現
1、Init初始化
大衛哥是個乾脆的人,初始化的理由直接看前面幾節。這次直接上代碼。
func (cList *CList) Init() {
lst := *cList
lst.size = 0 // 沒車廂
lst.head = nil // 沒車頭
}
2、Append添加數據
將數據添加到鏈表的尾部。
func (cList *CList) Append(data Object) bool {
node := new(CNode)
(*node).data = data // 安排一個新車廂,裝上data
if cList.GetSize() == 0 {
(*cList).head = node // 第一輛車,直接作為車頭
} else {
item := cList.GetHead() // 找到車尾
for ; (*item).next != cList.GetHead(); item = (*item).next {}
(*item).next = node // 把新車廂掛到車尾
}
(*node).next = (*cList).head // 車尾再掛上車頭
(*cList).size++
return true
}
3、InsertNext節點後面插入數據
在當前節點的後面,插入新的節點。
func (cList *CList) InsertNext(elmt *CNode, data Object) bool {
if elmt == nil {
return false
}
node := new(CNode) // 安排一個新車廂,裝上data
(*node).data = data
(*node).next = (*elmt).next // elmt後面車廂,掛在新車廂後面
(*elmt).next = node // elmt後面掛上新車廂
(cList).size++
return true
}
4、Remove刪除節點
func (cList *CList) Remove(elmt *CNode) Object {
if elmt == nil {
return false
}
item := cList.GetHead() // 找到elmt的前面一節車廂
for ; (*item).next != elmt; item = (*item).next {}
(*item).next = (*elmt).next // 將前面一節車廂的繩索直接掛到後面一節車廂
(*cList).size--
return elmt.GetData() // 返回elmt車廂裝的貨物
}
5、GetHead獲取鏈表開頭
func (cList *CList) GetHead() *CNode {
return (*cList).head
}
6、GetSize獲取鏈表節點數量
func (cList *CList) GetSize() uint64 {
return (*cList).size
}
7、GetData獲取節點裝的數據
GetData是節點的方法,獲取車廂里裝的貨物。
func (node *CNode) GetData() Object {
return (*node).data
}
8、GetNext獲取下一個節點
和GetData一樣是節點的方法,用於獲取下一個車廂。
func (node *CNode) GetNext() *CNode {
return (*node).next
}
四、小結
鏈表內容就此結束了,下麵一章大衛哥將講講棧和隊列,大衛哥將用鏈表實現。