Les listes linéaires chaînées sont une structure des données essentielles. Tout développeur doit les comprendre et apprendre à les utiliser. Il est, ainsi, nécessaire de penser à écrire un code pour faciliter la tâche aux débutants. Néanmoins, un problème essentiel s'affiche : les listes linéaires chaînées sont une structure des données, tout comme les tableaux, que nous utilisons pour réaliser une tâche. Elles sont considérées comme un outil, non pas une finalité. Ecrire un code pour aider les débutants semble sans intérêt si on ne connaît pas le problème exact sur lequel ils travaillent.
Malgré cela, j'ai décidé d'écrire un petit code en Java pour implémenter une liste linéaire chaînée très basique et ensuite l'utiliser pour implémenter une file d'attente et une pile en se basant entièrement sur la définition de la liste linéaire chaînée.
Sans un exemple d'application réel, l'exemple reste très limité alors j'ai préféré de faire une liste linéaire chaînée d'entiers; j'ai laissé l'utilisation de la programmation générique pour d'autres exemples.
La liste linéaire chaînée est comme une chaîne de maillons. Chaque noeud est attaché au noeud suivant et il suffit de connaitre le premier noeud (appelé souvent "la tête") pour connaitre (et avoir accès) à tous les autres noeuds, mais, il suffit de le perdre pour perdre une partie de (ou bien toute) la liste chaînée.
Un noeud se compose de deux parties :
Pour déclarer une liste linéaire chainée, il suffit de déclarer sa tête, c'est à dire, un noeud. Par la suite, il faut faire attention pour ne pas le modifier ou bien le perdre.
En Java, les choses sont plus simples pour plusieurs raisons (qui découlent essentiellement de la POO) :
Dans cet exemple, la liste linéaire chaînée créée est exploitée pour implémenter une file d'attente et une pile.
La file d'attente est une structure des données qui permet de stocker des données et de les récupérer dans le même ordre de leur insertion. Elle respecte le principe du FIFO (First In, First Out). Comme les listes, les files d'attente sont des structures de données qui facilitent la résolution de quelques problèmes algorithmiques; elles sont vues comme un moyen et non pas une finalité.
La pile est une structure de données qui permet de stocker des données et de les récupérer dans l'ordre inverse de leur arrivée. Elle respecte le principe LIFO (Last In, First Out). Elle est, aussi, considérée comme un moyen et non pas une finalité.
Dans cet exemple, les files d'attente et les piles sont dotées d'une taille limite. Les listes permettent de stocker un nombre (théoriquement) illimité des données; il sera, des fois, nécessaire de mettre une limite pour ce nombre des données que la liste peut sauvegarder. Dans cet exemple, la taille limite peut prendre deux types de valeur :
Pourquoi une taille limite dans cet exemple ? Sans raison particulière. Comme j'ai déjà mentionné, il est difficile de mettre toutes les possibilités offertes par les listes, les files et les piles; il y en a des milliers, alors j'ai choisi l'une des plus simples pour l'implémenter.
Téléchargez le projet par ici.
Malgré cela, j'ai décidé d'écrire un petit code en Java pour implémenter une liste linéaire chaînée très basique et ensuite l'utiliser pour implémenter une file d'attente et une pile en se basant entièrement sur la définition de la liste linéaire chaînée.
Sans un exemple d'application réel, l'exemple reste très limité alors j'ai préféré de faire une liste linéaire chaînée d'entiers; j'ai laissé l'utilisation de la programmation générique pour d'autres exemples.
La liste linéaire chaînée est comme une chaîne de maillons. Chaque noeud est attaché au noeud suivant et il suffit de connaitre le premier noeud (appelé souvent "la tête") pour connaitre (et avoir accès) à tous les autres noeuds, mais, il suffit de le perdre pour perdre une partie de (ou bien toute) la liste chaînée.
Un noeud se compose de deux parties :
- Une valeur : ou bien les données à sauvegarder, cette partie peut contenir une variable d'un type simple comme elle peut contenir un enregistrement de plusieurs champs.
- Un pointeur vers l'élément suivant : ce pointeur (ou référence) représente le chaînage qui existe entre les neouds et garantit la navigation et le parcours de la liste.
Pour déclarer une liste linéaire chainée, il suffit de déclarer sa tête, c'est à dire, un noeud. Par la suite, il faut faire attention pour ne pas le modifier ou bien le perdre.
En Java, les choses sont plus simples pour plusieurs raisons (qui découlent essentiellement de la POO) :
- Java n'utilise pas une manipulation directe et libre des pointeurs parce que chaque référence à un objet est en réalité un pointeur.
- La composition des objets est très simple, ainsi, la partie "données" du noeud peut être un objet avec toutes les possibilités qu'une telle déclaration apporte.
- Java représente un mécanisme très puissant pour la gestion des exceptions. Cela peut être vu comme une solution aux problèmes liés aux valeurs inconnues qui peuvent surgir lors de la manipulation des listes linéaires chaînées. Par exemple, quelle valeur à retourner si on est en train de récupérer la 5ème valeur d'une liste de trois valeurs seulement. Toute valeur retournée est en réalité erronée. Il est possible d'envisager des solutions si, par exemple, la liste ne contient que des valeurs positives et dire que je vais retourner la valeur -1. Ce type de solution ne peut pas être utilisé dans les cas généraux et l'utilisation des exceptions restent de loin une meilleure solution.
Dans cet exemple, la liste linéaire chaînée créée est exploitée pour implémenter une file d'attente et une pile.
La file d'attente est une structure des données qui permet de stocker des données et de les récupérer dans le même ordre de leur insertion. Elle respecte le principe du FIFO (First In, First Out). Comme les listes, les files d'attente sont des structures de données qui facilitent la résolution de quelques problèmes algorithmiques; elles sont vues comme un moyen et non pas une finalité.
La pile est une structure de données qui permet de stocker des données et de les récupérer dans l'ordre inverse de leur arrivée. Elle respecte le principe LIFO (Last In, First Out). Elle est, aussi, considérée comme un moyen et non pas une finalité.
Dans cet exemple, les files d'attente et les piles sont dotées d'une taille limite. Les listes permettent de stocker un nombre (théoriquement) illimité des données; il sera, des fois, nécessaire de mettre une limite pour ce nombre des données que la liste peut sauvegarder. Dans cet exemple, la taille limite peut prendre deux types de valeur :
- La valeur nulle (le zéro, 0) : qui signifie que le nombre d'éléments de la liste est illimité.
- Une valeur positive : qui sera égale au nombre maximal des éléments que la liste peut contenir.
Pourquoi une taille limite dans cet exemple ? Sans raison particulière. Comme j'ai déjà mentionné, il est difficile de mettre toutes les possibilités offertes par les listes, les files et les piles; il y en a des milliers, alors j'ai choisi l'une des plus simples pour l'implémenter.
Téléchargez le projet par ici.
