嘿，DEV.to 社群！
這是我的資料結構和演算法系列的一部分。在本文中，我們將實作單鍊錶，然後在本系列的下一篇文章中，我將使用 Go 實作其他類型的鍊錶。
要實作單鍊錶，我們需要結構、節點和單鍊錶本身。但在開始編碼之前，我喜歡這樣組織我的程式碼：
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
}
函數的作用如下：
現在我們有了鍊錶和節點定義，我們可以在 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 電子書：
如果您有任何問題或建議，請隨時與我聯繫。
以上是Go 中的單鍊錶實現的詳細內容。更多資訊請關注PHP中文網其他相關文章！
