golang怎麼實現雙向鍊錶-Golang-PHP中文網

雙向鍊錶是一種常見的資料結構，它可以在元素之間建立雙向關聯，使得在鍊錶中進行插入、刪除和遍歷等操作變得非常有效率。在 Go 語言中，雙向鍊錶的實作非常簡單，本文就來介紹如何用 Go 實作雙向鍊錶。

雙向鍊錶是一種鍊式結構，它的每個節點都包含三個部分：前驅指標 prev、後繼指標 next 和資料域 data。在Go 中，我們可以定義一個struct 來表示雙向鍊錶的節點：

type ListNode struct { prev *ListNode next *ListNode data interface{} }

登入後複製

其中，prev和next分別指向目前節點的前驅和後繼節點，data則是節點儲存的資料。

要實作雙向鍊錶，我們需要定義一個LinkedList 類型，其中包含一個指向鍊錶頭節點和尾節點的指針，以及鍊錶長度size：

type LinkedList struct { head *ListNode tail *ListNode size int }

登入後複製

下面我們來逐一實現雙向鍊錶的各個操作。

插入元素

在雙向鍊錶中插入元素，主要有三種情況：

在鍊錶頭插入元素。
在鍊錶尾插入元素。
在鍊錶中間插入元素。

在 Go 中，我們可以定義一個 Insert 方法來實現上述三種情況：

func (list *LinkedList) Insert(data interface{}) { node := &ListNode{data: data} if list.head == nil { list.head = node list.tail = node } else { node.prev = list.tail list.tail.next = node list.tail = node } list.size++ }

登入後複製

首先，我們建立一個新的節點 node，儲存要插入的資料 data。如果鍊錶為空，則將新節點作為頭節點和尾節點。否則，將新節點插入到尾節點的後面，並將尾節點指標更新為新節點。最後，鍊錶長度加1。

刪除元素

與插入元素類似，刪除元素也可能涉及三種情況：

刪除鍊錶頭元素。
刪除鍊錶尾元素。
刪除鍊錶中間的元素。

下面是一個 Delete 方法的範例實作：

func (list *LinkedList) Delete(data interface{}) { node := list.find(data) if node != nil { if node.prev != nil { node.prev.next = node.next } else { list.head = node.next } if node.next != nil { node.next.prev = node.prev } else { list.tail = node.prev } list.size-- } } func (list *LinkedList) find(data interface{}) *ListNode { node := list.head for node != nil && node.data != data { node = node.next } return node }

登入後複製

首先，我們需要找到要刪除的節點 node，透過一個輔助函數 find 實作。如果找到了要刪除的節點，則需要根據節點的位置，更新前驅和後繼節點的指標。如果要刪除的節點是頭節點，則將頭節點指標更新為下一個節點；如果要刪除的節點是尾節點，則將尾節點指標更新為前一個節點。最後，將鍊錶長度減1。

遍歷元素

遍歷雙向鍊錶非常簡單，只需要從頭節點開始，沿著後繼指標 next 一直遍歷即可。反向遍歷則可以從尾節點開始，沿著前驅指標 prev 遍歷。以下是分別實現正向和反向遍歷的兩個方法：

func (list *LinkedList) Traverse() []interface{} { result := make([]interface{}, list.size) node := list.head for i := 0; i < list.size; i++ { result[i] = node.data node = node.next } return result } func (list *LinkedList) ReverseTraverse() []interface{} { result := make([]interface{}, list.size) node := list.tail for i := 0; i < list.size; i++ { result[i] = node.data node = node.prev } return result }

登入後複製

遍歷時，我們需要建立一個切片用於保存遍歷結果，然後從頭或尾節點開始，沿著指標遍歷每個節點，並將節點的資料儲存到切片中。