golang 链表|极客笔记

golang 链表

1. 什么是链表

链表是一种常见的数据结构，它是一种线性表，但并不按线性的顺序存储数据，而是每个节点指向下一个节点，形成一个链式结构。

链表由节点组成，每个节点包含两部分：数据域和指针域。数据域用来存储数据，指针域用来指向下一个节点。

链表有多种类型，如单链表、双向链表、循环链表等。其中，最常见的是单链表，也是我们在本文中重点讲解的内容。

2. 单链表的定义

在 golang 中，可以通过定义结构体来表示节点和链表。下面是一个简单的单链表的定义：

package main

import "fmt"

type Node struct {
    data int
    next *Node
}

type LinkedList struct {
    head *Node
}

func main() {
    // 创建一个新的链表
    list := LinkedList{}

    // 在链表头部插入节点
    list.insertAtBeginning(1)

    // 在链表尾部插入节点
    list.insertAtEnd(2)

    // 打印链表中的所有节点
    list.printList()
}

// 在链表头部插入节点
func (ll *LinkedList) insertAtBeginning(data int) {
    newNode := &Node{data: data}
    newNode.next = ll.head
    ll.head = newNode
}

// 在链表尾部插入节点
func (ll *LinkedList) insertAtEnd(data int) {
    newNode := &Node{data: data}

    if ll.head == nil {
        ll.head = newNode
        return
    }

    last := ll.head
    for last.next != nil {
        last = last.next
    }
    last.next = newNode
}

// 打印链表中的所有节点
func (ll *LinkedList) printList() {
    curr := ll.head
    for curr != nil {
        fmt.Printf("%d -> ", curr.data)
        curr = curr.next
    }
    fmt.Println("nil")
}

在上面的代码中，我们定义了一个 Node 结构体表示链表的节点，其中 data 是节点的数据域，next 是指向下一个节点的指针。

然后，我们定义了一个 LinkedList 结构体表示链表本身，其中 head 是指向链表头部的指针。

在 main 函数中，我们创建了一个新的链表 list，并依次在链表头部和尾部插入了两个节点。最后，我们打印链表中的所有节点。

3. 单链表的操作

3.1. 插入节点

在单链表中，插入节点有两种情况：在链表头部插入节点和在链表尾部插入节点。我们已经在上面的代码中实现了这两种操作。

在链表头部插入节点：新节点的 next 指针指向原来的头节点，然后将头指针指向新节点即可。
在链表尾部插入节点：遍历整个链表，找到最后一个节点，然后将最后一个节点的 next 指针指向新节点。

3.2. 删除节点

在单链表中，删除节点也有两种情况：删除头节点和删除特定节点。下面是一个示例代码：

// 删除头节点
func (ll *LinkedList) deleteAtBeginning() {
    if ll.head == nil {
        return
    }
    ll.head = ll.head.next
}

// 删除特定节点
func (ll *LinkedList) deleteNode(data int) {
    curr := ll.head

    if curr.data == data {
        ll.head = curr.next
        return
    }

    for curr.next != nil {
        if curr.next.data == data {
            curr.next = curr.next.next
            return
        }
        curr = curr.next
    }
}

在上面的代码中，我们定义了两个方法：deleteAtBeginning 用于删除头节点，deleteNode 用于删除特定节点。删除头节点很简单，只需要将头指针指向下一个节点即可。删除特定节点需要遍历链表找到需要删除的节点，然后将该节点的前一个节点的 next 指针指向需要删除节点的下一个节点。