详解Go语言中单链表的使用

什么是单链表

单链表（Singly Linked List）是一种常见的数据结构之一，它由一串节点组成，每个节点包含两个部分：数据部分和指向下一个节点的指针部分。

单链表的头部节点称为头节点，尾部节点称为尾节点。尾节点的指针部分指向NULL。

Go语言中单链表的实现

在Go语言中实现单链表，我们可以定义一个结构体表示链表节点，代码如下：

type ListNode struct {
    Val  int         // 数据部分
    Next *ListNode   // 指向下一个节点的指针部分
}

我们可以定义单链表的头节点，然后使用头节点来对链表进行操作（添加、删除、查找等）。

type LinkedList struct {
    Head *ListNode   // 头节点
}

Go语言单链表常见操作

初始化一个单链表

我们可以定义一个构造函数进行初始化：

func NewLinkedList() *LinkedList {
    return &LinkedList{
        Head: &ListNode{Val: 0, Next: nil},
    }
}

在链表的末尾添加一个节点

我们可以先找到链表的尾部节点，然后在尾部节点的后面添加一个新的节点。代码如下：

func (list *LinkedList) AddAtTail(val int) {
    newNode := &ListNode{
        Val:  val,
        Next: nil,
    }
    // 找到尾部节点
    tail := list.Head
    for tail.Next != nil {
        tail = tail.Next
    }
    tail.Next = newNode
}

在链表的头部添加一个节点

我们可以先创建一个新的节点，然后将新节点的指针部分指向头节点的下一个节点，最后将头节点的指针部分指向新节点。代码如下：

func (list *LinkedList) AddAtHead(val int) {
    newNode := &ListNode{
        Val:  val,
        Next: nil,
    }
    newNode.Next = list.Head.Next
    list.Head.Next = newNode
}

在链表的第index个位置插入一个节点

我们可以先找到要插入节点的位置，然后创建新的节点，将新节点的指针部分指向原来位置上的节点，最后将前一个节点的指针部分指向新节点。代码如下：

func (list *LinkedList) AddAtIndex(index int, val int) {
    newNode := &ListNode{
        Val:  val,
        Next: nil,
    }
    // 找到要插入的位置
    prev := list.Head
    for i := 0; i < index && prev != nil; i++ {
        prev = prev.Next
    }
    if prev == nil {
        return
    }
    // 将新节点插入到链表中
    newNode.Next = prev.Next
    prev.Next = newNode
}

在链表中删除一个节点

我们可以先找到要删除节点的前一个节点，然后将其指针部分指向被删除节点的下一个节点。代码如下：

func (list *LinkedList) DeleteAtIndex(index int) {
    // 找到要删除的节点的前一个节点
    prev := list.Head
    for i := 0; i < index && prev != nil; i++ {
        prev = prev.Next
    }
    if prev == nil || prev.Next == nil {
        return
    }
    // 将前一个节点的指针部分指向下一个节点
    prev.Next = prev.Next.Next
}

示例说明

示例一

我们可以按照以下步骤在Go语言中使用单链表：

1. 创建一个新的单链表

go
list := NewLinkedList()

1. 在单链表中添加节点

go
list.AddAtTail(1)
list.AddAtTail(2)
list.AddAtTail(3)
list.AddAtIndex(1, 4)
list.AddAtHead(5)

1. 删除一个节点

go
list.DeleteAtIndex(3)

最终单链表的结果为：5, 1, 4, 2

示例二

我们还可以使用单链表来实现LRU缓存淘汰算法，以下是实现代码：

type LRUCache struct {
    capacity    int
    linkedList  *LinkedList
    hashMap     map[int]*ListNode
}

func Constructor(capacity int) LRUCache {
    return LRUCache{
        capacity:   capacity,
        linkedList: NewLinkedList(),
        hashMap:    make(map[int]*ListNode),
    }
}

func (this *LRUCache) Get(key int) int {
    if _, ok := this.hashMap[key]; !ok {
        return -1
    }
    node := this.hashMap[key]
    this.linkedList.DeleteNode(node)
    this.linkedList.AddAtHead(node.Val)
    return node.Val
}

func (this *LRUCache) Put(key int, value int) {
    if _, ok := this.hashMap[key]; ok {
        node := this.hashMap[key]
        node.Val = value
        this.linkedList.DeleteNode(node)
        this.linkedList.AddAtHead(node.Val)
        return
    }
    if this.linkedList.Length() >= this.capacity {
        tail := this.linkedList.RemoveTail()
        delete(this.hashMap, tail.Val)
    }
    newNode := &ListNode{
        Val:  value,
        Next: nil,
    }
    this.linkedList.AddAtHead(value)
    this.hashMap[key] = this.linkedList.Head.Next
}

以上是Go语言中单链表的使用攻略，希望对你有所帮助。