一、鍊錶簡介
鍊錶是一種資料結構，它由節點組成，每個節點包含資料和指向下一個節點的指標。相對於數組，鍊錶具有動態擴展的優勢，因為它不需要一開始就分配一塊連續的記憶體空間。鍊錶分為單向鍊錶、雙向鍊錶和循環鍊錶等多種類型。
在本文中，我們將討論 golang 中單向鍊錶的底層實作。
二、單向鍊錶的實作
在 golang 中，單向鍊錶的底層實作採用指標來建構節點之間的關係。每個節點定義如下：
type Node struct {
val interface{}
next *Node
}其中 val 表示節點的值，next 表示指向下一個節點的指標。單向鍊錶定義如下：
type SinglyLinkedList struct {
head *Node
}其中 head 表示鍊錶的頭節點，也就是第一個節點。
接下來，我們將實作鍊錶的常見操作，包括插入、刪除、尋找和遍歷。
1、插入操作
我們先介紹兩種插入操作：在鍊錶頭插入和在鍊錶末端插入。
在鍊錶頭插入操作如下：
func (l *SinglyLinkedList) InsertAtHead(val interface{}) {
node := &Node{val: val}
node.next = l.head
l.head = node
}建立一個新節點node，將節點的值設為val#，然後將其指向原頭節點l.head，最後更新l.head 指向新節點即可。
在鍊錶末端插入操作如下：
func (l *SinglyLinkedList) InsertAtTail(val interface{}) {
node := &Node{val: val}
if l.head == nil {
l.head = node
} else {
curr := l.head
for curr.next != nil {
curr = curr.next
}
curr.next = node
}
}先建立一個新節點 node，如果鍊錶為空，則將新節點設為頭節點。否則，從頭節點開始遍歷鍊錶，直到找到最後一個節點 curr.next == nil，將其 next 指向新節點即可。
2、刪除操作
刪除操作包括刪除一個指定節點和刪除鍊錶中的所有指定節點（相同節點值）。
刪除指定節點操作如下：
func (l *SinglyLinkedList) DeleteNode(node *Node) {
curr := l.head
if curr == node {
l.head = curr.next
return
}
for curr.next != nil {
if curr.next == node {
curr.next = curr.next.next
return
}
curr = curr.next
}
}若要刪除的節點是頭節點，則直接將 l.head 指向其下一個節點即可。否則從頭節點開始遍歷鍊錶，找到要刪除的節點（curr.next == node），將其 next 指向其下一個節點即可。
刪除鍊錶中的所有指定節點操作如下：
func (l *SinglyLinkedList) DeleteNodes(val interface{}) {
for l.head != nil && l.head.val == val {
l.head = l.head.next
}
curr := l.head
for curr != nil {
for curr.next != nil && curr.next.val == val {
curr.next = curr.next.next
}
curr = curr.next
}
}若頭節點的值為 val，則依序刪除指定節點。接著從頭節點開始遍歷鍊錶，依序刪除相同值的節點即可。
3、尋找操作
尋找操作主要有兩種方式：透過指定節點值來尋找節點和尋找該節點在鍊錶中的索引。
透過指定節點值來尋找節點操作如下：
func (l *SinglyLinkedList) FindNode(val interface{}) *Node {
curr := l.head
for curr != nil {
if curr.val == val {
return curr
}
curr = curr.next
}
return nil
}從頭節點開始遍歷鍊錶，依序比較節點的值與指定值val#，一旦匹配則傳回該節點，否則返回nil。
尋找該節點在鍊錶中的索引操作如下：
func (l *SinglyLinkedList) FindIndex(node *Node) int {
curr := l.head
index := 0
for curr != nil {
if curr == node {
return index
}
curr = curr.next
index++
}
return -1
}從頭節點開始遍歷鍊錶，依序比較節點是否與指定節點node 相同，如果相同，則傳回該節點所在的索引，否則傳回-1。
4、遍歷操作
遍歷操作主要有兩種方式：遍歷所有節點和遍歷所有節點的值。
遍歷所有節點操作如下：
func (l *SinglyLinkedList) Traverse() []*Node {
nodes := make([]*Node, 0)
curr := l.head
for curr != nil {
nodes = append(nodes, curr)
curr = curr.next
}
return nodes
}從頭節點開始遍歷鍊錶，將所有節點依序加入 nodes 切片中，並傳回該切片。
遍歷所有節點的值操作如下：
func (l *SinglyLinkedList) TraverseValues() []interface{} {
values := make([]interface{}, 0)
curr := l.head
for curr != nil {
values = append(values, curr.val)
curr = curr.next
}
return values
}從頭節點開始遍歷鍊錶，將所有節點的值依序加入 values 切片中，並傳回該切片。
三、總結
在 golang 中，單向鍊錶的底層實作採用指標來建構節點之間的關係。透過實現插入、刪除、查找和遍歷等常見操作，我們更了解鍊錶的本質和優勢，也更能理解 golang 在底層如何實現鍊錶的。在實際開發中，可以將鍊錶應用於許多場景，例如 LRU 快取、反轉鍊錶等。
以上是golang鍊錶底層實現的詳細內容。更多資訊請關注PHP中文網其他相關文章！
