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方法时，将输出链表的内容：