golang鍊錶底層實現

一、鍊錶簡介

鍊錶是一種資料結構，它由節點組成，每個節點包含資料和指向下一個節點的指標。相對於數組，鍊錶具有動態擴展的優勢，因為它不需要一開始就分配一塊連續的記憶體空間。鍊錶分為單向鍊錶、雙向鍊錶和循環鍊錶等多種類型。

在本文中，我們將討論 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中文網其他相關文章！