Implémentation d'une liste chaînée en Go

Vous trouverez des explications sur ce langage ici. Vous trouverez une solution possible ici.

Pour programmer, vous pouvez utiliser l'environnement en ligne : Go Playground

Go est un langage fortement typer. Nous ne pourrons pas créer une liste contenant n'importe quel type de donnée comme on l'a fait en Python. Nous devons choisir. Par exemple, notre liste contiendra des entiers int.

Les structures pour les maillons et la tête de liste

Nous avions besoin de maillon qui contenaient deux informations : La donnée contenue dans le maillon, data, et le lien avec le maillon suivant, next. En Python, nous utilisions un dictionnaire. Mais il n'y en a pas en Go.

Nous utiliserons donc la possibilité de créer un type de donnée. On appelle cela une structure que l'on appelle avec le mot-clé struct.

type Maillon struct {
    data int
    next *Maillon
}

type Liste struct {
   head *Maillon
}

En Python, on disait que maillon["next"] = autre_maillon ce qui laissait croire que maillon et autre_maillon étaient de variables contenant les informations sur un maillon. Ce n'est pas tout à fait exact : En vérité, maillon et autre_maillon sont des variables contenant une adresse qui amène au contenu de maillon concerné. Ce sont des pointeurs. Mais en Python cela est caché. En Go, nous devons l'expliciter. C'est pour cela que nous devons écrire *Maillon dans le code précédent : c'est la façon en Go d'indiquer que head et next ne sont pas des maillons mais des flèches pointant sur des maillons.

Pourquoi ces pointeurs sont-ils si important ? Si next désignait vraiment le contenu d'un maillon, alors un maillon pourrait contenir un autre maillon qui lui même pourrait contenir un maillon… Ainsi, on ne pourrait pas prévoir la taille en mémoire d'un maillon puisque un maillon pourrait, comme des poupées gigognes, en contenir d'autres. C'est pourquoi next est en fait une adresse vers un maillon. On peut prévoir la taille qu'aura une adresse. Quand on crée un maillon en mémoire, on sait quoi réserver comme place pour next puisque next ne contiendra qu'une adresse.

Le programme

Je vous donne le début du programme pour que vous voyez les différences de syntaxes. En suivant ce modèle vous pourrez deviner comment poursuivre.

// Exemple d'une liste d'entiers
package main

import fmt // pour les affichages écran

type Maillon struct {
    data int
    next *Maillon
}

type Liste struct {
    head *Maillon
}


// main est la fonction principale, le point d'entrée dans le programme :
// quand on exécute le programme, c'est main() qui est exécutée.
func main(){
    L := CREER_LISTE_VIDE()
    l := LONGUEUR(L)
    fmt.Println("Longueur de la liste :", l)
    INSERER(L, 45, 0)
    INSERER(L, 17, 0)
    INSERER(L, 19, 0)
    INSERER(L, 50, 1)
    x := LIRE(L, 1)
    fmt.Println("Valeur lue à l'indice 1 :", x)
    fmt.Println("Valeur lue à l'indice 2 :", LIRE(L,2))
    SUPPRIMER(L, 1)
    x = LIRE(L,1)
    fmt.Println("Valeur lue à l'indice 1 :", x)
    l = LONGUEUR(L)
    fmt.Println("Longueur de la liste :", l)
    i := RECHERCHER(L, 45)
    fmt.Println("45 apparaît à l'indice :", i)
    fmt.Println("A l'indice 2 : ", LIRE(L,2))
    MODIFIER(L, 137, 2)
    fmt.Println("A l'indice 2, après modif : ", LIRE(L,2))
}

// Un exemple de fonction toute faire
func CREER_LISTE_VIDE() *Liste{
    L := Liste{head:nil} // Création de l'entête
    // la liste étant vide, elle pointe sur rien (nil au lieu du None de Python)
    return &L
    // La fonction ne renvoie pas le bloc d'entête lui même mais
    // l'adresse de ce bloc, c'est à dire un pointeur.
    // L est du type Liste, donc son adresse &L est de type
    // *Liste, c'est à dire pointeur sur Liste
    
    // Remarquez qu'en Python si on écrit L = {"head":None}, L est en fait un pointeur
    // sur un dictionnaire. Mais cela est totalement caché de sorte que l'on
    // peut confondre dictionnaire et pointeur sur dictionnaire.
}

// définition d'une fonction
// On est obligé de bien spécifier les types des entrées et de la sortie
func LONGUEUR(L *Liste) int{
    c := 0 // En Go, := permet de faire l'initialisation d'une variable
           // on ne l'utilise qu'à la première apparition de la variable
           // en fonction de ce qui est à droite du :=, Go déduit le type
           // Ici, Go devine que c sera de type int
    m := L.head // même chose
                // notez comment on accède à l'attribut "head" de l'objet L.
                // En C cette notation est plus claire car on écrirait L->head
                // ce qui fait clairement apparaître la flèche du pointeur !
    for m != nil {
        // Go a une particularité : il utilise for pour les boucles tant que
        // donc for suivi d'une condition est en fait une boucle TANT QUE
        c++
        m = m.next
    }
    return c
}

func INSERER(L *Liste, e int, i int) {
    // à vous
}

func LIRE(L *Liste, i int) int {
    // à vous
}

// Je vous mets un autre exemple tout fait.
// Remarquez ici la gestion des erreurs. C'est toujours un problème :
// que fait-on quand il y a un problème ? En C on a la possibilité d'utiliser
// une fonction exit(message) qui interrompt l'exécution en affichant un message.
func SUPPRIMER(L *Liste, i int) {
    if L.head == nil {
        fmt.Println("Erreur de suppression, liste vide !")
        return
    }
    if i < 0 {
        fmt.Println("Erreur de suppression, indice négatif !")
        return
    }
    m := L.head
    if i==0 {
        // Suppression premier maillon
        L.head = m.next
        return
    }
    // rercherche élément précédent point d'insertion
    for (m != nil) && (i > 1) {
        i--
        m = m.next
    }
    if (m == nil)||(m.next == nil) {
        fmt.Println("Erreur de suppression, indice trop grand !")
        return
    }
    m_to_delete := m.next
    m.next = m_to_delete.next
}

func RECHERCHER(L *Liste, e int) int {
    // à vous
}

func MODIFIER(L *Liste, e int, i int) {
    // à vous
}