Aller au contenu

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 :

liste de courses liste de 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 :

  1. Accéder au \(k^e\) noeud pour l'examiner ou le modifier
  2. Insérer un noeud avant ou après le \(k^e\) noeud
  3. Effacer le \(k^e\) noeud
  4. Combiner deux ou plusieurs listes pour en former une seule
  5. Éclater une liste en deux ou plusieurs listes
  6. Faire une copie d'une liste
  7. Déterminer le nombre de noeuds d'une liste
  8. Trier les noeuds par ordre croissant sur le contenu de certains champs du noeud
  9. 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 :

  1. Une implémentation par allocation séquentielle des cellules
  2. 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 :

  1. l'opérateur [ ] qui permet d'accéder et de modifier un noeud (on emploiera plutôt le terme d'élément) puisque les list sont mutables ;
  2. les méthodes insert et append permettent l'insertion
  3. remove et pop permettent le retrait d'éléments
  4. la concaténation + et la concaténation multiple * pour combiner
  5. l'éclatement n'existe pas nativement
  6. copy pour une copie superficielle (et deepcopy du module copy pour une copie récursive)
  7. len donne la longueur d'une liste
  8. sort et sorted pour le tris, en place ou pas
  9. 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