C# : List<T> en profondeur

List<T> est la collection par défaut, mais derrière sa simplicité se cache un tableau de taille fixe que la classe remplace au fur et à mesure. Comprendre ce mécanisme, c'est éviter les réallocations inutiles et les pièges de suppression.

# Count vs Capacity

Deux nombres différents, souvent confondus :

• Count : le nombre d'éléments réellement présents.
• Capacity : la taille du tableau interne actuellement alloué, donc combien d'éléments la liste peut contenir avant de devoir s'agrandir.

List<int> liste = new List<int>();
Console.WriteLine($"{liste.Count} / {liste.Capacity}");  // 0 / 0

liste.Add(1);
Console.WriteLine($"{liste.Count} / {liste.Capacity}");  // 1 / 4

liste.Add(2);
liste.Add(3);
liste.Add(4);
liste.Add(5);
Console.WriteLine($"{liste.Count} / {liste.Capacity}");  // 5 / 8

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

Console.WriteLine($"{liste.Count} / {liste.Capacity}");  // 0 / 0

liste.Add(1);

Console.WriteLine($"{liste.Count} / {liste.Capacity}");  // 1 / 4

liste.Add(2);

liste.Add(3);

liste.Add(4);

liste.Add(5);

Console.WriteLine($"{liste.Count} / {liste.Capacity}");  // 5 / 8

Tu as toujours Count <= Capacity. L'espace entre les deux, ce sont des cases allouées mais vides, prêtes à accueillir des Add sans réallocation.

# Comment le tableau grandit

Un tableau a une taille fixe : on ne peut pas l'agrandir. Quand un Add dépasse la Capacity, List<T> :

1. alloue un nouveau tableau deux fois plus grand,
2. recopie tous les éléments de l'ancien vers le nouveau,
3. abandonne l'ancien tableau au ramasse-miettes.

La capacité suit donc 0 -> 4 -> 8 -> 16 -> 32.... Cette étape de copie coûte O(n), mais elle est rare : elle n'arrive qu'aux passages de puissance. Réparti sur l'ensemble des Add, le coût moyen redevient constant.

# Pré-dimensionner quand tu connais la taille

Si tu vas ajouter 10 000 éléments, la liste va réallouer et recopier une douzaine de fois en chemin. Une seule ligne l'évite :

// Sans capacité initiale : ~12 réallocations pour arriver à 10 000
List<int> lente = new List<int>();

// Avec : un seul tableau alloué, zéro recopie
List<int> rapide = new List<int>(10_000);

// Ou après coup, avant une grosse insertion
rapide.EnsureCapacity(10_000);

// Sans capacité initiale : ~12 réallocations pour arriver à 10 000

List<int> lente = new List<int>();

// Avec : un seul tableau alloué, zéro recopie

List<int> rapide = new List<int>(10_000);

// Ou après coup, avant une grosse insertion

rapide.EnsureCapacity(10_000);

À l'inverse, si une liste a été énorme puis vidée, sa Capacity reste grande. TrimExcess() rend la mémoire :

liste.Clear();          // Count = 0, mais Capacity inchangée
liste.TrimExcess();     // réduit Capacity au plus près de Count

liste.Clear();          // Count = 0, mais Capacity inchangée

liste.TrimExcess();     // réduit Capacity au plus près de Count

# Insert et RemoveAt : le coût du décalage

Comme les éléments sont contigus, insérer ou retirer ailleurs qu'à la fin oblige à décaler tout ce qui suit :

List<int> nombres = new List<int> { 10, 20, 30, 40, 50 };

nombres.Insert(0, 5);   // décale 10, 20, 30, 40, 50 d'un cran : O(n)
nombres.RemoveAt(0);    // re-décale tout dans l'autre sens : O(n)

List<int> nombres = new List<int> { 10, 20, 30, 40, 50 };

nombres.Insert(0, 5);   // décale 10, 20, 30, 40, 50 d'un cran : O(n)

nombres.RemoveAt(0);    // re-décale tout dans l'autre sens : O(n)

Ajouter (Add) ou retirer (RemoveAt(Count - 1)) en fin est instantané, car il n'y a rien à décaler. Si tu fais beaucoup d'insertions au début ou au milieu, c'est le signe qu'une autre structure (Queue, LinkedList, ou un Dictionary) conviendrait mieux.

# Supprimer proprement

Le piège classique : modifier la liste pendant qu'on l'itère.

// PLANTE : InvalidOperationException
foreach (int n in nombres)
{
    if (n % 2 == 0) nombres.Remove(n);   // interdit pendant un foreach
}

// PLANTE : InvalidOperationException

foreach (int n in nombres)

{

    if (n % 2 == 0) nombres.Remove(n);   // interdit pendant un foreach

}

Trois façons correctes :

// 1. RemoveAll : un seul passage, en O(n), le plus lisible
nombres.RemoveAll(n => n % 2 == 0);

// 2. Boucle for à l'envers (les index restent valides en reculant)
for (int i = nombres.Count - 1; i >= 0; i--)
{
    if (nombres[i] % 2 == 0) nombres.RemoveAt(i);
}

// 3. Matérialiser la liste à supprimer d'abord
List<int> aRetirer = nombres.Where(n => n % 2 == 0).ToList();
foreach (int n in aRetirer) nombres.Remove(n);

// 1. RemoveAll : un seul passage, en O(n), le plus lisible

nombres.RemoveAll(n => n % 2 == 0);

// 2. Boucle for à l'envers (les index restent valides en reculant)

for (int i = nombres.Count - 1; i >= 0; i--)

{

    if (nombres[i] % 2 == 0) nombres.RemoveAt(i);

}

// 3. Matérialiser la liste à supprimer d'abord

List<int> aRetirer = nombres.Where(n => n % 2 == 0).ToList();

foreach (int n in aRetirer) nombres.Remove(n);

# List<T> ou tableau T[] ?

List<T> s'appuie sur un T[]. Choisis le tableau brut seulement quand la taille est fixe et connue, ou pour un accès très bas niveau ; sinon List<T> gagne par sa souplesse.

Une List<T> d'objets ne stocke que des références vers le tas (voir la mémoire) ; une List<int> stocke les entiers directement dans son tableau interne, sans boxing.

# La suite

• Les collections en pratique - la vue d'ensemble des structures
• Dictionary et le hachage - l'autre grand deep-dive
• La mémoire - pile, tas et références