第三節 迴圈鏈表的Go語言實現

一、什麼是迴圈鏈表

迴圈鏈表的節點形成一個圈。把單鏈表的尾巴指向開頭形成單迴圈鏈表。把雙向鏈表的尾巴與開頭鏈接起來就形成雙向迴圈鏈表。使用迴圈鏈表可以不斷的繞圈尋找所需要的數據，而不需要像單鏈表那樣每次都從開頭開始尋找，可以提高查詢的效率。

今天大衛哥先實現一個單向迴圈鏈表，雙向迴圈鏈表的實現就交給大家了。

二、單向迴圈鏈表的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
    }

代碼下載

四、小結

鏈表內容就此結束了，下麵一章大衛哥將講講棧和隊列，大衛哥將用鏈表實現。