详解Go语言单链表及其常用方法的实现

什么是单链表

单链表是一种常见的数据结构，它由一系列节点组成。每个节点分为两个部分，第一个部分存储当前节点的值，第二个部分存储下一个节点的地址。最后一个节点指向空（null）。单链表中保存的数据不存在顺序关系，且每个节点仅知道下一个节点的地址，不知道前一个节点的地址。因此，无法随机访问单链表中的元素，只能从链表的头部一个一个地遍历各个节点。

在Go语言中实现单链表

定义单链表节点的结构体

在Go语言中，可以使用结构体来定义单链表中的节点。结构体包含两个属性：Value表示当前节点存储的值，Next表示下一个节点的地址。

type ListNode struct {
    Value interface{} // 存储的值，使用interface{}可以保存任何类型的数据
    Next  *ListNode   // 下一个节点的地址
}

定义单链表结构体

定义单链表结构体，包含头结点和当前链表长度。头结点不存储任何值，仅用来标识链表的开始位置。

type LinkedList struct {
    head  *ListNode // 头结点
    count int       // 当前链表长度
}

实现单链表的初始化方法

初始化单链表时，仅需要创建一个头结点，并将链表长度设置为0。

func (list *LinkedList) Init() {
    list.head = new(ListNode) // 创建头结点
    list.count = 0           // 链表长度为0
}

实现单链表的获取长度方法

链表长度是记录在链表结构体中的一个属性，只需要返回该属性的值即可。

func (list *LinkedList) Len() int {
    return list.count
}

实现单链表的添加节点方法

链表中最常用的操作之一是添加节点。在单链表中，添加节点指的是将新节点插入到链表的末尾。

func (list *LinkedList) Append(value interface{}) {
    node := &ListNode{Value: value} // 创建新节点
    tail := list.head

    for tail.Next != nil {
        tail = tail.Next // 获取最后一个节点的地址
    }

    tail.Next = node // 将新节点添加到链表的末尾
    list.count++     // 更新链表长度
}

实现单链表的查找节点方法

在单链表中，查找节点指的是根据节点的值，从头结点开始寻找该节点。

func (list *LinkedList) Find(value interface{}) *ListNode {
    cur := list.head.Next // 从第一个节点开始查找

    for cur != nil {
        if cur.Value == value {
            return cur // 查找到节点
        }

        cur = cur.Next // 继续查找下一个节点
    }

    return nil // 没有找到节点
}

示例1：使用单链表保存任务列表

func main() {
    // 初始化单链表
    taskList := new(LinkedList)
    taskList.Init()

    // 添加任务到链表中
    taskList.Append("任务1")
    taskList.Append("任务2")
    taskList.Append("任务3")
    taskList.Append("任务4")

    // 在任务列表中查找指定任务
    task := taskList.Find("任务3")
    if task != nil {
        fmt.Println("找到任务：", task.Value)
    } else {
        fmt.Println("未找到任务")
    }
}

示例2：使用单链表实现LRU缓存

type LRUCache struct {
    cap     int           // 缓存容量
    cache   map[int]*Node // 缓存中的节点
    head    *Node         // 头结点
    tail    *Node         // 尾节点
    current int           // 当前链表长度
}

type Node struct {
    key   int  // 缓存键
    value int  // 缓存值
    prev  *Node
    next  *Node
}

func NewLRUCache(cap int) *LRUCache {
    cache := &LRUCache{
        cap:   cap,
        cache: make(map[int]*Node),
        head:  new(Node),
        tail:  new(Node),
    }

    cache.head.next = cache.tail
    cache.tail.prev = cache.head

    return cache
}

func (cache *LRUCache) Put(key int, value int) {
    node, ok := cache.cache[key]

    if !ok {
        node = &Node{key: key, value: value}
        cache.cache[key] = node
        cache.current++

        if cache.current > cache.cap {
            cache.Remove(cache.tail.prev)
        }
    } else {
        node.value = value
        cache.Remove(node)
    }

    cache.MoveToFront(node)
}

func (cache *LRUCache) Remove(node *Node) {
    node.prev.next = node.next
    node.next.prev = node.prev
    delete(cache.cache, node.key)
    cache.current--
}

func (cache *LRUCache) MoveToFront(node *Node) {
    node.prev = cache.head
    node.next = cache.head.next
    cache.head.next.prev = node
    cache.head.next = node
}

func (cache *LRUCache) Get(key int) int {
    node, ok := cache.cache[key]

    if !ok {
        return -1
    }

    cache.MoveToFront(node)

    return node.value
}

以上是单链表及其常用方法的实现。通过示例，可以看到单链表的应用非常广泛，可以用于任务列表、LRU缓存等场景。本文实现的单链表类似于Go标准库中的container/list包，读者可以自行比较并学习。