Programmation · Prog 10 · Ranger les données

Collections

Une liste, un dictionnaire ou un ensemble : à chaque besoin son rangement.

Déjà à l'aise ? Aller directement au quiz

Les élèves d’une classe, une playlist, les notes de chacun, les inscrits d’un tournoi : on range sans cesse des données en groupe.

Mais pas toujours de la même façon.

Selon ce qu’on veut faire, on choisit un rangement différent.

[0]Léa[1]Noah[2]Léa garder l’ordreliste Léa 5.5 Tom 4.0 retrouver par un nomdictionnaire LéaNoah éviter les doublonsensemble trois rangements, trois usages

Garder l’ordre, retrouver vite par un nom, éviter les doublons : une liste, un dictionnaire, un ensemble.

À chaque besoin, son rangement.

Au programme

  • 01pourquoi pas un simple tableau
  • 02la liste : l’ordre et les indices
  • 03le dictionnaire : retrouver par une clé
  • 04l’ensemble : pas de doublon
  • 05choisir la bonne collection
  • 06trier selon un critère
Question pour toi : pour savoir si un pseudo est déjà pris parmi 100 000 inscrits, faut-il vraiment les regarder un par un ?

Ben oui, comment faire autrement ?

Il y a bien plus rapide. La réponse t’attend au chapitre des ensembles.

Un tableau a une taille fixe

Dans la vraie vie

Une boîte à œufs a six places, pas une de plus.

6 places, pas une de plus 7e plus grande boîte, on déplace tout

Un septième œuf ? Il faut une boîte plus grande, et y déplacer tous les autres.

new int[5]

En Java, new int[5] réserve cinq cases, pas une de plus (Prog 6). Une collection fait le déménagement pour toi : elle grandit toute seule, avec add, remove, contains…

tableauJava
int[] notes = new int[5];
// 5 cases, pour toujours
collectionJava
List<Integer> notes = new ArrayList<>();
notes.add(5);   // grandit toute seule

Et en Python ?

Pas de tableau à taille fixe dans le langage de base : la list de Python grandit toute seule, comme ArrayList en Java ou Array en JavaScript.

Des éléments dans l’ordre, numérotés depuis 0

Dans la vraie vie

Dans une file au guichet, chacun a sa place : 1re, 2e, 3e…

guichet Léa NoahEmmaMalik Zoé 1re2e3e4e5e ceux qui suivent reculent d’une place

Arriver au bout, c’est facile. Se glisser devant, c’est faire reculer tous ceux qui suivent.

liste

Une liste garde l’ordre d’arrivée et accepte les doublons. La 1re place a l’indice 0. En coulisse, une ArrayList range ses éléments dans un tableau un peu plus grand que nécessaire : sa capacité.

[0]Léa[1]Zoé[2]Noah[3] taille : 3 capacité : 4 case libre

Où s’arrête la file.

Dans la file, le premier qui part fait avancer tout le monde ; remove(0) aussi décale toute la liste. Pour une vraie file d’attente, Java a ArrayDeque, qui retire le premier en temps constant7.

Une ArrayList en coulisse

Six opérations sur une liste de capacité 4 : ajouter, insérer, agrandir, retirer, lire. Fais défiler.

Une ArrayList en coulissetaille 0
  1. List<String> e = new ArrayList<>(4);
  2. e.add("Léa");
  3. e.add("Noah"); e.add("Emma");
  4. e.add(1, "Zoé");
  5. e.add("Malik");
  6. e.remove(0);
  7. e.get(2);

Une liste vide, avec une capacité de 4 : le tableau caché a 4 cases, la taille vaut 0.

Lire, modifier

e.get(i) se fait en temps constant : la case d’indice i est lue directement2.

Ajouter à la fin

En temps constant « amorti » : de temps en temps, le tableau caché est plein et doit être recopié dans un plus grand.

Insérer ou retirer au début

Tous les éléments suivants se décalent : c’est proportionnel à la taille de la liste.

La liste, en cinq langages

Python, Java, JavaScript, Go et R : touche un langage. Attention, R compte depuis 1.

Pythonliste.py
eleves = []
eleves.append("Léa")        # à la fin
eleves.append("Noah")
eleves.insert(1, "Zoé")     # à l'indice 1
print(eleves, len(eleves))  # ['Léa', 'Zoé', 'Noah'] 3
del eleves[0]               # retire l'indice 0
print(eleves[1])            # Noah
for e in eleves:
    print(e)
JavaListe.java
List<String> eleves = new ArrayList<>();
eleves.add("Léa");
eleves.add("Noah");
eleves.add(1, "Zoé");         // insère à l'indice 1
System.out.println(eleves);   // [Léa, Zoé, Noah]
eleves.remove(0);             // retire l'indice 0
System.out.println(eleves.get(1));   // Noah
for (String e : eleves) {
    System.out.println(e);
}
JavaScriptliste.js
const eleves = [];
eleves.push("Léa");
eleves.push("Noah");
eleves.splice(1, 0, "Zoé");   // insère à l'indice 1
console.log(eleves.length);   // 3
eleves.splice(0, 1);          // retire l'indice 0
console.log(eleves[1]);       // Noah
for (const e of eleves) {
    console.log(e);
}
Goliste.go
eleves := []string{}                  // une slice vide
eleves = append(eleves, "Léa")
eleves = append(eleves, "Noah")
premier := eleves[0]
eleves = append(eleves[:0], eleves[1:]...)   // retire l'indice 0
fmt.Println(premier, len(eleves))
for i, e := range eleves {
    fmt.Printf("[%d] %s\n", i, e)
}
Rliste.R
eleves <- c()                   # vecteur vide
eleves <- c(eleves, "Léa")
eleves <- c(eleves, "Noah")
premier <- eleves[1]            # en R, on compte depuis 1
eleves <- eleves[-1]            # retire le 1er élément
length(eleves)
Exercice 1

Que contient la liste ?

Touche la bonne réponse.

notes = [4, 5.5, 6]
notes.insert(1, 3)
print(notes)
List<Integer> l = new ArrayList<>(List.of(10, 20, 30));
l.remove(1);
System.out.println(l);

Laquelle de ces opérations devient lente quand la liste est très longue ?

Retrouver une valeur par sa clé

Dans la vraie vie

Dans un classeur à onglets, la fiche de Tom se range sous T.

A–DE–HI–LM–PQ–TU–Z « Tom » Tom : 4.0 Tim : 5.0 onglet de T :on y va tout droit même onglet ? on compare quelques fiches

Pas besoin de feuilleter tout le classeur : on va droit au bon onglet. Tom et Tim s’y retrouvent ? On compare juste ces fiches-là.

clé → valeur

Un dictionnaire associe chaque clé (un prénom) à une valeur (sa note). À partir de la clé, il calcule un nombre, le hachage, qui désigne directement la case où chercher.

"Tom" hachage case 3 01234567 3 on va droit à la case, sans fouiller les autres

Mieux que la première lettre.

Là s’arrête le classeur : le vrai hachage tient compte de toute la clé et répartit bien mieux. Dans une HashMap de 8 cases, Tom va en case 3, Tim en case 1.

HashMap, 8 cases

Une HashMap Java de 8 cases, avec les vrais numéros de case : quatre clés, une recherche, une collision.

HashMap, 8 casesvide
  1. notes.put("Léa", 5.5);
  2. notes.put("Tom", 4.0);
  3. notes.put("Lina", 6.0);
  4. notes.get("Tom");
  5. notes.put("Léa", 5.0);
  6. notes.put("Mia", 4.5);
  7. notes.get("Zoé");

Une table de 8 cases, numérotées de 0 à 7. Chaque clé ira dans la case que son hachage désigne.

Tu as vu Mia ? Elle tombe dans la même case que Lina. C’est une collision, et c’est normal.

Et alors, laquelle on prend ?

La table compare ensuite les clés une par une, mais seulement dans cette case-là. C’est pour ça que ça reste rapide.

Compter des votes

Un vrai programme, ligne par ligne : une liste de bulletins, un dictionnaire qui compte les voix.

votes.pyPython
votes = ["Léa", "Tom", "Léa",         "Mia", "Léa", "Tom"]compte = {}for v in votes:    compte[v] = compte.get(v, 0) + 1print(compte)
votesLéaTomLéaMiaLéaTom compte sortie

Six bulletins, un dictionnaire. Une liste garde les votes dans l’ordre ; le dictionnaire compte les voix de chaque prénom.

Lignes 1 à 3. La liste votes contient six bulletins, avec des doublons. compte part vide : aucune clé.

Premier tour : v vaut "Léa". La clé est absente, get(v, 0) renvoie 0 au lieu d’une erreur : compte["Léa"] vaut 1.

Deuxième tour : "Tom". Nouvelle clé, rangée après Léa : un dictionnaire Python garde l’ordre d’insertion.

Troisième tour : "Léa" encore. La clé existe : get renvoie 1, on range 2 sous la même clé. Pas de doublon de clé, la valeur est remplacée.

Les trois derniers tours : Mia, Léa, Tom. Mia entre avec 1, Léa monte à 3, Tom à 2.

Ligne 6 : l’affichage. {'Léa': 3, 'Tom': 2, 'Mia': 1}, dans l’ordre où les clés sont apparues.

Le dictionnaire, en quatre langages

Python, Java, JavaScript et Go : touche un langage pour voir les mêmes notes rangées par prénom.

Pythonnotes.py
notes = {"Léa": 5.5, "Tom": 4.0}
notes["Lina"] = 6.0      # ajoute une paire
notes["Léa"] = 5.0       # même clé : valeur remplacée
print(notes["Tom"])      # 4.0
print("Zoé" in notes)    # False
print(notes.get("Zoé"))  # None, sans erreur
for nom, note in notes.items():
    print(nom, note)
JavaNotes.java
Map<String, Double> notes = new HashMap<>();
notes.put("Léa", 5.5);
notes.put("Tom", 4.0);
notes.put("Léa", 5.0);                  // valeur remplacée
System.out.println(notes.get("Tom"));   // 4.0
System.out.println(notes.get("Zoé"));   // null
System.out.println(notes.getOrDefault("Zoé", 0.0));   // 0.0
for (Map.Entry<String, Double> e : notes.entrySet()) {
    System.out.println(e.getKey() + " : " + e.getValue());
}
JavaScriptnotes.js
const notes = new Map();
notes.set("Léa", 5.5);
notes.set("Tom", 4);
notes.set("Léa", 5);             // valeur remplacée
console.log(notes.get("Tom"));   // 4
console.log(notes.get("Zoé"));   // undefined
console.log(notes.has("Tom"));   // true
for (const [nom, note] of notes) {
    console.log(`${nom} : ${note}`);
}
Gonotes.go
notes := map[string]float64{"Léa": 5.5, "Tom": 4.0}
notes["Léa"] = 5.0               // valeur remplacée
note, existe := notes["Zoé"]      // 0 false : absente
fmt.Println(note, existe)
delete(notes, "Tom")
for nom, n := range notes {      // ordre non garanti
    fmt.Println(nom, n)
}

Une clé est unique

Ranger une valeur sous une clé déjà présente remplace l’ancienne valeur1.

Clé absente

notes["Zoé"] lève KeyError en Python ; get renvoie None (Python), null (Java), undefined (JavaScript)6.

Rapide en moyenne

get et put prennent un temps constant tant que le hachage répartit bien les clés3. Beaucoup de collisions ralentiraient la recherche.

L’ordre

Une HashMap Java ne garantit aucun ordre (il faut LinkedHashMap). Un dict Python et une Map JavaScript gardent l’ordre d’insertion.

Piège Java

double x = notes.get("Zoé"); compile. Mais get renvoie null, qui ne rentre pas dans un double : NullPointerException.

Utilise getOrDefault("Zoé", 0.0), ou teste containsKey d’abord.

Exercice 2

Clés et valeurs

Que se passe-t-il ?

d = {"Léa": 5.5}
d["Léa"] = 5
print(d)
d = {"Léa": 5}
print(d["Tom"])
Map<String, Double> notes = new HashMap<>();
double x = notes.get("Zoé");

Pas de doublon, pas d’ordre

Dans la vraie vie

Dans un album de vignettes, chaque vignette a sa place.

12345678 5 la 5 : sa place 3 un double : refusé

Un double ? Il ne rentre pas, la place est prise. Et pour savoir si tu as la 7, tu regardes directement sa case.

ensemble

Un ensemble garde chaque élément une seule fois et ne promet aucun ordre. Pas de cases numérotées visibles : le hachage choisit la place, comme dans un dictionnaire. Un HashSet Java repose d’ailleurs sur une HashMap4.

Les inscrits du tournoi

Les inscriptions arrivent : un doublon, puis deux tests d’appartenance. Fais défiler.

Les inscrits du tournoi0 inscrit

Un ensemble vide. Chaque pseudo inscrit y entrera une seule fois.

Réponse à ma question du début : non. Avec un ensemble, « ce pseudo existe-t-il ? » prend en moyenne le même temps avec 10 ou 100 000 inscrits.

Et avec une liste ?

Il faudrait les parcourir, parfois jusqu’au dernier. Plus la liste est longue, plus c’est lent.

L’ensemble, en trois langages

Python, Java et JavaScript : touche un langage. En Python, l’union, l’intersection et la différence s’écrivent avec |, & et -.

Pythoninscrits.py
inscrits = set()               # pas {} : c'est un dict vide
inscrits.add("Léa")
inscrits.add("Noah")
inscrits.add("Léa")            # déjà là : rien ne change
print(len(inscrits))           # 2
print("Emma" in inscrits)      # False

a = {"Léa", "Noah", "Emma"}
b = {"Noah", "Tom"}
print(a | b)   # union : les 4 pseudos
print(a & b)   # intersection : {'Noah'}
print(a - b)   # différence : Léa et Emma
JavaInscrits.java
Set<String> inscrits = new HashSet<>();
System.out.println(inscrits.add("Léa"));    // true
System.out.println(inscrits.add("Léa"));    // false : déjà présent
System.out.println(inscrits.size());        // 1
System.out.println(inscrits.contains("Emma"));   // false
JavaScriptinscrits.js
const inscrits = new Set(["Léa", "Noah"]);
inscrits.add("Léa");                  // déjà là
console.log(inscrits.size);           // 2
console.log(inscrits.has("Emma"));    // false

Piège Python

{} crée un dictionnaire vide, pas un ensemble. Un ensemble vide s’écrit set()1.

En revanche, {"Léa", "Noah"}, avec des éléments, est bien un ensemble.

Trois questions pour choisir

Dans la vraie vie

Une course à pied : l’ordre d’arrivée, le coureur derrière chaque dossard, les pays représentés.

à l’arrivée1. Léa2. Noah3. Emmaliste les dossards12 → Léa7 → Noah31 → Emmadictionnaire les paysCHFRITensemble CH

Trois besoins, trois rangements. Le pays déjà noté ne compte pas deux fois.

L’ordre compte ?

Arrivée, playlist, notes dans l’ordre des tests : une liste.

On cherche par une clé ?

Le numéro d’un ami, le stock d’un article, les votes d’un candidat : un dictionnaire.

Pas de doublon ?

Les pays visités, les mots différents d’un texte : un ensemble.

Ce que coûte chaque opération

Lire par indice

  • listerapide
  • dictionnairenon
  • ensemblenon

Trouver par clé ou valeur

  • listelent (parcours)
  • dictionnairerapide en moyenne
  • ensemblerapide en moyenne

Ajouter

  • listerapide à la fin (amorti)
  • dictionnairerapide en moyenne
  • ensemblerapide en moyenne

Ordre

  • listeordre d’ajout
  • dictionnaireselon le langage
  • ensembleaucun

Doublons

  • listepermis
  • dictionnaireclés uniques
  • ensembleinterdits

« Rapide » veut dire un temps qui ne grandit pas avec le nombre d’éléments : O(1). « Lent », un temps proportionnel à ce nombre : O(n).

tempsnombre d’éléments O(1) : rapide O(n) : proportionnel

Pour garder les éléments triés en permanence, Java propose aussi TreeMap et TreeSet.

Exercice 3

Liste, dictionnaire ou ensemble ?

Range chaque besoin dans la bonne case.

Listel'ordre compte
Dictionnaireclé → valeur
Ensemblepas de doublon
Exercice 4

Compte les mots d'une phrase

Remets les lignes dans l'ordre. texte contient « le chat voit le chien et le chat » ; le programme doit afficher {'le': 3, 'chat': 2, 'voit': 1, 'chien': 1, 'et': 1}.

  1. compte = {}
  2. for mot in texte.split():
  3. if mot in compte:
  4. compte[mot] += 1
  5. else:
  6. compte[mot] = 1
  7. print(compte)

Remettre la classe dans l’ordre

Dans la vraie vie

Pour la photo de classe, le photographe range les élèves du plus grand au plus petit.

LéaNoahEmmaTomZoé même taille même taille

Deux élèves de même taille ? Il les laisse dans l’ordre où ils étaient.

sorted(…, key=…)

Trier, c’est choisir un critère : la taille pour la photo, la note dans le code. En Python, sorted() renvoie une nouvelle liste triée, list.sort() trie sur place. Le paramètre key dit selon quoi trier.

Cinq élèves

La même classe triée deux fois : par prénom, puis par note décroissante. Fais défiler.

Cinq élèvesordre d'origine

L'ordre d'origine : celui dans lequel les élèves ont été ajoutés à la liste.

Le tri, en Python

Trier une liste de tuples par prénom, puis par note décroissante avec key et reverse.

Pythontri.py
classe = [("Léa", 5.5), ("Noah", 4.5), ("Emma", 6),
          ("Tom", 4.5), ("Zoé", 5.5)]

par_nom = sorted(classe)       # compare d'abord le prénom
par_note = sorted(classe, key=lambda e: e[1], reverse=True)
print([nom for nom, note in par_note])
# ['Emma', 'Léa', 'Zoé', 'Noah', 'Tom']

Un tri stable.

Les tris de Python sont garantis stables : deux éléments égaux pour le critère gardent leur ordre d’origine5. Léa reste devant Zoé (5,5), Noah devant Tom (4,5). Collections.sort en Java et sort en JavaScript sont stables aussi.

La fiche en six cartes

Liste

Garde l’ordre et les doublons ; lire par indice et ajouter à la fin sont rapides, insérer au début décale tout.

Dictionnaire

Des clés uniques associées à des valeurs ; le hachage désigne la case où chercher.

Clé absente

KeyError avec les crochets en Python ; None, null ou undefined avec get.

Ensemble

Refuse les doublons et teste l’appartenance rapidement, en moyenne.

Choisir

L’ordre compte : liste. On cherche par clé : dictionnaire. Pas de doublon : ensemble.

Trier

sorted(…, key=…) ; les tris de Python, Java et JavaScript sont stables.

Dix questions, zéro faute

Mode survie

Dix questions tirées au hasard, de plus en plus difficiles. À la première erreur, la partie s’arrête : lis l’explication, puis relance.

Mon conseil : pour chaque question, demande-toi si l’ordre compte, si on cherche par clé, et si les doublons sont permis.

10 questions · zéro faute · chronomètre

Sources

  1. Python Software Foundation, Le tutoriel Python : Structures de données (listes, ensembles, dictionnaires), documentation Python 3, consultée en 2026. docs.python.org
  2. Oracle, Java SE 21 API : ArrayList, consulté en 2026. docs.oracle.com
  3. Oracle, Java SE 21 API : HashMap, consulté en 2026. docs.oracle.com
  4. Oracle, Java SE 21 API : HashSet, consulté en 2026. docs.oracle.com
  5. Python Software Foundation, Sorting Techniques (tris stables, paramètre key), documentation Python 3, consultée en 2026. docs.python.org
  6. MDN, Map (ordre d'insertion, get et undefined), consulté en 2026. developer.mozilla.org
  7. Oracle, Java SE 21 API : ArrayDeque (opérations en temps constant amorti), consulté en octobre 2026. docs.oracle.com

Fiche relue et sourcée en septembre 2026, refaite en récit en octobre 2026. Extraits exécutés : Python 3.14, Java 21, Node 25 ; les numéros de case de la HashMap ont été calculés avec Java. Extraits Go et R relus (compilateurs non disponibles).

Glisser pour continuer vers Prog 11 : Exceptions
Gymnase 3