Go语言编程指南：单链表实现详解

Guide de programmation du langage Go : explication détaillée de l'implémentation d'une liste chaînée unique

En langage Go, une liste chaînée unique est une structure de données commune utilisée pour stocker une série d'éléments et y accéder séquentiellement. Cet article présentera en détail le principe de mise en œuvre de la liste à chaînage unique et donnera des exemples de code de langage Go spécifiques.

Définition d'une liste chaînée unique

Une liste chaînée unique est une structure de données de liste linéaire, dans laquelle chaque élément (nœud) contient deux parties : le champ de données et le champ de pointeur. Le champ de données est utilisé pour stocker la valeur de l'élément et le champ de pointeur pointe vers le nœud suivant. Le champ de pointeur du dernier nœud est généralement vide, indiquant la fin de la liste chaînée.

Définition de nœud d'une liste à chaînage unique

Tout d'abord, nous définissons le type de nœud d'une liste à chaînage unique :

type Node struct {
    data int
    next *Node
}

Parmi eux, le champ data字段存储节点的值，next stocke le pointeur vers le nœud suivant.

Initialisation d'une liste chaînée unique

Ensuite, nous définissons la fonction d'initialisation d'une liste chaînée unique :

type LinkedList struct {
    head *Node
}

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

Dans la fonction d'initialisation, nous créons une liste chaînée vide et initialisons le pointeur du nœud principal à vide.

Opération d'insertion d'une liste chaînée unique

L'opération d'insertion d'une liste chaînée unique peut être divisée en deux situations : insérer un nœud en tête de la liste chaînée et insérer un nœud à la fin de la liste chaînée.

La première est la fonction pour insérer un nœud en tête de la liste chaînée :

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

Dans cette fonction, nous créons d'abord un nouveau nœud et initialisons sa valeur à la valeur transmise. Pointez ensuite le pointeur du nouveau nœud vers la tête de la liste chaînée, et enfin mettez à jour le nœud principal de la liste chaînée vers le nouveau nœud.

Next est la fonction pour insérer un nœud à la fin de la liste chaînée :

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
}

Cette fonction crée d'abord un nouveau nœud et détermine si la liste chaînée est vide. S'il est vide, le nouveau nœud est directement défini comme nœud principal ; sinon, la liste chaînée est parcourue jusqu'à ce que le dernier nœud soit trouvé, puis le nouveau nœud est inséré après le dernier nœud.

Opération de suppression d'une liste à chaînage unique

L'opération de suppression est divisée en deux situations : la suppression du nœud principal et la suppression du nœud avec la valeur spécifiée.

La première est la fonction pour supprimer le nœud principal :

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

Cette fonction pointe directement le pointeur du nœud principal vers le nœud suivant, supprimant ainsi le nœud principal.

Suivant est la fonction pour supprimer le nœud avec la valeur spécifiée :

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

Dans cette fonction, nous devons d'abord déterminer si la liste chaînée est vide. Parcourez ensuite la liste chaînée en commençant par le nœud principal, recherchez le nœud où se trouve la valeur cible et supprimez-le.

Opération de parcours de liste chaînée unique

La dernière est l'opération de parcours de liste chaînée unique :

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

Cette fonction imprime la valeur des nœuds un par un en commençant par le nœud principal jusqu'à la fin de la liste chaînée.

Exemple de code

Ce qui suit est un exemple de code complet qui montre comment utiliser une liste à chaînage unique :

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

Ce qui précède est un guide détaillé pour implémenter une liste à chaînage unique à l'aide du langage Go. J'espère que grâce à l'introduction et à l'exemple de code de cet article, les lecteurs pourront mieux comprendre les principes et la mise en œuvre des listes à lien unique.

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!