golang linked list deletion

Golang is an efficient, concise, safe and highly scalable programming language that supports the implementation of data structures such as linked lists. A linked list is a commonly used data structure that can be used to implement stacks, queues, and other data structures. In a linked list, each node contains data and a pointer to the next node. The insertion and deletion operations of linked lists are more efficient than arrays, but the deletion operations of linked lists are more complicated. This article will introduce how to implement linked list deletion operation in Golang.

1. Basic knowledge of linked lists

In Golang, linked lists are implemented using structures and pointers. Each node contains data and a pointer to the next node, with the last node's pointer being null.

The following is a simple example of a linked list:

type Node struct {
    val  int
    next *Node
}

The above code defines a structure named Node, which contains a val of type int and a pointer next pointing to the next node.

You can use the following method to create a linked list:

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
}

The above code will start from the head node and add each node to the linked list through a continuous loop. Finally, the entire linked list is returned.

2. Linked list deletion operation

The linked list deletion operation requires first traversing the linked list to find the node that needs to be deleted. Then, update the pointer of the node before that node so that it points to the node next to the deleted node. Finally, release the memory space occupied by the deleted node.

The following is the method to implement the linked list deletion operation:

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
}

The above code first creates a virtual head node to handle the situation where the deletion starts with the head node. Then, traverse the linked list and find the node that needs to be deleted. Finally, the pointer of the previous node is updated so that it points to the node next to the deleted node. Returns the remaining nodes in the linked list.

3. Complete code

The following is a complete program, including creating a linked list and deleting nodes:

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
    }
}

This program creates a list of 10 A linked list of nodes, and the node with val 5 is deleted. Finally, output the values ​​of the remaining nodes.

4. Summary

This article introduces how to use Golang to implement linked list deletion operations. Linked list is an important data structure and is widely used in algorithms. The method introduced in this article can be applied to the implementation of linked lists in other programming languages, and you can choose to use it based on your actual needs.

The above is the detailed content of golang linked list deletion. For more information, please follow other related articles on the PHP Chinese website!