golang实现双向链表

时间：2023-05-11 03:14

双向链表（Doubly linked list）是一种常用的数据结构，它使得我们可以在 O(1) 时间复杂度内在链表的任意位置执行插入、删除或查询操作。

在 Golang 中实现双向链表需要使用指针，因为 Golang 中的所有类型都是值类型，无法直接修改原始数据。通过指针，我们可以轻松地进行值的修改和传递，从而实现双向链表的操作。

下面是一个简单的 Golang 实现的双向链表：

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