Go Language Programming Guide: Detailed Explanation of Single Linked List Implementation

Go Language Programming Guide: Detailed Explanation of Single Linked List Implementation

In Go language, singly linked list is a common data structure used to store a series of elements and Sequential access. This article will introduce the implementation principle of singly linked list in detail and give specific Go language code examples.

Definition of singly linked list

Singly linked list is a linear list data structure in which each element (node) contains two parts: the data field and the pointer field. The data field is used to store the value of the element, and the pointer field points to the next node. The pointer field of the last node is usually empty, indicating the end of the linked list.

Node definition of a singly linked list

First, we define a node type of a singly linked list:

type Node struct {
    data int
    next *Node
}

Among them, the data field stores the value of the node, nextThe field stores the pointer to the next node.

Initialization of singly linked list

Next, we define the initialization function of singly linked list:

type LinkedList struct {
    head *Node
}

func NewLinkedList() *LinkedList {
    return &LinkedList{}
}

In the initialization function, we create an empty linked list and set the head node The pointer is initialized to null.

Insertion operation of singly linked list

The insertion operation of singly linked list can be divided into two situations: inserting a node at the head of the linked list and inserting a node at the end of the linked list.

The first is the function to insert a node at the head of the linked list:

func (list *LinkedList) InsertAtBeginning(value int) {
    newNode := &Node{data: value}
    newNode.next = list.head
    list.head = newNode
}

In this function, we first create a new node and initialize its value to the passed in value. Then point the pointer of the new node to the head of the linked list, and finally update the head node of the linked list to the new node.

Next is the function to insert a node at the end of the linked list:

func (list *LinkedList) InsertAtEnd(value int) {
    newNode := &Node{data: value}
    if list.head == nil {
        list.head = newNode
        return
    }

    current := list.head
    for current.next != nil {
        current = current.next
    }
    current.next = newNode
}

This function first creates a new node and determines whether the linked list is empty. If it is empty, the new node is directly set as the head node; otherwise, the linked list is traversed until the last node is found, and then the new node is inserted after the last node.

Singly linked list deletion operation

Deletion operation is divided into two situations: deleting the head node and deleting the node with the specified value.

The first is the function to delete the head node:

func (list *LinkedList) DeleteAtBeginning() {
    if list.head == nil {
        return
    }
    list.head = list.head.next
}

This function directly points the head node pointer to the next node, thereby deleting the head node.

Next is the function to delete the node with the specified value:

func (list *LinkedList) DeleteByValue(value int) {
    if list.head == nil {
        return
    }
    if list.head.data == value {
        list.head = list.head.next
        return
    }

    prev := list.head
    current := list.head.next
    for current != nil {
        if current.data == value {
            prev.next = current.next
            return
        }
        prev = current
        current = current.next
    }
}

In this function, we need to first determine whether the linked list is empty. Then traverse the linked list starting from the head node, find the node where the target value is located and delete it.

Singly linked list traversal operation

The last is the singly linked list traversal operation:

func (list *LinkedList) Print() {
    current := list.head
    for current != nil {
        fmt.Print(current.data, " ")
        current = current.next
    }
    fmt.Println()
}

This function prints the value of the node one by one starting from the head node until the end of the linked list.

Sample code

The following is a complete sample code that demonstrates how to use a singly linked list:

package main

import "fmt"

type Node struct {
    data int
    next *Node
}

type LinkedList struct {
    head *Node
}

func NewLinkedList() *LinkedList {
    return &LinkedList{}
}

func (list *LinkedList) InsertAtBeginning(value int) {
    newNode := &Node{data: value}
    newNode.next = list.head
    list.head = newNode
}

func (list *LinkedList) InsertAtEnd(value int) {
    newNode := &Node{data: value}
    if list.head == nil {
        list.head = newNode
        return
    }

    current := list.head
    for current.next != nil {
        current = current.next
    }
    current.next = newNode
}

func (list *LinkedList) DeleteAtBeginning() {
    if list.head == nil {
        return
    }
    list.head = list.head.next
}

func (list *LinkedList) DeleteByValue(value int) {
    if list.head == nil {
        return
    }
    if list.head.data == value {
        list.head = list.head.next
        return
    }

    prev := list.head
    current := list.head.next
    for current != nil {
        if current.data == value {
            prev.next = current.next
            return
        }
        prev = current
        current = current.next
    }
}

func (list *LinkedList) Print() {
    current := list.head
    for current != nil {
        fmt.Print(current.data, " ")
        current = current.next
    }
    fmt.Println()
}

func main() {
    list := NewLinkedList()

    list.InsertAtEnd(1)
    list.InsertAtEnd(2)
    list.InsertAtEnd(3)
    list.Print()

    list.DeleteByValue(2)
    list.Print()

    list.DeleteAtBeginning()
    list.Print()
}

The above is a detailed guide to using the Go language to implement a singly linked list. I hope that through the introduction and sample code of this article, readers can have a deeper understanding of the principles and implementation of singly linked lists.

The above is the detailed content of Go Language Programming Guide: Detailed Explanation of Single Linked List Implementation. For more information, please follow other related articles on the PHP Chinese website!