C# : Les collections en pratique

Le tour des classes concrètes de System.Collections.Generic : celles que tu instancies au quotidien. Pour chacune, l'usage courant et le coût des opérations.

# List<T> - le tableau dynamique

La collection la plus utilisée, de loin. C'est un tableau qui se redimensionne tout seul quand il se remplit.

List<string> villes = new List<string> { "Paris", "Lyon", "Marseille" };

villes.Add("Lille");              // ajoute à la fin
villes.Insert(0, "Bordeaux");    // insère en tête
villes.Remove("Lyon");           // retire par valeur
villes.RemoveAt(1);              // retire par index

string premiere = villes[0];      // accès par index
int combien = villes.Count;       // nombre d'éléments
bool aParis = villes.Contains("Paris");

List<string> villes = new List<string> { "Paris", "Lyon", "Marseille" };

villes.Add("Lille");              // ajoute à la fin

villes.Insert(0, "Bordeaux");    // insère en tête

villes.Remove("Lyon");           // retire par valeur

villes.RemoveAt(1);              // retire par index

string premiere = villes[0];      // accès par index

int combien = villes.Count;       // nombre d'éléments

bool aParis = villes.Contains("Paris");

Côté performance, c'est un tableau derrière : l'accès par index est instantané (O(1)), mais insérer ou supprimer au milieu décale tous les éléments suivants (O(n)).

# Dictionary<TKey, TValue> - la table de hachage

Associe une clé unique à une valeur. La recherche par clé est quasi instantanée (O(1) en moyenne) grâce au hachage.

Dictionary<string, int> ages = new Dictionary<string, int>
{
    ["Alice"] = 30,
    ["Bob"] = 25,
};

ages["Charlie"] = 40;             // ajoute ou met à jour
int ageAlice = ages["Alice"];     // lecture par clé
bool existe = ages.ContainsKey("Bob");

foreach (KeyValuePair<string, int> paire in ages)
{
    Console.WriteLine($"{paire.Key} a {paire.Value} ans");
}

Dictionary<string, int> ages = new Dictionary<string, int>

{

    ["Alice"] = 30,

    ["Bob"] = 25,

};

ages["Charlie"] = 40;             // ajoute ou met à jour

int ageAlice = ages["Alice"];     // lecture par clé

bool existe = ages.ContainsKey("Bob");

foreach (KeyValuePair<string, int> paire in ages)

{

    Console.WriteLine($"{paire.Key} a {paire.Value} ans");

}

Attention à l'accès par clé absente : l'indexeur lève une exception. La bonne pratique, c'est TryGetValue :

// PLANTE : KeyNotFoundException si "Zoe" n'existe pas
int age = ages["Zoe"];

// BIEN : TryGetValue teste et récupère en une seule opération
if (ages.TryGetValue("Zoe", out int ageZoe))
{
    Console.WriteLine(ageZoe);
}

// PLANTE : KeyNotFoundException si "Zoe" n'existe pas

int age = ages["Zoe"];

// BIEN : TryGetValue teste et récupère en une seule opération

if (ages.TryGetValue("Zoe", out int ageZoe))

{

    Console.WriteLine(ageZoe);

}

# HashSet<T> - l'ensemble d'éléments uniques

Une collection sans doublons où tester l'appartenance est instantané (O(1)). Idéal pour dédupliquer ou vérifier « est-ce que je l'ai déjà vu ? ».

HashSet<string> vus = new HashSet<string>();

bool ajoute1 = vus.Add("Paris");   // true  : nouvel élément
bool ajoute2 = vus.Add("Paris");   // false : déjà présent, ignoré

bool contient = vus.Contains("Paris");  // O(1)

HashSet<string> vus = new HashSet<string>();

bool ajoute1 = vus.Add("Paris");   // true  : nouvel élément

bool ajoute2 = vus.Add("Paris");   // false : déjà présent, ignoré

bool contient = vus.Contains("Paris");  // O(1)

Il offre aussi les opérations ensemblistes mathématiques :

HashSet<int> a = new HashSet<int> { 1, 2, 3, 4 };
HashSet<int> b = new HashSet<int> { 3, 4, 5, 6 };

a.IntersectWith(b);   // a = { 3, 4 }     (intersection)
// a.UnionWith(b);    // a = { 1..6 }     (union)
// a.ExceptWith(b);   // a = { 1, 2 }     (différence)

HashSet<int> a = new HashSet<int> { 1, 2, 3, 4 };

HashSet<int> b = new HashSet<int> { 3, 4, 5, 6 };

a.IntersectWith(b);   // a = { 3, 4 }     (intersection)

// a.UnionWith(b);    // a = { 1..6 }     (union)

// a.ExceptWith(b);   // a = { 1, 2 }     (différence)

# Queue<T> - premier entré, premier sorti (FIFO)

Une file d'attente. On ajoute d'un côté (Enqueue), on retire de l'autre (Dequeue). Le premier arrivé est le premier servi, comme à la boulangerie.

Queue<string> file = new Queue<string>();

file.Enqueue("Alice");   // Alice entre
file.Enqueue("Bob");     // Bob entre derrière

string premier = file.Peek();     // "Alice" (regarde sans retirer)
string servi = file.Dequeue();    // "Alice" sort
int restants = file.Count;         // 1 (Bob)

Queue<string> file = new Queue<string>();

file.Enqueue("Alice");   // Alice entre

file.Enqueue("Bob");     // Bob entre derrière

string premier = file.Peek();     // "Alice" (regarde sans retirer)

string servi = file.Dequeue();    // "Alice" sort

int restants = file.Count;         // 1 (Bob)

Quand l'utiliser : traiter des tâches dans l'ordre d'arrivée, un parcours en largeur (BFS) d'un graphe, un buffer de messages.

# Stack<T> - dernier entré, premier sorti (LIFO)

Une pile. On empile (Push) et on dépile (Pop) toujours par le haut. Le dernier posé est le premier repris, comme une pile d'assiettes.

Stack<string> pile = new Stack<string>();

pile.Push("page 1");
pile.Push("page 2");
pile.Push("page 3");

string sommet = pile.Peek();   // "page 3" (regarde sans retirer)
string retour = pile.Pop();    // "page 3" sort
// il reste "page 1" et "page 2"

Stack<string> pile = new Stack<string>();

pile.Push("page 1");

pile.Push("page 2");

pile.Push("page 3");

string sommet = pile.Peek();   // "page 3" (regarde sans retirer)

string retour = pile.Pop();    // "page 3" sort

// il reste "page 1" et "page 2"

Quand l'utiliser : une fonction annuler / rétablir (undo), l'historique de navigation, un parcours en profondeur (DFS), l'évaluation d'expressions.

# LinkedList<T> - la liste doublement chaînée

Une suite de nœuds reliés entre eux, chacun connaissant son précédent et son suivant. Insérer ou supprimer quand on tient déjà le nœud est instantané (O(1)), sans décaler le reste.

LinkedList<int> liste = new LinkedList<int>();

LinkedListNode<int> noeud = liste.AddFirst(10);
liste.AddLast(30);
liste.AddAfter(noeud, 20);   // insère 20 juste après le 10

// liste = 10 -> 20 -> 30

LinkedList<int> liste = new LinkedList<int>();

LinkedListNode<int> noeud = liste.AddFirst(10);

liste.AddLast(30);

liste.AddAfter(noeud, 20);   // insère 20 juste après le 10

// liste = 10 -> 20 -> 30

# Les variantes triées

Trois collections gardent leurs éléments triés en permanence, au prix d'insertions un peu plus coûteuses (O(log n)) :

• SortedDictionary<TKey, TValue> : un dictionnaire dont les clés restent ordonnées.
• SortedSet<T> : un HashSet toujours trié.
• SortedList<TKey, TValue> : proche du SortedDictionary, plus économe en mémoire mais plus lent à l'insertion.

SortedDictionary<string, int> scores = new SortedDictionary<string, int>
{
    ["Charlie"] = 3,
    ["Alice"] = 1,
    ["Bob"] = 2,
};
// L'itération sort dans l'ordre des clés : Alice, Bob, Charlie

SortedDictionary<string, int> scores = new SortedDictionary<string, int>

{

    ["Charlie"] = 3,

    ["Alice"] = 1,

    ["Bob"] = 2,

};

// L'itération sort dans l'ordre des clés : Alice, Bob, Charlie

# Et les interfaces ?

Toutes ces classes implémentent une hiérarchie de contrats (IEnumerable<T>, ICollection<T>, IList<T>...). Les connaître permet d'écrire des méthodes qui acceptent n'importe quelle collection plutôt qu'un type figé.

C'est le sujet de la page voisine : Les interfaces de collection.

# La suite

• List<T> en profondeur - capacité, croissance, coût amorti
• Dictionary et le hachage - buckets, collisions, clés personnalisées
• HashSet et l'égalité - classe vs record, comparateurs
• Les interfaces de collection - la hiérarchie des contrats
• LINQ - filtrer, trier et transformer ces collections