Comment implémenter une liste chaînée dans Golang

La liste chaînée est une structure de données commune composée d'une série de nœuds, chaque nœud contient des données et un pointeur vers le nœud suivant. Dans cet article, nous utiliserons le langage Go pour implémenter une simple liste chaînée.

1. Définir le type de nœud

Tout d'abord, nous devons définir un type de nœud. Le nœud doit contenir un élément de données et un pointeur vers le nœud suivant. Le code est le suivant :

type Node struct {
    Data interface{} //节点存储的数据
    Next *Node       //指向下一个节点的指针
}

Nous utilisons l'interface{} pour enregistrer les données du nœud, ce qui permet à la liste chaînée de stocker tout type de données.

2. Définir le type de liste chaînée

Ensuite, nous devons définir un type de liste chaînée. Il doit contenir un pointeur vers le premier nœud. Parallèlement, nous avons également ajouté deux méthodes : AddNode et Traverse. La méthode

type LinkedList struct {
    Head *Node //指向第一个节点的指针
}

//添加一个节点
func (l *LinkedList) AddNode(data interface{}) {
    newNode := &Node{Data: data}

    if l.Head == nil {
        l.Head = newNode
    } else {
        current := l.Head
        for current.Next != nil {
            current = current.Next
        }
        current.Next = newNode
    }
}

//遍历链表并执行函数
func (l *LinkedList) Traverse(fn func(interface{})) {
    current := l.Head
    for current != nil {
        fn(current.Data)
        current = current.Next
    }
}

AddNode ajoute un nœud à la fin de la liste chaînée. Si la liste chaînée est vide, le nœud ajouté devient le premier nœud. Sinon, nous parcourons la liste chaînée, trouvons le dernier nœud et ajoutons le nouveau nœud comme nœud suivant.

La méthode Traverse utilise une fonction de rappel pour faire fonctionner chaque nœud de la liste chaînée. Il parcourt chaque nœud de la liste chaînée, puis exécute la fonction transmise sur chaque nœud. Nous pouvons utiliser cette méthode pour parcourir la liste chaînée et imprimer chaque nœud :

func main() {
    list := LinkedList{}
    list.AddNode("A")
    list.AddNode("B")
    list.AddNode("C")

    list.Traverse(func(data interface{}) {
        fmt.Println(data)
    })
}

Le code ci-dessus s'imprimera :

A
B
C

3. Supprimer le nœud

Maintenant, ajoutons une méthode pour supprimer le nœud dans la liste chaînée.

//删除链表中的节点
func (l *LinkedList) RemoveNode(target interface{}) {
    if l.Head == nil {
        return
    }

    if l.Head.Data == target {
        l.Head = l.Head.Next
        return
    }

    current := l.Head
    for current.Next != nil {
        if current.Next.Data == target {
            current.Next = current.Next.Next
            return
        }
        current = current.Next
    }
}

La méthode RemoveNode prend un paramètre identifiant le nœud à supprimer et parcourt la liste chaînée pour trouver le nœud. Si le nœud est trouvé, modifiez le pointeur suivant du nœud actuel pour le supprimer de la liste chaînée. Si la liste chaînée est vide ou si le nœud n'est pas trouvé, aucune action n'est effectuée.

Code complet :

package main

import "fmt"

type Node struct {
    Data interface{} //节点存储的数据
    Next *Node       //指向下一个节点的指针
}

type LinkedList struct {
    Head *Node //指向第一个节点的指针
}

//添加一个节点
func (l *LinkedList) AddNode(data interface{}) {
    newNode := &Node{Data: data}

    if l.Head == nil {
        l.Head = newNode
    } else {
        current := l.Head
        for current.Next != nil {
            current = current.Next
        }
        current.Next = newNode
    }
}

//遍历链表并执行函数
func (l *LinkedList) Traverse(fn func(interface{})) {
    current := l.Head
    for current != nil {
        fn(current.Data)
        current = current.Next
    }
}

//删除链表中的节点
func (l *LinkedList) RemoveNode(target interface{}) {
    if l.Head == nil {
        return
    }

    if l.Head.Data == target {
        l.Head = l.Head.Next
        return
    }

    current := l.Head
    for current.Next != nil {
        if current.Next.Data == target {
            current.Next = current.Next.Next
            return
        }
        current = current.Next
    }
}

func main() {
    list := LinkedList{}
    list.AddNode("A")
    list.AddNode("B")
    list.AddNode("C")

    //遍历链表
    list.Traverse(func(data interface{}) {
        fmt.Println(data)
    })

    //删除节点并再次遍历链表
    list.RemoveNode("B")
    list.Traverse(func(data interface{}) {
        fmt.Println(data)
    })
}

Le code ci-dessus s'imprimera :

A
B
C
A
C

4. Résumé

Dans cet article, nous avons implémenté une simple liste chaînée en utilisant le langage Go. Les listes chaînées constituent une structure de données importante qui est largement utilisée dans de nombreux scénarios de développement d'algorithmes et de logiciels. Lors de l'écriture du code réel, envisagez d'ajouter des fonctionnalités supplémentaires et d'évaluer les performances.

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!