Chapitre 5 : Listes chaînées
Notion de liste chaînée
Une liste (simplement) chaînée est une structure de données représentant un ensemble ordonné d'éléments qui sont stockés en mémoire sous la forme de maillons (ou de cellules).
Si une liste chaînée est vide, son unique maillon est remplacé par None. Sinon son maillon contient :
- une valeur appelée la tête de la liste,
- un pointeur vers une liste chaînée (éventuellement vide) appelée la queue de la liste.
On donne ci-dessous une représentation schématique d'une liste chaînée L :
Implémentation avec deux classes Maillon et Liste
On donne une implémentation des listes chaînées à partir de deux classes Maillon et Liste :
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81 | class Maillon:
def __init__(self, tete, queue):
"""
Crée une instance de la classe Maillon.
- Entrées : tete (type quelconque), queue (instance de la classe Liste)
"""
self.tete = tete
self.queue = queue
class Liste:
def __init__(self, maillon):
"""
Crée une instance de la classe Liste.
- Entrée : maillon (instance de la classe Maillon, ou None pour créer une liste vide)
"""
self.maillon = maillon
def est_vide(self):
"""
Détermine si la liste est vide.
- Sortie : (booléen, True si la liste est vide, False sinon)
"""
return self.maillon is None
def tete(self):
"""
Renvoie la première valeur de la liste.
- Sortie : None si la liste est vide, sinon la valeur située à l'indice 0 dans la liste
"""
if self.est_vide():
return None
else:
return self.maillon.tete
def queue(self):
"""
Renvoie la queue de la liste, c'est-à-dire la liste privée de son premier maillon.
- Sortie : (instance de la classe Liste)
"""
if self.est_vide():
raise ValueError("la liste est vide")
else:
return self.maillon.queue
def nb_elements(self):
"""
Compte le nombre d'éléments de la liste.
- Sortie : (entier, nombre de valeurs présentes dans la liste)
"""
if self.est_vide():
return 0
else:
liste = self.queue()
return 1 + liste.nb_elements()
def inserer_en_tete(self, elem):
"""
Insère un maillon en début de liste.
- Entrée : elem (type quelconque)
"""
self.maillon = Maillon(elem, Liste(self.maillon))
def supprimer_en_tete(self):
"""
Supprime un maillon en début de liste.
"""
if self.est_vide():
raise ValueError("la liste est vide")
else:
self.maillon = self.queue().maillon
def __str__(self):
"""
Permet l'affichage des éléments de la liste via un appel à la fonction print.
"""
chaine = ""
liste = self
for k in range(self.nb_elements()):
chaine = chaine + f"{liste.tete()} "
liste = liste.queue()
return chaine
|
Avec cette implémentation, une liste vide se définit de la façon suivante :
| L1 = Liste(Maillon(3, Liste(Maillon(5, Liste(Maillon(6, Liste(None)))))))
L2 = Liste(None)
L2.inserer_en_tete(1)
L2.inserer_en_tete(2)
L2.inserer_en_tete(3)
|
Les listes L1 et L2 définies ci-dessus se représentent ainsi :
Exercices et activités
Exercices
Activités