Structures de données en Python

📚 Le cours : listes, tuples, dictionnaires et ensembles

Un programme garde rarement une seule valeur : il manipule des collections (les notes d'une classe, un annuaire, les mots d'un texte…). Python en propose quatre, qui diffèrent par ce qu'on peut leur faire : modifier leur contenu, garder l'ordre, accepter les doublons, retrouver un élément rapidement.

Les listes : créer et lire

Une liste s'écrit entre crochets. Ses éléments sont numérotés à partir de 0 ; un indice négatif compte depuis la fin (-1 est le dernier). Une tranche liste[debut:fin:pas] crée une nouvelle liste (le début est inclus, la fin est exclue).

notes = [12, 15, 9, 18]
print(notes[0], notes[-1], len(notes))
print(notes[1:3], notes[:2], notes[2:], notes[::2], notes[::-1])
print(15 in notes, 20 in notes)
vide = []
melange = [1, "a", 2.5, [3, 4]]
print(len(vide), melange[3][0])

12 18 4
[15, 9] [12, 15] [9, 18] [12, 9] [18, 9, 15, 12]
True False
0 3

Les listes : modifier

Une liste est modifiable : on peut changer un élément, en ajouter ou en retirer, sans en créer une nouvelle.

liste = [3, 1, 2]
liste.append(4)
liste.insert(0, 9)
liste.extend([5, 6])
print(liste)
liste.remove(1)
dernier = liste.pop()
premier = liste.pop(0)
print(liste, dernier, premier)
liste[0] = 100
del liste[1]
print(liste, liste.index(100), liste.count(100))

[9, 3, 1, 2, 4, 5, 6]
[3, 2, 4, 5] 6 9
[100, 4, 5] 0 1

• append(x) ajoute à la fin ; insert(i, x) insère à l'indice i ; extend(autre) ajoute tous les éléments d'une autre liste.
• remove(x) retire la première valeur égale à x ; pop() retire et renvoie le dernier élément, pop(i) celui d'indice i ; del liste[i] supprime sans rien renvoyer.
• index(x) donne la position de x (erreur s'il est absent) ; count(x) compte ses occurrences.

Trier une liste

liste.sort() trie en place (et renvoie None) ; sorted(liste) renvoie une nouvelle liste triée et laisse l'originale intacte. Les deux acceptent reverse=True et key=fonction pour trier selon un autre critère. Le tri est stable : deux éléments de même clé gardent leur ordre d'origine.

nombres = [5, 2, 9, 1]
print(sorted(nombres), nombres)
nombres.sort(reverse=True)
print(nombres)

mots = ["python", "C", "java", "Rust"]
print(sorted(mots))
print(sorted(mots, key=len))
print(sorted(mots, key=str.lower))

[1, 2, 5, 9] [5, 2, 9, 1]
[9, 5, 2, 1]
['C', 'Rust', 'java', 'python']
['C', 'java', 'Rust', 'python']
['C', 'java', 'python', 'Rust']

Les majuscules passent avant les minuscules dans l'ordre alphabétique de Python (leurs codes sont plus petits) : key=str.lower trie sans tenir compte de la casse.

Copier une liste : alias et copies

b = a ne copie pas la liste : a et b désignent le même objet, et modifier l'un modifie l'autre. Pour une copie indépendante, utilise a.copy(), list(a) ou a[:]. Attention : la copie est « superficielle », donc les listes imbriquées restent partagées (voir aliasing et copies).

a = [1, 2, 3]
b = a
c = a.copy()
b.append(4)
print(a, b, c)

grille = [[0] * 2 for _ in range(2)]
grille[0][0] = 1
print(grille)

[1, 2, 3, 4] [1, 2, 3, 4] [1, 2, 3]
[[1, 0], [0, 0]]

Les tuples

Un tuple s'écrit entre parenthèses (elles sont facultatives) : c'est une liste non modifiable. On l'utilise pour un petit groupe de valeurs liées (coordonnées, date) et pour renvoyer plusieurs valeurs d'une fonction. Le déballage (x, y = point) range chaque élément dans une variable, et permet d'échanger deux variables sans variable temporaire. Un tuple d'un seul élément s'écrit avec une virgule : (5,).

point = (3, 4)
x, y = point
print(x, y, point[0], len(point))

a, b = 1, 2
a, b = b, a
print(a, b)

premier, *reste = (10, 20, 30)
print(premier, reste)

seul = (5,)
print(type(seul), type((5)))

3 4 3 2
2 1
10 [20, 30]
<class 'tuple'> <class 'int'>

Les dictionnaires : lire et modifier

Un dictionnaire associe une valeur à chaque clé. On accède à une valeur par sa clé : d[cle] (erreur si elle manque) ou d.get(cle, defaut) (valeur par défaut si elle manque). Les clés sont uniques et doivent être non modifiables (nombre, texte, tuple). Depuis Python 3.7, un dictionnaire conserve l'ordre dans lequel on a ajouté ses clés.

eleve = {"nom": "Ada", "age": 17, "notes": [18, 15]}
print(eleve["nom"], eleve.get("age"), eleve.get("ville", "inconnue"))
eleve["ville"] = "Lyon"
eleve["age"] = 18
del eleve["notes"]
print(eleve)
print("nom" in eleve, "notes" in eleve, len(eleve))

Ada 17 inconnue
{'nom': 'Ada', 'age': 18, 'ville': 'Lyon'}
True False 3

Parcourir un dictionnaire

Une boucle for sur un dictionnaire parcourt ses clés. .keys(), .values() et .items() donnent respectivement les clés, les valeurs et les couples (clé, valeur). max(d, key=d.get) renvoie la clé qui a la plus grande valeur.

prix = {"pomme": 1.2, "poire": 1.5, "kiwi": 0.8}
for fruit in prix:
    print(fruit)
print(list(prix.keys()), list(prix.values()))
for fruit, p in prix.items():
    print(f"{fruit} : {p:.2f} €")
print(max(prix, key=prix.get))

pomme
poire
kiwi
['pomme', 'poire', 'kiwi'] [1.2, 1.5, 0.8]
pomme : 1.20 €
poire : 1.50 €
kiwi : 0.80 €
poire

Dictionnaires : compter et regrouper

Deux schémas reviennent sans cesse. Compter : compte[m] = compte.get(m, 0) + 1. Regrouper : groupes.setdefault(cle, []).append(x) crée la liste de la clé si elle n'existe pas encore, puis y ajoute x.

mots = ["a", "b", "a", "c", "a", "b"]
compte = {}
for m in mots:
    compte[m] = compte.get(m, 0) + 1
print(compte)

groupes = {}
for nom, classe in [("Ada", "1A"), ("Lin", "1B"), ("Max", "1A")]:
    groupes.setdefault(classe, []).append(nom)
print(groupes)

{'a': 3, 'b': 2, 'c': 1}
{'1A': ['Ada', 'Max'], '1B': ['Lin']}

Construire un dictionnaire

On peut construire un dictionnaire avec dict(zip(cles, valeurs)), avec une compréhension {cle: valeur for …}, ou le compléter avec update. pop(cle) retire une clé et renvoie sa valeur. Les valeurs peuvent elles-mêmes être des dictionnaires : c'est la structure du format JSON.

noms = ["Ada", "Lin"]
notes = [18, 17]
carnet = dict(zip(noms, notes))
carres = {n: n ** 2 for n in range(4)}
carnet.update({"Max": 12})
print(carnet)
print(carres)
print(carnet.pop("Lin"), carnet)

classe = {"1A": {"Ada": 18, "Max": 12}, "1B": {"Lin": 17}}
print(classe["1A"]["Ada"])
print(sum(sum(n.values()) for n in classe.values()))

{'Ada': 18, 'Lin': 17, 'Max': 12}
{0: 0, 1: 1, 2: 4, 3: 9}
17 {'Ada': 18, 'Max': 12}
18
47

Les ensembles

Un ensemble (set) ne contient que des valeurs distinctes et n'a pas d'ordre : les doublons disparaissent, et tester x in ensemble est très rapide. Il se prête aux opérations de la théorie des ensembles : réunion |, intersection &, différence -, différence symétrique ^. Attention : {} désigne un dictionnaire vide ; un ensemble vide s'écrit set().

a = {1, 2, 3, 3, 2}
b = {3, 4}
print(sorted(a), len(a))
print(sorted(a | b), sorted(a & b), sorted(a - b), sorted(a ^ b))
a.add(10)
a.discard(1)
print(sorted(a), 2 in a)

doublons = [3, 1, 3, 2, 1]
print(sorted(set(doublons)), list(dict.fromkeys(doublons)))
print(type({}), type(set()))

[1, 2, 3] 3
[1, 2, 3, 4] [3] [1, 2] [1, 2, 4]
[2, 3, 10] True
[1, 2, 3] [3, 1, 2]
<class 'dict'> <class 'set'>

L'ordre d'affichage d'un ensemble n'est pas garanti : on le trie avec sorted quand on veut un résultat stable. Pour supprimer les doublons en gardant l'ordre d'apparition, list(dict.fromkeys(liste)) fait l'affaire.

Quelle structure pour quel besoin ?

Le choix dépend surtout de la façon dont on retrouve ses données, car les coûts diffèrent : chercher une valeur dans une liste oblige à la parcourir (O(n)), alors que chercher une clé dans un dictionnaire ou une valeur dans un ensemble est en moyenne instantané (O(1)).

Tableaux à deux dimensions

Une matrice est une liste de listes : m[i][j] est la case de la ligne i et de la colonne j. On la construit avec une compréhension pour que chaque ligne soit un objet distinct (voir matrices en 2D).

matrice = [[1, 2, 3], [4, 5, 6]]
print(matrice[1][2], len(matrice), len(matrice[0]))
transposee = [[ligne[j] for ligne in matrice] for j in range(3)]
print(transposee)

6 2 3
[[1, 4], [2, 5], [3, 6]]

⚠️ Erreurs fréquentes

Un indice hors de la liste

Une liste de n éléments a des indices de 0 à n - 1. Lire un indice qui n'existe pas est une IndexError. Pour le dernier élément, utilise liste[-1].

liste = [1, 2, 3]
print(liste[3])

IndexError: list index out of range

liste = [1, 2, 3]
print(liste[-1], liste[len(liste) - 1])

3 3

Une clé absente du dictionnaire

d[cle] lève une KeyError si la clé n'existe pas. d.get(cle, defaut) renvoie une valeur par défaut, et cle in d permet de tester avant.

notes = {"Ada": 18}
print(notes["Lin"])

KeyError: 'Lin'

notes = {"Ada": 18}
print(notes.get("Lin", "absent"))

absent

Récupérer le résultat de append ou de sort

Les méthodes qui modifient une liste en place (append, sort, reverse, extend…) renvoient None. Écrire liste = liste.append(3) remplace la liste par None.

liste = [1, 2]
liste = liste.append(3)
print(liste)

None

liste = [1, 2]
liste.append(3)
print(liste)

[1, 2, 3]

Modifier un tuple

Un tuple n'est pas modifiable : on ne peut ni remplacer un élément, ni en ajouter. Pour « modifier », on crée un nouveau tuple (ou on choisit une liste dès le départ).

point = (3, 4)
point[0] = 1

TypeError: 'tuple' object does not support item assignment

point = (3, 4)
point = (1, point[1])
print(point)

(1, 4)

Une clé de dictionnaire modifiable

Les clés d'un dictionnaire (et les éléments d'un ensemble) doivent être non modifiables : une liste n'est pas acceptée, un tuple l'est.

d = {[1, 2]: "x"}

TypeError: unhashable type: 'list'

d = {(1, 2): "x"}
print(d[(1, 2)])

x

Multiplier une liste de listes

[[0] * 3] * 2 répète la même ligne deux fois : modifier une case modifie les deux lignes. Construis chaque ligne séparément avec une compréhension.

grille = [[0] * 3] * 2
grille[0][0] = 1
print(grille)

[[1, 0, 0], [1, 0, 0]]

grille = [[0] * 3 for _ in range(2)]
grille[0][0] = 1
print(grille)

[[1, 0, 0], [0, 0, 0]]

{} n'est pas un ensemble vide

vide = {}
vide.add(1)

AttributeError: 'dict' object has no attribute 'add'

vide = set()
vide.add(1)
print(vide)

{1}

Ajouter une clé pendant qu'on parcourt le dictionnaire

Changer la taille d'un dictionnaire pendant une boucle sur ce dictionnaire est interdit (RuntimeError). Parcours une copie de ses clés : list(d).

d = {"a": 1, "b": 2}
for cle in d:
    d[cle + "2"] = d[cle]

RuntimeError: dictionary changed size during iteration

d = {"a": 1, "b": 2}
for cle in list(d):
    d[cle + "2"] = d[cle]
print(d)

{'a': 1, 'b': 2, 'a2': 1, 'b2': 2}

📋 Aide-mémoire

Listes

Dictionnaires

Tuples

Ensembles