golang怎么实现双向链表

PHPz

发布时间：2023-04-25 09:11:29

1117人浏览过

来源于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语言免费学习笔记（深入）”；

插入元素

向双向链表中插入元素，主要有三种情况：

在链表头插入元素。
在链表尾插入元素。
在链表中间插入元素。

在 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。

ClipDrop

Stability.AI出品的图片处理系列工具（背景移除、图片放大、打光）

下载

删除元素

与插入元素类似，删除元素也可能涉及到三种情况：

删除链表头元素。
删除链表尾元素。
删除链表中间的元素。

下面是一个 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
}

遍历时，我们需要创建一个切片用于保存遍历结果，然后从头或尾节点开始，沿着指针遍历每个节点，并将节点的数据存储到切片中。