L’informatique est la manipulation de données numériques, un computer est un calculateur (computare en latin : compter). Face à l’explosion des données disponibles il est indispensable de les présenter et les organiser correctement.

Un exemple pour s’en rendre compte : vous avez devant vous vos manuels du lycée et vous devez traiter l’exercice de mathématiques 12 p. 58. Comment faites-vous ?

• vous parcourez la pile de livre depuis le premier jusqu’à trouver le bon livre
• vous feuilletez ce livre jusqu’à trouver la page 58
• vous lisez les titres des exercices jusqu’à trouver le numéro 12

Cela prend un peut moins d’une minute sans doute.

Maintenant faisons la même chose mais en considérant l’ensemble du CDI ! Il est hors de question de parcourir l’ensemble des étagères dans l’ordre jusqu’à trouver le bon livre… Heureusement, les livres/données sont organisés : chaque livre est classé selon son auteur, son thème… et les rayonnages sont organisés par thème et auteur.

Pour décrire cette situation, on parle en informatique de type de données abstrait

Un type de données abstrait (TDA) est un modèle mathématique permettant de décrire des données. Afin de simplifier les choses, retenons qu’un TDA :

• décrit les attributs d’un objet
• décrit les opérations réalisables sur cet objet. Ces opérations sont définies à l’aide de méthodes primitives

I. Interface

L’interface d’un TDA est sa spécification, la description de ses éléments constitutifs et de ses méthodes primitives. On ne rentre pas dans le détail du code des méthodes, on se contente de donner leurs spécifications (entrées, rôle et sorties)

Prenons l’exemple d’une liste chaînée. Cette structure est décrite ci-dessous :

Une liste chaînée est une structure de donnée permettant de stocker plusieurs valeurs de même type. La longueur de la liste n’est pas fixée a priori et peut évoluer au fil des ajouts et suppressions d’éléments.

Chaque élément \(x\) d’une liste chaînée comporte deux attributs :

• la valeur à stocker \(x.donnée\)
• un lien vers le prochain élément \(x.successeur\) : un élément contient un autre élément ! On peut ainsi se représenter la structure comme des éléments reliés le long d’une chaîne

La liste chaînée \(L\) quant à elle contient au minimum un attribut, la tête de la liste \(L.tête\) qui est le premier élément (données + successeur). La liste vide est telle que sa tête contient null (elle pointe vers un élément nul).

Le lien du dernier élément de la liste vaut lui aussi null (il ne pointe nulle part).

Du point de vue des primitives, les méthodes minimales à implémenter sont :

• la création d’une liste vide
• l’insertion d’un élément (au début de la liste ici). On suppose que l’élément est non null
• la suppression du premier élément

II. Implémentation

L’interface d’un type de données abstrait est son modèle théorique. Pour l’utiliser dans notre ordinateur, il faut le coder, l’implémenter.

Le point important à retenir est qu’une interface peut avoir plusieurs implémentations différentes : le type de données utilisé, l’algorithme utilisé dans une méthodes peuvent varier d’un programmeur à l’autre.

Voici une implémentation de la liste chaînée.

creation() :
  liste.tête = null

  retourne liste

On se contente de retourner une liste ne contenant aucun élément et dont la tête pointe vers null.

insertion(liste, nouveau) :
  nouveau.successeur = liste.tête
  liste.tête = nouveau

Remarque : on a supposé que nouveau n’était pas un élément vide.

On commence par faire pointer le nouvel élément vers l’ancienne tête de la liste puis on indique à la liste que sa tête est désormais le nouvel élément.

suppression(liste, element) :
  precedent = null
  x = liste.tête

  tant que x != element :
    precedent = x
    x = x.successeur

  si precedent = null :
    liste.tête = x.successeur
  sinon :
    precedent.successeur = x.successeur

Remarque : on a supposé que element faisait bien partie de la liste (et donc que la liste était non-vide)

Cette méthode est plus subtile. On utilise deux variables :

• precedent contient l’élément situé juste avant celui qui nous intéresse dans la liste
• x contient l’élément en cours

On commence ainsi par chercher l’élément à supprimer dans la liste. Un fois trouvé, on se contente le faire disparaître en disant que precedent pointe désormais vers le successeur de x. Il peut arriver que l’élément à supprimer soit à la tête de la liste. Dans ce cas, on met à jour cette tête. Concrètement, l’élément n’a pas été effacé de la mémoire de l’ordinateur, on l’a juste sorti de la liste châinée en supprimant ses références.

Voici une implémentation de la liste châinée en python. On commence par construire un élément :

class Element:
    """
    Classe décrivant les éléments utilisés dans les listes châinées
    Un élément possède :
        - une donnée (de type quelconque)
        - un successeur (un autre élément)
    """

    def __init__(self, donnee):
        self.donnee = donnee
        self.successeur = None

    def afficher(self):
        print(str(self.donnee) + " --> " + str(self.successeur), end="\n\n")


class Liste_Chainee:
    """
    Classe décrivant une liste simplement chaînée
    La liste est caractérisée par sa seule tête
    """

    def __init__(self):
        """
        Constructeur : renvoie la liste vide
        """
        self.tete = None

    def inserer(self, nouveau):
        """
        Insertion d'un élément à la tête de la liste
        """
        nouveau.successeur = self.tete
        self.tete = nouveau

    def supprimer(self, element):
        """
        Suppression de l'élément indiqué en argument
        """
        precedent = None
        x = self.tete

        while x != element:
            precedent = x
            x = x.successeur

        if precedent == None:
            self.tete = x.successeur
        else:
            precedent.successeur = x.successeur

    def afficher(self):
        """
        Affichage de la liste
        """
        s = ""

        pointeur = self.tete

        while pointeur != None:
            s += str(pointeur.donnee) + " --> "
            pointeur = pointeur.successeur

        print(s + "Vide", end="\n\n")

On peut alors exécuter le code suivant :

liste = Liste_Chainee()
liste.afficher()

elt1 = Element(1)
liste.inserer(elt1)
liste.afficher()

elt2 = Element(2)
liste.inserer(elt2)
liste.afficher()

elt3 = Element(3)
liste.inserer(elt3)
liste.afficher()

liste.supprimer(elt2)
liste.afficher()