Golang 链表|极客教程

Golang 链表

链表是一种常见的数据结构，它由一系列节点组成，其中每个节点都包含数据以及指向下一个节点的指针。链表与数组不同，链表中的节点在内存中不是连续存储的，而是通过指针进行连接。在 Golang 中，我们可以使用结构体来实现链表。

定义节点结构体

首先，我们需要定义一个节点结构体，用来表示链表中的每个节点。

package main

import "fmt"

type Node struct {
    data int
    next *Node
}

func newNode(data int) *Node {
    return &Node{data: data}
}

func main() {
    node := newNode(10)
    fmt.Println(node.data)
}

在上面的示例中，我们定义了一个包含 data 和 next 两个字段的节点结构体。data 用来存储节点的数据，next 则用来指向下一个节点。我们还定义了一个 newNode 函数来创建新节点，并在 main 函数中演示了如何使用该函数创建节点并访问数据。运行上面的代码会输出 10，表示成功创建了一个节点并访问了其数据。

定义链表结构体

接下来，我们需要定义一个链表结构体，用来管理链表中的所有节点。

type LinkedList struct {
    head *Node
}

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

func (l *LinkedList) append(data int) {
    newNode := newNode(data)
    if l.head == nil {
        l.head = newNode
    } else {
        current := l.head
        for current.next != nil {
            current = current.next
        }
        current.next = newNode
    }
}

func (l *LinkedList) printList() {
    current := l.head
    for current != nil {
        fmt.Print(current.data, " ")
        current = current.next
    }
    fmt.Println()
}

func main() {
    list := newLinkedList()
    list.append(10)
    list.append(20)
    list.append(30)
    list.printList()
}

在上面的示例中，我们定义了一个包含 head 字段的链表结构体，其中 head 指向链表的第一个节点。我们还定义了一个 newLinkedList 函数来创建新链表，以及 append 和 printList 方法来向链表中追加节点和打印链表中的所有节点。在 main 函数中，我们演示了如何创建一个新链表并向其中添加多个节点，最后打印整个链表。运行上面的代码会输出 10 20 30，表示成功创建了一个链表，并向其中添加了三个节点。

实现链表的基本操作

除了追加节点之外，链表还支持其他基本操作，比如插入节点、删除节点等。

func (l *LinkedList) insertAt(index int, data int) {
    if index < 0 {
        fmt.Println("Index out of range")
        return
    }

    newNode := newNode(data)
    if index == 0 {
        newNode.next = l.head
        l.head = newNode
    } else {
        current := l.head
        for i := 0; i < index-1 && current != nil; i++ {
            current = current.next
        }
        if current == nil {
            fmt.Println("Index out of range")
            return
        }
        newNode.next = current.next
        current.next = newNode
    }
}

func (l *LinkedList) deleteAt(index int) {
    if index < 0 {
        fmt.Println("Index out of range")
        return
    }

    if index == 0 {
        if l.head == nil {
            fmt.Println("Index out of range")
            return
        }
        l.head = l.head.next
    } else {
        current := l.head
        for i := 0; i < index-1 && current != nil; i++ {
            current = current.next
        }
        if current == nil || current.next == nil {
            fmt.Println("Index out of range")
            return
        }
        current.next = current.next.next
    }
}

func main() {
    list := newLinkedList()
    list.append(10)
    list.append(20)
    list.append(30)

    list.insertAt(1, 15)
    list.printList()

    list.deleteAt(2)
    list.printList()
}

在上面的示例中，我们分别实现了 insertAt 和 deleteAt 方法，用来在指定位置插入和删除节点。在 main 函数中，我们演示了如何创建一个新链表并向其中添加三个节点，然后在第一个节点后插入一个新节点，再删除第三个节点。运行上面的代码会输出 10 15 20 30 和 10 15 30，表示我们成功实现了链表的插入和删除操作。