golang实现双向链表-Golang-PHP中文网

golang实现双向链表

王林

发布： 2023-05-10 22:37:37

原创

555人浏览过

双向链表（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。

立即学习“go语言免费学习笔记（深入）”；

下面是实现双向链表所需的几个方法：

// 在链表头部插入一个元素
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 方法时，将输出链表的内容：