golang實作雙向鍊錶

雙向鍊錶（Doubly linked list）是一種常用的資料結構，它使得我們可以在 O(1) 時間複雜度內在鍊錶的任意位置執行插入、刪除或查詢操作。

在 Golang 中實作雙向鍊錶需要使用指針，因為 Golang 中的所有類型都是值類型，無法直接修改原始資料。透過指針，我們可以輕鬆地進行值的修改和傳遞，從而實現雙向鍊錶的操作。

下面是一個簡單的Golang 實作的雙向鍊錶：

package main

import "fmt"

type Node struct {
    data     int
    previous *Node
    next     *Node
}

type LinkedList struct {
    head *Node
    tail *Node
}

func (list *LinkedList) insertAtBeginning(data int) {
    newNode := &Node{
        data:     data,
        previous: nil,
        next:     nil,
    }

    if list.head == nil {
        list.head = newNode
        list.tail = newNode
        return
    }

    newNode.next = list.head
    list.head.previous = newNode
    list.head = newNode
}

func (list *LinkedList) insertAtEnd(data int) {
    newNode := &Node{
        data:     data,
        previous: nil,
        next:     nil,
    }

    if list.tail == nil {
        list.head = newNode
        list.tail = newNode
        return
    }

    newNode.previous = list.tail
    list.tail.next = newNode
    list.tail = newNode
}

func (list *LinkedList) delete(data int) bool {
    currentNode := list.head

    for currentNode != nil {
        if currentNode.data == data {
            if currentNode == list.head {
                list.head = currentNode.next
                list.head.previous = nil
            } else if currentNode == list.tail {
                list.tail = currentNode.previous
                list.tail.next = nil
            } else {
                currentNode.previous.next = currentNode.next
                currentNode.next.previous = currentNode.previous
            }

            return true
        }

        currentNode = currentNode.next
    }

    return false
}

func (list *LinkedList) display() {
    currentNode := list.head

    for currentNode != nil {
        fmt.Printf("%d ", currentNode.data)
        currentNode = currentNode.next
    }

    fmt.Println()
}

func main() {
    list := LinkedList{}

    list.insertAtEnd(1)
    list.insertAtEnd(2)
    list.insertAtEnd(3)
    list.insertAtBeginning(4)

    list.display()

    list.delete(3)

    list.display()
}

在上面的程式碼中，我們首先定義了一個Node 結構體，該結構體包含鍊錶中的每個節點所需的三個資料：data、previous 和next。其中，data 儲存節點的值，previous 儲存上一個節點的位址，next 儲存下一個節點的位址。

然後，我們定義了一個 LinkedList 結構體來表示整個鍊錶。此結構體包含鍊錶的頭指標 head 和尾指標 tail。

下面是實現雙向鍊錶所需的幾個方法：

// 在链表头部插入一个元素
func (list *LinkedList) insertAtBeginning(data int) {
    newNode := &Node{
        data:     data,
        previous: nil,
        next:     nil,
    }

    if list.head == nil {
        list.head = newNode
        list.tail = newNode
        return
    }

    newNode.next = list.head
    list.head.previous = newNode
    list.head = newNode
}

// 在链表尾部插入一个元素
func (list *LinkedList) insertAtEnd(data int) {
    newNode := &Node{
        data:     data,
        previous: nil,
        next:     nil,
    }

    if list.tail == nil {
        list.head = newNode
        list.tail = newNode
        return
    }

    newNode.previous = list.tail
    list.tail.next = newNode
    list.tail = newNode
}

// 删除链表中指定的元素
func (list *LinkedList) delete(data int) bool {
    currentNode := list.head

    for currentNode != nil {
        if currentNode.data == data {
            if currentNode == list.head {
                list.head = currentNode.next
                list.head.previous = nil
            } else if currentNode == list.tail {
                list.tail = currentNode.previous
                list.tail.next = nil
            } else {
                currentNode.previous.next = currentNode.next
                currentNode.next.previous = currentNode.previous
            }

            return true
        }

        currentNode = currentNode.next
    }

    return false
}

// 打印链表的所有元素
func (list *LinkedList) display() {
    currentNode := list.head

    for currentNode != nil {
        fmt.Printf("%d ", currentNode.data)
        currentNode = currentNode.next
    }

    fmt.Println()
}

在定義了這幾個方法後，我們可以在main 函數中實例化一個鍊錶物件並進行操作：

func main() {
    list := LinkedList{}

    list.insertAtEnd(1)
    list.insertAtEnd(2)
    list.insertAtEnd(3)
    list.insertAtBeginning(4)

    list.display()

    list.delete(3)

    list.display()
}

在上面的程式碼中，我們首先實例化了一個LinkedList 物件list，然後我們按順序插入了四個元素： 1、2、3 和4。我們在第一次呼叫display 方法時，將輸出鍊錶的內容：

4 1 2 3

接著，我們刪除了元素3，並再次呼叫display 方法，輸出鍊錶的最新內容：

4 1 2

這個簡單的Golang 實作的雙向鍊錶示範如何使用指標來建立和修改鍊錶，以及如何實作鍊錶的插入、刪除和查詢等操作。如果你需要使用雙向鍊錶來建立高效的資料結構，請參考上面的程式碼來學習如何在 Golang 中實作雙向鍊錶。

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