golang實作雙向鍊錶-Golang-PHP中文網

雙向鍊錶（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方法時，將輸出鍊錶的內容：