Algorithmes et structures de données en Go : guide pratique

Introduction : Pourquoi les algorithmes et les structures de données sont importants en Go

Go (Golang) est un langage compilé moderne créé chez Google pour les systèmes hautes performances. Sa simplicité et son support intégré de la concurrence le rendent idéal pour le développement backend, les microservices et les applications cloud. Cependant, comme pour tout autre langage, l'efficacité du code Go dépend directement de la compréhension des algorithmes et des structures de données. Sans eux, même le langage le plus rapide peut devenir un goulot d'étranglement.

Dans cet article, nous aborderons les principales structures de données et algorithmes que tout développeur Go devrait connaître : des tableaux à la recherche binaire. Vous verrez des exemples de code, découvrirez leur fonctionnement "sous le capot" et obtiendrez des conseils pratiques d'optimisation.

1. Structures de données de base en Go

Go fournit des structures de données intégrées, mais les utiliser correctement est essentiel pour la performance. Examinons trois principales : les tableaux, les slices et les tables de hachage.

1.1 Tableaux et Slices

Un tableau en Go est une séquence de longueur fixe d'éléments de même type. Une slice est une enveloppe dynamique autour d'un tableau qui permet de modifier sa taille.

package main

import "fmt"

func main() {    // Tableau de longueur fixe    var arr [5]int = [5]int{1, 2, 3, 4, 5}    fmt.Println("Tableau:", arr)

    // Slice — structure dynamique    slice := []int{10, 20, 30}    slice = append(slice, 40) // Ajout d'un élément    fmt.Println("Slice:", slice)

    // Slice à partir d'un tableau    subSlice := arr[1:4] // [2, 3, 4]    fmt.Println("Sous-slice:", subSlice)}

Astuce : Utilisez toujours les slices plutôt que les tableaux pour plus de flexibilité, mais rappelez-vous que append peut provoquer une réallocation mémoire. Pré-allouez la capacité avec make([]int, 0, capacity).

1.2 Tables de hachage (Map)

Une map est une collection non ordonnée de paires clé-valeur. En Go, une map est implémentée comme une table de hachage, offrant un temps d'accès moyen de O(1).

package main

import "fmt"

func main() {    // Création d'une map    scores := make(map[string]int)    scores["Alice"] = 95    scores["Bob"] = 87

    // Lecture avec vérification    if val, ok := scores["Alice"]; ok {        fmt.Println("Score d'Alice :", val)    }

    // Suppression    delete(scores, "Bob")    fmt.Println("Après suppression :", scores)}

Important : Les maps ne supportent pas l'accès concurrent sans synchronisation. Pour les scénarios multi-threadés, utilisez sync.Map ou des mutex.

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

Les listes chaînées sont rarement utilisées en Go en raison de la disponibilité des slices, mais elles sont utiles pour comprendre les pointeurs et les structures dynamiques. Examinons une liste simplement chaînée.

2.1 Structure du nœud et opérations de base

package main

import "fmt"

// Nœud de listetype Node struct {    Value int    Next  *Node}

// Listetype LinkedList struct {    Head *Node}

// Ajout au débutfunc (ll *LinkedList) Prepend(value int) {    newNode := &Node{Value: value, Next: ll.Head}    ll.Head = newNode}

// Recherche d'un élémentfunc (ll *LinkedList) Search(value int) bool {    current := ll.Head    for current != nil {        if current.Value == value {            return true        }        current = current.Next    }    return false}

// Affichage de la listefunc (ll *LinkedList) Print() {    current := ll.Head    for current != nil {        fmt.Printf("%d -> ", current.Value)        current = current.Next    }    fmt.Println("nil")}

func main() {    list := LinkedList{}    list.Prepend(10)    list.Prepend(20)    list.Prepend(30)    list.Print() // 30 -> 20 -> 10 -> nil    fmt.Println("Trouvé 20 :", list.Search(20)) // true}

Performance : L'insertion au début est en O(1), la recherche est en O(n). Pour un accès fréquent par index, utilisez les slices.