Une liste chaînée est une collection d'items formées par des maillons liés les uns aux autres. Chaque maillon correspond à un emplacement mémoire contenant un item et un lien vers le maillon suivant. Comme le type de l'item est connu et que le lien est une adresse vers la case mémoire du maillon suivant, l'occupation mémoire du maillon est connue et peut être réservée.

On a besoin de pointer sur un maillon, il s'agit donc d'une adresse.

Le type défini pour les maillons étant Maillon, l'adresse d'un tel élément sera en Go de type *Maillon. L'étoile sert à indiquer que l'on veut un pointeur sur l'élément.

On définit le type Maillon contenant un entier et un pointeur vers le maillon suivant. Pour cela on utilise une structure:

type Maillon struct {
    data int
    next *Maillon
}

La liste elle-même est un conteneur chargé d'amorcer la liste.

type Liste struct {
    head *Maillon
}

Retrouver ce script sur GoPlayground.

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

import fmt

type Maillon struct {
    data int
    next *Maillon
}

type Liste struct {
    head *Maillon
}


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

func CREER_LISTE_VIDE() *Liste{
    L := Liste{head:nil}
    return &L
}

func LONGUEUR(L *Liste) int{
    c := 0
    m := L.head
    for m != nil {
        c++
        m = m.next
    }
    return c
}

func INSERER(L *Liste, e int, i int) {
    if i < 0  {
        // interdit. On ne fait pas de gestion d'erreur,
        // on se contente de sortir
        return
    }
    new_maillon := Maillon{data:e, next:nil}
    if (i==0) {
        // insertion en premier
        new_maillon.next = L.head
        L.head = &new_maillon
        return
    }
    // sinon chercher le point d'insertion
    m := L.head
    for (m != nil) && (i > 1) {
        i--
        m = m.next;
    }
    if m == nil {
        // On est arrivé trop loin, pas d'insertion possible
        fmt.Println("Erreur insertion, i trop grand !")
        return
    }
    new_maillon.next = m.next
    m.next = &new_maillon
}

func LIRE(L *Liste, i int) int {
    // il faudrait vérifier i > 0
    if i < 0  {
        fmt.Println("Erreur lecture : indice négatif !")
        return 0
    }
    m := L.head
    for (i > 0) && (m != nil) {
        i--
        m = m.next
    }
    if m == nil {
        // On est arrivé trop loin, pas d'insertion possible
        fmt.Println("Erreur de lecture, i trop grand !")
        return 0
    }
    return m.data
}

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 {
    /* renvoie l'indice de la première apparition
       de e dans la liste s'il existe, -1 sinon */
    m := L.head
    i := 0
    for m != nil {
        if m.data == e {
            return i
        }
        i++
        m = m.next
    }
    return -1
}

func MODIFIER(L *Liste, e int, i int) {
    /* écrit la valeur e à l'indice i */
    if i < 0 {
        fmt.Println("Erreur de modification, indice négatif !")
        return
    }
    m := L.head
    for (m != nil) && (i > 0) {
        i--
        m = m.next
    }
    if m == nil {
        fmt.Println("Erreur de modification, indice trop grand !")
        return
    }
    m.data = e
}