Listes et autres structures linéaires⚓︎
Lorsqu'on pense à une liste au sens le plus commun du terme, on pense à quelque chose qui évolue dans le temps, comme la liste des courses :
En Informatique et en Mathématiques, la liste est une structure abstraite permettant de modéliser et manipuler une collection de données.
La Liste Informatique⚓︎
Une définition informatique très générique et plutôt orientée allocation mémoire est celle donnée par D. E. Knuth dans [1]
Définition
Une liste linéaire est une séquence de \(n \geq 0\) noeuds (au sens cases mémoire) X[1], X[2], ..., X[n]
dont la propriété structurelle essentielle est la position relative des éléments : X[1]
est le premier noeud et X[n]
le dernier et si \(1 \lt k \lt n\), X[k]
est précédé de X[k - 1]
et suivi de X[k + 1]
.
De plus, les opérations possibles sur cette structure pourraient inclure :
- Accéder au \(k^e\) noeud pour l'examiner ou le modifier
- Insérer un noeud avant ou après le \(k^e\) noeud
- Effacer le \(k^e\) noeud
- Combiner deux ou plusieurs listes pour en former une seule
- Éclater une liste en deux ou plusieurs listes
- Faire une copie d'une liste
- Déterminer le nombre de noeuds d'une liste
- Trier les noeuds par ordre croissant sur le contenu de certains champs du noeud
- Rechercher la liste des occurrences d'une noeud avec une valeur particulière dans un de ses champs
Cette définition est très générale et peut correspondre effectivement à notre liste de courses :
- il y a effectivement un premier et un dernier item
- chacun des autres possède un suivant et un précédent
- on peut retirer un élément de la liste
- en rajouter, plutôt à la fin
- on peut compter combien il y a d'items
- ou encore vérifier qu'un article est présent dans la liste
Cette définition est une abstraction, et pour être utilisée réellement dans un programme doit s'appuyer sur une implémentation.
D.E. Knuth distingue deux implémentations :
- Une implémentation par allocation séquentielle des cellules
- Une implémentation par chaînage
Implémentation séquentielle⚓︎
La méthode la plus simple de stocker une liste en mémoire est d'avoir des cases mémoires contiguës. Il s'agit alors de tableau dynamique, ce que sont par exemple les list
de Python. On y retrouve d'ailleurs presque toutes les opérations en fonctions ou méthodes prédéfinies :
- l'opérateur
[ ]
qui permet d'accéder et de modifier un noeud (on emploiera plutôt le terme d'élément) puisque leslist
sont mutables ; - les méthodes
insert
etappend
permettent l'insertion remove
etpop
permettent le retrait d'éléments- la concaténation
+
et la concaténation multiple*
pour combiner - l'éclatement n'existe pas nativement
copy
pour une copie superficielle (etdeepcopy
du modulecopy
pour une copie récursive)len
donne la longueur d'une listesort
etsorted
pour le tris, en place ou pas- pas de fonction native pour obtenir directement la liste des occurrences, mais une fonction pour obtenir l'indice de la première occurrence
Implémentation par chaînage⚓︎
D. E. Knuth :
Instead of keeping a linear list in sequential memory locations, we can make use of a much more flexible scheme in which each node contains a link to the next node of the list
Contrairement à l'implémentation séquentielle, ici l'insertion et la suppression se font en temps constant dès lors qu'on a le noeud où doit se faire l'opération.
C'est cette définition d'une liste que donnent T. H. Cormen et al. dans [2]. Dans le chapitre sur les structures de données, les piles et les files sont introduites puis les listes chaînées.
Il existe une quantité de chaînages possibles, citons les plus connus :
- chaînage simple
- double chaînage (chaque noeud pointe un suivant et un précédent, ou éventuellement un seul des deux pour les extrémités de la liste)
- circulaire
liste simplement chaînée
Début d'un code possible (il n'y a que peu de méthodes implantées ici) :
class Node:
def __init__(self, val, suivant=None):
self.val = val
self.suivant = suivant
class Liste:
def __init__(self):
self.head = None
self.lenght = 0
def __str__(self):
s = '['
p = self.head
while p is not None:
s += f'{p.val}, '
p = p.suivant
return s[:-2] + ']'
def __len__(self):
return self.lenght
def __getitem__(self, k):
if k >= len(self):
raise IndexError('index out of range')
else:
p = self.head
for _ in range(k):
p = p.suivant
return p
def is_empty(self):
return self.lenght == 0
def after(self, val, node=None):
"""insère la valeur val après le noeud node -- gère le cas de la liste vide"""
new_node = Node(val)
if not self.is_empty():
new_node.suivant = node.suivant
node.suivant = new_node
else:
self.head = new_node
self.lenght += 1
>>> test = Liste()
>>> test.after(10)
>>> print(test)
[10]
>>> test[0].val
10
>>> test.after(-2, test.head)
>>> print(test)
[10, -2]
>>> test.after(1, test.head)
>>> print(test)
[10, 1, -2]
>>> test.after(3, test[2])
>>> print(test)
[10, 1, -2, 3]
liste circulaire doublement chaînée
Là encore il s'agit d'un début de code... à chacun de compléter
class Node:
def __init__(self, val, left=None, right=None):
self.val = val
self.left = left or self
self.right = right or self
class Circular:
def __init__(self):
self.head = None
self.lenght = 0
def __len__(self):
return self.lenght
def is_empty(self):
return len(self) == 0
def insert_left(self, val, node=None):
new_node = Node(val)
if self.is_empty():
self.head = new_node
else:
self.head.left.right = new_node
new_node.left = self.head.left
new_node.right = self.head
self.head.left = new_node
self.lenght += 1
ici un graphique
>>> test = Circular()
>>> test.insert_left(10)
>>> test.head.val
10
La liste est déjà circulaire avec un unique élément :
>>> test.head.left.left.left.val
10
Et bien doublement chaînée :
>>> test.head.left.right.left.left.right.val
10
Bibliographie⚓︎
[1]: The Art of Computer Programming, D. E. Knuth, vol.1 Fundamental Algorithms, Third Edition, 2011
[2]: Introduction à l'algorithmique, T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein, 2e Edition, 2004