Introduction

Commençons par le commencement. Avant de parler de liste, parlons de tableaux.

Tableau

Un tableau est un ensemble de valeurs ordonnées de même type ou de type différent. Pour représenter un tableau, on affiche les valeurs séparées par des virgules et encadrées par des crochets.

Exemple : [4, 7, 5]

Attention, un tableau n'est pas extensible ! Ce défaut permet toutefois un point positif : l'accès à un élément se fait en temps constant.

Pour le comprendre, il faut savoir comment un tableau est stocké dans la mémoire de notre ordinateur.

Adresse	Valeur
0870	x = 3
0871	t[0] = 4
0872	t[1] = 7
0873	t[2] = 5
0874	y = 9

Voici une représentation synthétique de la mémoire de notre ordinateur. On remarque que les éléments du tableau t sont placés de manière contiguë et ordonnée dans la mémoire. Ainsi, pour insérer un nouvel élément dans notre tableau, il faudra copier ce tableau dans un nouvel espace libre dans la mémoire.

En Python, nous n'avons pas de tableau, mais des listes. Même si elles utilisent la même syntaxe, ces listes ont été implémentés de manière à pouvoir être extensibles.

Implémentation

Mais ça veut dire quoi Implémentation ? Ça veut dire qu'on a cherché comment représenter un concept (ici une liste) en informatique.

Par exemple, avec le TP des Fractions, on a cherché à implémenter des fractions en Python.

Les développeurs ont choisi d'implémenter les listes avec des tableaux. Ainsi, lorsqu'il faut rajouter un élément, si le tableau est plein, on double sa taille. Cela permet de diminuer le nombre de fois où on met à jour la taille du tableau. Par contre, si on veut insérer un élément au milieu, il faudra déplacer tous les éléments, et c'est une énorme perte de temps. C'est pourquoi il est recommandé de n'utiliser que les méthodes .append() et .pop() qui ont un effet sur la fin de la liste.

t.insert(0, v)

# est équivalent à faire

t.append(None)
for i in range(len(t) - 1, 0, -1):
    t[i] = t[i - 1]
t[0] = v

Le nombre d'opérations est donc proportionnel au nombre d'éléments dans la liste. Cela signifie que si on a 10 millions d'éléments, alors on va devoir faire 10 millions d'opérations pour insérer un élément en début de liste. On parle aussi d'une complexité temporelle de \(\mathcal{O}(n)\) avec \(n\) le nombre d'éléments dans la liste.

Dans ce cours, nous verrons une première implémentation des listes via des listes chaînées, qui apportera une solution au problème d'insertion.