Listes, tuples et dictionnaires

5.1 Introduction et Motivation

Pour traiter des volumes importants de données, les variables simples ne suffisent plus. Il devient nécessaire de regrouper et d'ordonner des collections d'objets au sein de structures de données structurées. En informatique, le choix d'une structure de données influence directement la complexité temporelle et spatiale des algorithmes associés. Ce chapitre présente les concepts théoriques de structures de données linéaires (tableaux et listes chaînées), puis détaille trois structures fondamentales de Python : les listes (mutables, ordonnées), les tuples (immuables, ordonnés) et les dictionnaires (tables d'association clé-valeur). Nous aborderons également les mécanismes de mutabilité, de copie, et des algorithmes fondamentaux de parcours et de recherche.

5.2 Structures de Données Linéaires en Mémoire

Une structure de données linéaire est une collection finie et ordonnée d'éléments. En machine, la représentation physique de cette structure en mémoire distingue principalement deux modèles fondamentaux : les tableaux et les listes chaînées.

5.2.1 Les Tableaux (Structures Statiques)

Un tableau associe une suite de variables de même type à des emplacements mémoire contigus.

Puisque les éléments sont homogènes, ils occupent tous le même nombre de cases mémoire $d$. Ainsi, l'adresse mémoire de l'élément d'indice $k$ se calcule directement par :

$$\text{Adresse}(k)=a+k\times d$$

où $a$ désigne l'adresse de départ du tableau.

• Avantage : L'accès en lecture/écriture à n'importe quel élément d'indice $k$ s'effectue en temps constant ($O(1)$).
• Inconvénient : La structure est statique. La taille du tableau est fixée à la création et ne peut plus être modifiée par la suite, car l'espace contigu situé au-delà de la dernière case n'est pas garanti libre.

5.2.2 Les Listes Chaînées (Structures Dynamiques)

Une liste chaînée associe à chaque élément (ou maillon) deux informations : la donnée elle-même et un pointeur (adresse mémoire) indiquant la localisation de l'élément suivant.

• Avantage : La structure est dynamique. On peut facilement ajouter ou retirer des éléments en ajustant les pointeurs sans déplacer les données préexistantes.
• Inconvénient : L'accès direct à l'élément d'indice $k$ n'est pas possible. Il est nécessaire de parcourir les $k-1$ maillons précédents depuis la tête de liste, engendrant un coût d'accès linéaire ($O(k)$).

5.2.3 La classe list de Python : Une Structure Hybride

En Python, le type list est une structure hybride cherchant à concilier les avantages des deux mondes : être une structure de données dynamique tout en offrant un accès direct aux éléments en temps constant ($O(1)$).

En interne, Python gère un tableau dynamique de pointeurs d'objets. L'accès indexé est direct ($O(1)$) car le tableau de pointeurs est contigu. Lorsque la capacité maximale du tableau sous-jacent est atteinte lors de l'ajout d'un élément, Python alloue automatiquement un nouveau tableau plus grand (sur-allocation amortie) et y copie les pointeurs existants.

5.3 Les Listes

5.3.1 Construction, Accès et Slicing

Une liste en Python se déclare entre crochets, les éléments (pouvant être hétérogènes) étant séparés par des virgules :

a = [0, 1, 'abc', 4.5, 'de', 6]
b = [[], [1], [1, 2], [1, 2, 3]] # Liste imbriquée (2D)

5.3.2 Indexation Positive et Négative

Les index positifs commencent à 0 (premier élément) et s'arrêtent à $\text{len}(L)-1$ (dernier élément). Les index négatifs démarrent à $-1$ (dernier élément) et vont jusqu'à $-\text{len}(L)$ (premier élément). L'index négatif $-k$ coïncide avec l'index positif $\text{len}(L)-k$.

5.3.3 Slicing (Découpage)

La syntaxe générale d'une découpe s'écrit :

$$\text{sous\_liste}=L[\text{deˊbut}:\text{fin}:\text{pas}]$$

L = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
L[2:9:3] # Renvoie [2, 5, 8]
L[3::2] # Renvoie [3, 5, 7, 9]
L[::-1] # Renvoie [10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0]

5.3.4 Méthodes Principales des Listes

5.3.5 Mutabilité et Modification par Tranche

Puisqu'une liste est mutable, on peut modifier ses éléments individuellement ou par tranches (slice assignment) :

L = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
L[3] = 'a' # L devient [0, 1, 2, 'a', 4, 5, 6, 7, 8, 9, 10]
L[3:7] = ['abc'] # L devient [0, 1, 2, 'abc', 7, 8, 9, 10]

5.3.6 Les Pièges de l'Affectation Simple

L'affectation simple d'une variable à une autre ne réalise pas une copie de l'objet, mais crée simplement un alias (un nouveau nom pointant vers la même adresse mémoire).

L1 = [1, 2, 3]
L2 = L1 # L1 et L2 pointent vers le même objet physique (id identique)
L1[0] = 99
print(L2) # Affiche [99, 2, 3] (L2 a également été modifié !)

5.3.7 Copie Superficielle vs Copie Profonde

Pour copier réellement une liste, on doit instancier un nouvel objet. On distingue deux niveaux de copie :

• Copie superficielle (shallow copy) : crée une nouvelle liste contenant des références vers les mêmes objets enfants. Obtenue via L.copy() ou L[:].
• Copie profonde (deep copy) : recrée récursivement tous les objets contenus dans la liste. Unique méthode sûre pour les listes imbriquées. Obtenue via copy.deepcopy().

from copy import deepcopy
L1 = [[1, 2], [3, 4]]
L2 = L1.copy() # Copie superficielle
L3 = deepcopy(L1) # Copie profonde

L1[0][0] = 99
print(L2[0][0]) # Affiche 99 ! Les sous-listes sont partagées
print(L3[0][0]) # Affiche 1 ! Parfaitement indépendante

5.3.8 Création par Compréhension

La compréhension de liste fournit un formalisme élégant pour filtrer et transformer des données :

$$L=[f(x)\text{ for }x\text{ in }E\text{ if }P(x)]$$

triplets = [(x, y, z) for x in range(1, 20)
                      for y in range(x, 20)
                      for z in range(y, 20)
                      if x**2 + y**2 == z**2]
# triplets vaut : [(3, 4, 5), (5, 12, 13), (6, 8, 10), (8, 15, 17), (9, 12, 15)]

5.4 Les Tuples

Un tuple est une séquence ordonnée d'éléments, similaire à une liste mais immuable : une fois créé, on ne peut ni modifier, ni ajouter, ni supprimer ses éléments.

5.4.1 Construction et Accès

# Définition d'un tuple
coordonnees = (10, 20)
seul_element = (42,) # Virgule obligatoire pour un tuple d'un élément
sans_parentheses = 1, 2, 3 # Tuple par virgules

# Accès (identique aux listes)
print(coordonnees[0]) # 10
print(coordonnees[-1]) # 20

Une tentative de modification (ex: coordonnees[0] = 30) lèvera une erreur de type TypeError ('tuple' object does not support item assignment).

5.4.2 Pourquoi utiliser un tuple plutôt qu'une liste ?

• Immuabilité : Un tuple peut servir de clé de dictionnaire (contrairement aux listes).
• Performance : Les tuples sont légèrement plus rapides et consomment moins de mémoire.
• Sémantique : Un tuple indique que les données sont de nature différente (ex: (nom, age, ville)), tandis qu'une liste contient généralement des éléments de même nature (ex: [note1, note2]).
• Sécurité : L'immuabilité évite les modifications accidentelles.

5.4.3 Packing et Unpacking

# Packing : groupe de valeurs
point = 3, 5 # équivalent à (3, 5)

# Unpacking : extraction dans des variables
x, y = point
print(x, y) # 3 5

# Échange de variables (grâce au tuple implicite)
a, b = 1, 2
a, b = b, a # Échange élégant !

# Unpacking avec *
premier, *reste = [1, 2, 3, 4]
print(premier) # 1
print(reste) # [2, 3, 4]

5.4.4 Comparaison Listes vs Tuples

5.5 Les Dictionnaires

Un dictionnaire est une collection non ordonnée d'associations clé-valeur. Chaque clé doit être unique et immuable (les listes ne peuvent pas être clés, mais les tuples oui).

5.5.1 Principe : Table de Hachage

En interne, un dictionnaire utilise une table de hachage. Une fonction de hachage transforme la clé en un index (généralement modulo la taille du tableau). L'accès à la valeur associée se fait en temps constant en moyenne ($O(1)$).