Go 中的單鍊錶實現

嘿，DEV.to 社群！

這是我的資料結構和演算法系列的一部分。在本文中，我們將實作單鍊錶，然後在本系列的下一篇文章中，我將使用 Go 實作其他類型的鍊錶。

圖片來源：GeeksforGeeks

要實作單鍊錶，我們需要結構、節點和單鍊錶本身。但在開始編碼之前，我喜歡這樣組織我的程式碼：

project
├── singly_linked_list
│   ├── node.go
│   └── list.go
└── main.go

節點

節點僅以其最簡單的形式保存資料和指向下一個節點的指標。因此，這是我們將用作節點的結構（在 node.go 檔案中）：

type SinglyNode struct {
    data interface{}
    next *SinglyNode
}

我們使用 interface{} 作為結構中資料的資料類型，因此我們可以在節點內儲存我們想要的任何資料。

然後我們應該定義一些方法來利用我們剛剛建立的節點結構。

func NewSinglyNode(data interface{}) *SinglyNode {
    return &SinglyNode{data: data}
}

如果您習慣了物件導向語言，您很可能會熟悉建構函式是什麼。由於 Go 不是物件導向的語言，因此沒有類，但根據 Go 世界的一些約定，我們通常會建立一個以 New 一詞為前綴的函數。但請記住，在 OOP 語言中 new 是一個特殊的關鍵字，意味著建立一個物件。這裡的 New 只是一個名稱前綴，僅此而已。

NewSinglyNode 函數只接收一個名為 data 的介面{}類型的參數，並傳回一個 SinglyNode 的指標。

接下來，我們為節點定義一些 getter 和 setter：

func (n *SinglyNode) SetData(data interface{}) {
    n.data = data
}

func (n *SinglyNode) SetNext(next *SinglyNode) {
    n.next = next
}

func (n *SinglyNode) GetData() interface{} {
    return n.data
}

func (n *SinglyNode) GetNext() (*SinglyNode, error) {
    if n.next == nil {
        return nil, errors.New("no next node")
    }
    return n.next, nil
}

SetData、Setnext 和 GetData 幾乎是不言自明的。 GetNext 傳回兩個值，一個指向下一個 SinglyNode 的指針，如果沒有下一個節點，則傳回一個錯誤。

這是我總是喜歡添加的額外函數，這樣我總是可以知道我的結構的字串表示形式是：

func (n *SinglyNode) ToString() string {
    return n.data.(string)
}

清單

現在我們已經完成了節點，我們應該實作列表本身。單鍊錶將第一個節點作為頭，而根據我自己的喜好，另外兩個名為「最後」的資料保存最後一個節點，以及一個國家屬性，該屬性保存添加到列表中的節點的計數。

這是 list.go 檔案的第一行：

type SinglyLinkedList struct {
    head  *SinglyNode
    last  *SinglyNode
    count int
}

顯然，一個類似建構子的函式可以輕鬆地建立 SinglyLinkedList：

func NewSinglyLinkedList() *SinglyLinkedList {
    return &SinglyLinkedList{}
}

鍊錶中最重要的函數是新增節點。這是我對這樣一個函數的實作：

func (l *SinglyLinkedList) AttachNode(node *SinglyNode) {
    if l.head == nil {
        l.head = node
    } else {
        l.last.SetNext(node)
    }
    l.last = node
    l.count++
}

函數的作用如下：

• 檢查鍊錶頭是否為空，如果為空則將接收到的節點設定為鍊錶頭。
• 如果頭不為空，則將接收到的節點設定為最後一個節點的下一個屬性。
• 無論之前發生了什麼，當前節點都應該是最後一個節點，因此下次新增節點時，它可以設定為清單中最後一個節點的下一個節點。
• 將計數加一。

這是一個接收資料並建立節點並將其傳遞給 AttachNode 函數的函數：

func (l *SinglyLinkedList) Add(data interface{}) {
    l.AttachNode(NewSinglyNode(data))
}

雖然這個功能可能看起來多餘，但它可以輕鬆地將節點添加到列表中，而無需每次手動創建一個。

取得計數屬性的函數：

func (l *SinglyLinkedList) Count() int {
    return l.count
}

最後需要的函數應該會傳回鍊錶中的下一個節點：

func (l *SinglyLinkedList) GetNext() (*SinglyNode, error) {
    if l.head == nil {
        return nil, errors.New("list is empty")
    }
    return l.head, nil
}

我更喜歡將此函數命名為與為節點定義的 GetNext 函數相同的名稱。這樣做是為了提高一致性。當第一次存取鍊錶時，類型是鍊錶，因此無法存取為節點定義的函數。定義一個具有相同名稱的函數將使您能夠盡可能地使用 GetNext 來遍歷清單。

我總是傾向於添加的一個額外函數是透過索引檢索節點的函數：

func (l *SinglyLinkedList) GetByIndex(index int) (*SinglyNode, error) {
    if l.head == nil {
        return nil, errors.New("list is empty")
    }
    if index+1 > l.count {
        return nil, errors.New("index out of range")
    }
    node, _ := l.GetNext()
    for i := 0; i < index; i++ {
        node, _ = node.GetNext()
    }
    return node, nil
}

函數的作用如下：

• 檢查頭部是否為空回傳錯誤
• 檢查索引 1 是否大於清單的計數以傳回錯誤。我們檢查索引 1 而不是索引，因為我們認為索引從 0 開始就像陣列一樣。
• 將l.GetNext() 指派給名為node 的變數（忽略帶有_ 的錯誤），然後循環查找比提供的索引少的一個，因為我們已經將第一個節點儲存在節點變數中，分配目前節點的下一個節點節點再次成為節點。
• 傳回沒有錯誤的遍歷節點。

測試

現在我們有了鍊錶和節點定義，我們可以在 main.go 檔案中測試它，如下所示：

func main() {
    list := singly_linked_list.NewSinglyLinkedList()

    list.Add("One")
    list.Add("Two")
    list.Add("Three")

    firstNode, err := list.GetNext()
    if err != nil {
        panic(err)
    }

    secondNode, err := firstNode.GetNext()
    if err != nil {
        panic(err)
    }

    thirdNode, err := secondNode.GetNext()
    if err != nil {
        panic(err)
    }

    println(firstNode.ToString())  // One
    println(secondNode.ToString()) // Two
    println(thirdNode.ToString())  // Three
}

或使用 GetByIndex 函數：

func main() {
    list := singly_linked_list.NewSinglyLinkedList()

    list.Add("One")
    list.Add("Two")
    list.Add("Three")

    node, err := list.GetByIndex(2)
    if err != nil {
        panic(err)
    }

    fmt.Println(node.ToString()) // Three
}

---

順便說一下！在這裡查看我的免費 Node.js Essentials 電子書：

NodeJS 重點 |免費電子書

Adnan Babakan（他/他） ・ 2020 年 9 月 11 日

＃節點 #javascript ＃圖書

如果您有任何問題或建議，請隨時與我聯繫。

以上是Go 中的單鍊錶實現的詳細內容。更多資訊請關注PHP中文網其他相關文章！