golang链表删除

WBOY原创: 2023-05-27 12:16:39159浏览

Golang是一门高效、简洁、安全且高可扩展性的编程语言，它支持链表这种数据结构的实现。链表是一种常用的数据结构，可用于实现栈、队列以及其他数据结构。在链表中，每个节点包含数据和一个指向下一个节点的指针。链表的插入和删除操作比数组更高效，但链表删除操作比较复杂。本文将介绍如何在Golang中实现链表删除操作。

链表基本知识

在Golang中，链表是利用结构体和指针实现的。每个节点都包含数据和一个指向下一个节点的指针，且最后一个节点的指针为空。

以下是一个简单的链表示例：

type Node struct {
    val  int
    next *Node
}

上述代码定义了一个名为Node的结构体，它包含int类型的val和指向下一个节点的指针next。

可以使用以下方法创建一个链表：

func createLinkedList() *Node {
    head := Node{0, nil} // 创建头结点
    curr := &head

    // 添加节点到链表
    for i := 1; i < 10; i++ {
        node := Node{i, nil}
        curr.next = &node
        curr = &node
    }

    return &head
}

上述代码会从头结点开始，通过不断循环将每个节点添加到链表中。最后，返回整个链表。

链表删除操作

链表删除操作需要首先遍历链表，找到需要删除的节点。然后，更新该节点前一个节点的指针，使其指向删除节点的下一个节点。最后，释放删除节点占用的内存空间。

以下是实现链表删除操作的方法：

func deleteNode(head *Node, val int) *Node {
    dummy := &Node{0, head} // 创建虚拟头结点
    prev := dummy
    curr := head

    // 遍历链表，寻找需要删除的节点
    for curr != nil {
        if curr.val == val {
            prev.next = curr.next // 更新前一个节点的指针
            break
        }
        prev = curr
        curr = curr.next
    }

    return dummy.next
}

上述代码首先创建一个虚拟头结点来处理删除开始就是头结点的情况。然后，遍历链表并找到需要删除的节点。最后，更新前一个节点的指针，使其指向删除节点的下一个节点。返回链表中剩余的节点。

完整代码

以下是一个完整的程序，包括创建链表和删除节点操作：

package main

import "fmt"

type Node struct {
    val  int
    next *Node
}

func createLinkedList() *Node {
    head := Node{0, nil} // 创建头结点
    curr := &head

    // 添加节点到链表
    for i := 1; i < 10; i++ {
        node := Node{i, nil}
        curr.next = &node
        curr = &node
    }

    return &head
}

func deleteNode(head *Node, val int) *Node {
    dummy := &Node{0, head} // 创建虚拟头结点
    prev := dummy
    curr := head

    // 遍历链表，寻找需要删除的节点
    for curr != nil {
        if curr.val == val {
            prev.next = curr.next // 更新前一个节点的指针
            break
        }
        prev = curr
        curr = curr.next
    }

    return dummy.next
}

func main() {
    head := createLinkedList()
    fmt.Println("before delete:")
    curr := head
    for curr != nil {
        fmt.Println(curr.val)
        curr = curr.next
    }

    head = deleteNode(head, 5)
    fmt.Println("after delete:")
    curr = head
    for curr != nil {
        fmt.Println(curr.val)
        curr = curr.next
    }
}

该程序创建了一个包含10个节点的链表，并删除了val为5的节点。最后，输出剩余节点的值。