Organisation en mémoire

Pour amener à une implémentation efficace des listes, nous allons commencer par nous interroger sur la façon dont les données sont stockées en mémoire.

Une description simplifiée

Ce qui suit ne correspond pas à la réalité. Les méthodes de gestion mémoire peuvent être très compliquées et les données à stocker très variées. L'approche qui suit permet de comprendre l'essentiel.

Imaginons que la mémoire soit une grille ou chaque case est numérotée de 1 à n. Le numéro d'une case mémoire est son adresse. Connaissant l'adresse, on sait trouver le contenu de la variable. On suppose également que chaque case ne peut contenir qu'une donnée élémentaire, par exemple un nombre.

Le langage va ainsi pouvoir énoncer des règles comme :

Quand on écrit n = None, le langage associe à n à une case mémoire qui contiendra la valeur 0.
Quand on écrit x = 5, le langage associe x à une case mémoire y écrit la valeur 1 qui signifie que x est une donnée unique, à chercher dans la case immédiatement suivante.
Quand on écrit t = [4,13,48], le langage associe t à une case mémoire et y écrit la valeur 3 qui signifie que t est un groupe de 3 valeurs à chercher dans les cases suivantes. Dans un premier temps, on procédera de même pour une liste L=4:13:48.

n = None
x = 5
t = [4, 13, 48]

nom	adresse
n	6
x	12
t	16

Dans les cas ci-dessus, on voit que, du moment que l'on sait la place à occuper, on peut réserver des cases mémoires. La difficulté posée par la liste est justement que sa taille est variable.

Exercice 1

Complétez comme précédemment en supposant qu'à la création d'un élément en mémoire, on occupe toujours la première case libre.

x = 5
L = 4:5
y = 3
L[0] = x + 1
Ajout 3 à la suite de L

nom	adresse
x
L
y

L'ajout final pose un problème, lequel ?

Exercice 2

n = None
L = 4:13:48
Ajout 21 suite de L
Supprimer L[0]
Ajout 15 suite de L
Ajout 17 suite de L
Ajout 91 suite de L

nom	adresse
L	16
n	22

Cette fois, au gré des créations et suppressions, la mémoire se trouve occupée selon la figure – case grise = case occupée. On ne se soucie que de L que l'on modifie et de n qui va poser problème.

Là encore, quel difficulté rencontre-t-on ?

Dans nos exemples, L représentent une collection de plusieurs données. On a choisi jusqu'ici de stoker tous les éléments de L à la suite dans la mémoire. C'est pratique car quand on connaît l'adresse de la case L[0], on trouve aussitôt la case L[2] par exemple. C'est le principe d'un tableau. Mais cela crée des difficultés quand on veut modifier la taille de L. Or c'est justement ce que l'on veut faire avec une liste !

Notion de pointeur

Ajoutons un ingrédient à notre langage : la possibilité d'écrire l'adresse d'une case comme une donnée. J'écrirais &15 pour dire adresse 15.

Exercice 3

Dans la grille ci-dessous représentant la mémoire, une variable L est initialisée. Cette variable représente une liste.

nom	adresse
L	6

Devinez quel est le contenu de cette liste.
Que faudrait-il faire pour ajouter la valeur 31 à la suite de cette liste ?
Que faudrait-il faire pour enlever la première valeur de cette liste ?
Comment fait-on pour atteindre L[2] ?

On a dit qu'une liste était une structure séquentielle. Vous devez maintenant mieux comprendre ce que cela signifie. La liste telle qu'on vient de la présenter est appelée liste chaînée. Par rapport à un tableau, il est extrêmement simple d'ajouter ou retirer un élément. En revanche, atteindre un élément prend plus de temps.

Exercice 4

Pour bien saisir la différence, on envisage deux structures de données L et T. La première est une liste et la seconde un tableau. On suppose que T est un tableau dynamique, c'est à dire qu'on voudrait pouvoir lui ajouter ou retirer des éléments.

L = 9:11:7:31
T = [9,11,7,31]

nom	adresse
L	8
T	1

Comment gérer dans la mémoire les opérations suivantes :

Accéder à T[3]
Accéder à L[3]
Supprimer T[0] sans modifier le fait que T → 1
Supprimer L[0] sans modifier le fait que L → 8