Understand and apply the basic principles and methods of Golang linked lists

The basic principles and methods of Golang linked list implementation

The linked list is a common data structure. It consists of a series of nodes, each node contains data and Pointer to the next node. Each node is connected to each other to form an ordered linked list. In Golang, we can implement linked lists by using structures and pointers. Below we will introduce the basic principles and methods of linked lists in detail, and attach specific code examples.

Basic structure of linked list

First, we need to define a structure of linked list nodes. In Golang, we can use the structure to achieve this.

type ListNode struct {
    Val  int       // 节点存储的数据
    Next *ListNode // 指向下一个节点的指针
}

Basic operations of linked lists

In linked lists, common operations include insertion, deletion and search. Below we will introduce the specific implementation of these operations one by one.

1. Insertion operation

The insertion operation of the linked list can be divided into two situations: inserting at the head of the linked list and inserting in the middle of the linked list. The specific implementation of the insertion operation is as follows:

func Insert(head *ListNode, val int) *ListNode {
    newNode := &ListNode{
        Val:  val,
        Next: nil,
    }
    if head == nil {
        return newNode
    }
    newNode.Next = head
    return newNode
}

When inserting at the head of the linked list, we only need to point the Next pointer of the new node to the head node of the original linked list, and return the new node as the new head node. .

2. Delete operation

The deletion operation of the linked list can also be divided into two situations: deleting the specified node in the linked list and deleting the node with the specified value in the linked list. The specific implementation of the deletion operation is as follows:

func DeleteNode(head *ListNode, target int) *ListNode {
    dummy := &ListNode{}
    dummy.Next = head
    cur := dummy
    for cur != nil && cur.Next != nil {
        if cur.Next.Val == target {
            cur.Next = cur.Next.Next
        } else {
            cur = cur.Next
        }
    }
    return dummy.Next
}

When deleting a specified node in the linked list, we only need to point the Next pointer of the current node to the Next pointer of the next node.

3. Search operation

The search operation of a linked list is often used to determine whether a certain value exists in the linked list. The specific implementation of the search operation is as follows:

func Search(head *ListNode, target int) bool {
    cur := head
    for cur != nil {
        if cur.Val == target {
            return true
        }
        cur = cur.Next
    }
    return false
}

We can traverse each node of the linked list and determine whether the node value is equal to the target value. If equal, return true, otherwise continue traversing until the end of the linked list.

Traversal operation of linked list

Traversal operation of linked list is often used to print the linked list or obtain the length of the linked list. The specific implementation of the traversal operation is as follows:

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

func Length(head *ListNode) int {
    count := 0
    cur := head
    for cur != nil {
        count += 1
        cur = cur.Next
    }
    return count
}

We can access each node of the linked list by continuously moving the pointer and perform corresponding operations.

The above are the basic principles and methods of Golang linked list implementation. By defining the structure and pointer of the node to construct the linked list, operations such as insertion, deletion, search and traversal are realized. Through these operations, we can flexibly process the data in the linked list and further implement more complex functions. I hope this article can help you understand the principles and methods of linked lists.

The above is the detailed content of Understand and apply the basic principles and methods of Golang linked lists. For more information, please follow other related articles on the PHP Chinese website!