golang 实现双向链表

发布时间:2024-12-23 01:40:32

双向链表是一种常用的数据结构，能够在O(1)的时间复杂度下实现插入、删除和查找操作。在Golang中，我们可以使用指针和结构体来实现双向链表。本文将介绍如何使用Golang编写双向链表。

定义链表节点

首先，我们需要定义一个链表节点的结构体，每个节点包含两个指针，分别指向前一个节点和后一个节点。另外，还需要一个存储数据的字段。

type Node struct {
    prev  *Node
    next  *Node
    value interface{}
}

初始化链表

接下来，我们需要定义一个链表结构体，并初始化一个空链表。链表结构体包含一个头节点和一个尾节点。

type LinkedList struct {
    head *Node
    tail *Node
}

通过初始化一个空链表，我们将头节点和尾节点都指向nil。

func NewLinkedList() *LinkedList {
    return &LinkedList{}
}

插入操作

链表的插入操作分为两种情况：在链表的头部插入和在链表的尾部插入。在头部插入时，我们只需要更新头节点的指针即可。在尾部插入时，我们需要更新尾节点的指针。

func (list *LinkedList) InsertHead(value interface{}) {
    newNode := &Node{value: value}
    if list.head == nil {
        list.head = newNode
        list.tail = newNode
    } else {
        newNode.next = list.head
        list.head.prev = newNode
        list.head = newNode
    }
}

func (list *LinkedList) InsertTail(value interface{}) {
    newNode := &Node{value: value}
    if list.tail == nil {
        list.head = newNode
        list.tail = newNode
    } else {
        newNode.prev = list.tail
        list.tail.next = newNode
        list.tail = newNode
    }
}

删除操作

链表的删除操作也分为两种情况：删除头节点和删除尾节点。删除头节点时，我们需要更新头节点的指针。删除尾节点时，我们需要更新尾节点的指针。

func (list *LinkedList) DeleteHead() (interface{}, bool) {
    if list.head == nil {
        return nil, false
    }
    value := list.head.value
    list.head = list.head.next
    if list.head == nil {
        list.tail = nil
    } else {
        list.head.prev = nil
    }
    return value, true
}

func (list *LinkedList) DeleteTail() (interface{}, bool) {
    if list.tail == nil {
        return nil, false
    }
    value := list.tail.value
    list.tail = list.tail.prev
    if list.tail == nil {
        list.head = nil
    } else {
        list.tail.next = nil
    }
    return value, true
}

遍历链表

我们可以通过遍历链表的节点，依次输出节点的值。从头节点开始遍历，直到尾节点。

func (list *LinkedList) Traverse() {
    current := list.head
    for current != nil {
        fmt.Println(current.value)
        current = current.next
    }
}