golang实现链表

使用Golang实现链表

链表简介

链表（Linked List）是由一系列“节点”组成的数据结构，每个节点包含了存储的数据和一个指向下一个节点的指针。相对于数组，链表的大小可以动态地改变，并且不需要连续的内存空间。

链表的基本操作

在Golang中，我们可以通过定义一个链表结构体来实现链表的基本操作。其中，每个节点存储的数据类型可以根据具体需求而定。下面是一个简单的示例：

type ListNode struct {
    Val  int
    Next *ListNode
}

上述代码中，ListNode结构体表示链表的节点，其中Val字段存储数据，Next字段是指向下一个节点的指针。

创建链表

要创建一个链表，我们首先需要创建一个头节点，然后依次向链表中添加节点。下面是一个示例：

func CreateLinkedList(nums []int) *ListNode {
    // 创建头节点
    head := &ListNode{}

    // 遍历nums，逐个添加节点
    curr := head
    for _, num := range nums {
        node := &ListNode{Val: num}
        curr.Next = node
        curr = curr.Next
    }

    return head.Next
}

上述代码中，我们通过遍历nums数组，逐个添加节点到链表中。最后返回链表头节点的Next字段即可。

遍历链表

遍历链表是常见的操作，我们可以通过循环来依次访问每个节点。下面是一个示例：

func TraverseLinkedList(head *ListNode) {
    curr := head
    for curr != nil {
        fmt.Println(curr.Val)
        curr = curr.Next
    }
}

上述代码中，我们从头节点开始，依次打印每个节点的值，直到当前节点为nil，表示遍历结束。

插入节点

如果要在链表的指定位置插入一个节点，我们可以找到目标位置的前一个节点，然后修改前一个节点的Next指针。下面是一个示例：

func InsertNode(prev *ListNode, val int) {
    node := &ListNode{Val: val}
    node.Next = prev.Next
    prev.Next = node
}

上述代码中，我们创建一个新节点，然后将新节点的Next指针指向前一个节点的Next指针所指向的节点。最后，将前一个节点的Next指针指向新节点即可。

删除节点

删除链表中的一个节点，我们需要找到目标节点的前一个节点，然后修改前一个节点的Next指针。下面是一个示例：

func DeleteNode(prev *ListNode) {
    prev.Next = prev.Next.Next
}

上述代码中，我们将前一个节点的Next指针指向目标节点的下一个节点即可完成删除操作。

反转链表

反转链表是常见的操作，通过修改节点的指针，可以将链表逆序。下面是一个示例：

func ReverseLinkedList(head *ListNode) *ListNode {
    var prev *ListNode
    curr := head

    for curr != nil {
        next := curr.Next
        curr.Next = prev
        prev = curr
        curr = next
    }

    return prev
}

上述代码中，我们使用三个指针来记录前一个节点（prev）、当前节点（curr）和下一个节点（next）。每次循环中，将当前节点的Next指针指向前一个节点，然后依次向后移动指针。

总结

本文介绍了如何使用Golang实现链表，并讲解了链表的基本操作，包括创建链表、遍历链表、插入节点、删除节点和反转链表等。通过掌握这些操作，我们可以更加灵活地处理链表数据。