双向链表（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中文网其他相关文章！
