在Golang中实现循环链表

在Golang中实现循环链表

什么是循环链表

循环链表是一种特殊的链表，它的最后一个节点指向头部节点，形成一个闭环。循环链表可以在链表中插入、删除、遍历节点。

为什么使用循环链表

相对于标准链表，循环链表的好处是可以在最后一个节点处加入新节点来代替头节点，而不用遍历整个链表。

循环链表可以用于循环播放媒体文件、循环赛制比赛、斗地主的轮流出牌等等场景。

在Golang中实现循环链表

package main

import (
    "fmt"
)

type Node struct {
    value int
    next  *Node
}

type CircularLinkedList struct {
    head *Node
    tail *Node
}

func (list *CircularLinkedList) AddNode(value int) {
    node := &Node{value: value}

    if list.head == nil {
        list.head = node
        list.tail = node
        list.tail.next = list.head
        return
    }

    list.tail.next = node
    node.next = list.head
    list.tail = node
}

func (list *CircularLinkedList) RemoveNode(value int) {
    if list.head.value == value {
        list.head = list.head.next
        list.tail.next = list.head
        return
    }

    current := list.head
    for current.next != list.head {
        if current.next.value == value {
            current.next = current.next.next
            return
        }
        current = current.next
    }
}

func (list *CircularLinkedList) Traverse() {
    if list.head == nil {
        return
    }

    current := list.head
    for current.next != list.head {
        fmt.Printf("%d ", current.value)
        current = current.next
    }
    fmt.Printf("%d\n", current.value)
}

func main() {
    list := &CircularLinkedList{}
    list.AddNode(1)
    list.AddNode(2)
    list.AddNode(3)
    list.AddNode(4)

    list.Traverse() // output: 1 2 3 4

    list.RemoveNode(2)

    list.Traverse() // output: 1 3 4
}

AddNode

RemoveNode

Traversevalue

结论

在Golang中实现循环链表是非常容易的。循环链表比标准链表更加灵活，能够在最后一个节点加入新节点，代替头节点，同时也能够删除链表节点，遍历节点等操作。我们需要根据具体的场景，选择合适的数据结构来解决问题。