In-depth analysis of insertion, deletion, update and query operations of linked lists in Golang

Detailed explanation of add, delete, modify and query operations in linked list in Golang

Linked list (linked list) is a common data structure, which consists of a set of nodes (node) , each node contains data and a pointer to the next node. Compared with arrays, the advantage of linked lists is that the time complexity of insertion and deletion operations is O(1), and is not limited by the length of the linked list. In Golang, we can use a combination of structures and pointers to implement linked lists.

This article will introduce in detail the operations of adding, deleting, modifying, and checking linked lists in Golang, and provide corresponding code examples.

1. Linked list structure definition

To define the linked list structure in Golang, we can use the following structure:

type ListNode struct {
    Val  int
    Next *ListNode
}

Among them, ListNode is the type of each node, Val is the data stored in the node, Next is the pointer to the next node.

2. Creation of linked list

Creation of linked list can be done node by node, or it can be quickly created through slices or arrays. The following is a sample code for creating a linked list node by node:

func createLinkedList(data []int) *ListNode {
    if len(data) == 0 {
        return nil
    }
    head := &ListNode{Val: data[0]}
    curr := head
    for i := 1; i < len(data); i++ {
        node := &ListNode{Val: data[i]}
        curr.Next = node
        curr = node
    }
    return head
}

Call the createLinkedList function to create a linked list containing given data.

3. Insertion into a linked list

The insertion operation into a linked list requires specifying the location to be inserted and the element to be inserted. The following is a sample code to insert an element at a specified position:

func insertNode(head *ListNode, index int, val int) *ListNode {
    if index == 0 {
        newNode := &ListNode{Val: val, Next: head}
        return newNode
    }
    curr := head
    for i := 0; i < index-1; i++ {
        curr = curr.Next
        if curr == nil {
            return head
        }
    }
    newNode := &ListNode{Val: val}
    newNode.Next = curr.Next
    curr.Next = newNode
    return head
}

Call the insertNode function to insert an element at a specified position.

4. Deletion of a linked list

The deletion operation of a linked list is performed by specifying the node or index to be deleted. The following is a sample code to delete a specified node:

func deleteNode(head *ListNode, target *ListNode) *ListNode {
    if head == nil || target == nil {
        return head
    }
    if head == target {
        return head.Next
    }
    curr := head
    for curr.Next != nil && curr.Next != target {
        curr = curr.Next
    }
    if curr.Next != nil {
        curr.Next = curr.Next.Next
    }
    return head
}

Call the deleteNode function to delete the specified node.

5. Modification of linked list

The modification operation of linked list is performed by specifying the node or index to be modified and the new element value. The following is a sample code to modify the specified node:

func modifyNode(head *ListNode, target *ListNode, val int) *ListNode {
    if head == nil || target == nil {
        return head
    }
    curr := head
    for curr != nil && curr != target {
        curr = curr.Next
    }
    if curr != nil {
        curr.Val = val
    }
    return head
}

Call the modifyNode function to modify the value of the specified node.

6. Looking up the linked list

The looking up operation of the linked list is performed by traversing the linked list. The following is a sample code to find the specified element:

func searchNode(head *ListNode, val int) *ListNode {
    curr := head
    for curr != nil && curr.Val != val {
        curr = curr.Next
    }
    return curr
}

Call the searchNode function to find the node of the specified element.

The above is a detailed explanation of the add, delete, modify, and check operations of linked lists in Golang. Through the above code examples, we can flexibly operate linked lists to implement various functions. As an important data structure, linked lists can be used in many scenarios, such as LRU caching mechanism, LRU caching mechanism, linked list sorting, etc. In actual development, we can choose linked lists as the appropriate data structure according to specific needs.

It should be noted that when dealing with linked list operations, special attention should be paid to boundary conditions and the handling of empty linked lists to avoid null pointer exceptions.

I hope the introduction in this article can help everyone better understand and use linked lists. thanks for reading!

The above is the detailed content of In-depth analysis of insertion, deletion, update and query operations of linked lists in Golang. For more information, please follow other related articles on the PHP Chinese website!