En 2009, je me suis lancé le défi d’écrire un article de blog par semaine pendant toute l’année. J’avais lu que la meilleure façon d’obtenir plus de trafic sur un blog était de poster régulièrement. Un article par semaine semblait être un objectif réaliste étant donné toutes les idées d’articles que j’avais, mais il s’est avéré que j’étais loin d’avoir 52 idées. J’ai fouillé dans certains chapitres à moitié écrits de ce qui allait devenir JavaScript professionnel et j’ai trouvé beaucoup de matériel sur des sujets informatiques classiques, notamment les structures de données et les algorithmes. J’ai pris ce matériel et l’ai transformé en plusieurs posts en 2009 et (et quelques-uns en 2012), et j’ai reçu beaucoup de commentaires positifs à leur sujet.

Maintenant, au dixième anniversaire de ces posts, j’ai décidé de les mettre à jour, de les republier et de les développer en utilisant JavaScript en 2019. Il a été intéressant de voir ce qui a changé et ce qui n’a pas changé, et j’espère que vous les apprécierez.

Qu’est-ce qu’une liste chaînée?

Une liste chaînée est une structure de données qui stocke plusieurs valeurs de manière linéaire. Chaque valeur dans une liste liée est contenue dans son propre nœud, un objet qui contient les données ainsi qu’un lien vers le nœud suivant de la liste. Le lien est un pointeur vers un autre objet de nœud ou null s’il n’y a pas de nœud suivant. Si chaque nœud n’a qu’un seul pointeur vers un autre nœud (le plus souvent appelé next) alors la liste est considérée comme une liste singulièrement liée (ou juste liée) alors que si chaque nœud a deux liens (généralement previous et next) alors elle est considérée comme une liste doublement liée. Dans ce post, je me concentre sur les listes singulièrement liées.

Pourquoi utiliser une liste liée ?

Le principal avantage des listes liées est qu’elles peuvent contenir un nombre arbitraire de valeurs tout en utilisant uniquement la quantité de mémoire nécessaire pour ces valeurs. La préservation de la mémoire était très importante sur les anciens ordinateurs où la mémoire était rare. À l’époque, un tableau intégré en C nécessitait que vous spécifiiez le nombre d’éléments que le tableau pouvait contenir et le programme réservait cette quantité de mémoire. Réserver cette mémoire signifiait qu’elle ne pouvait pas être utilisée pour le reste du programme ou pour tout autre programme exécuté en même temps, même si la mémoire n’était jamais remplie. Sur les machines à faible mémoire, vous pouviez facilement manquer de mémoire disponible en utilisant des tableaux. Les listes liées ont été créées pour contourner ce problème.

Bien qu’initialement destinées à une meilleure gestion de la mémoire, les listes liées sont également devenues populaires lorsque les développeurs ne savaient pas combien d’éléments un tableau contiendrait finalement. Il était beaucoup plus facile d’utiliser une liste chaînée et d’ajouter des valeurs si nécessaire que de deviner avec précision le nombre maximal de valeurs qu’un tableau pourrait contenir. En tant que telles, les listes chaînées sont souvent utilisées comme base pour les structures de données intégrées dans divers langages de programmation.

Le type intégré JavaScript Array n’est pas implémenté comme une liste chaînée, bien que sa taille soit dynamique et soit toujours la meilleure option pour commencer. Vous pourriez passer toute votre carrière sans avoir besoin d’utiliser une liste chaînée en JavaScript, mais les listes chaînées sont toujours un bon moyen d’apprendre à créer vos propres structures de données.

La conception d’une liste chaînée

La partie la plus importante d’une liste chaînée est sa structure de nœuds. Chaque nœud doit contenir des données et un pointeur vers le nœud suivant de la liste. Voici une représentation simple en JavaScript:

class LinkedListNode { constructor(data) { this.data = data; this.next = null; }}

Dans la classe LinkedListNode, la propriété data contient la valeur que l’élément de la liste chaînée doit stocker et la propriété next est un pointeur vers l’élément suivant de la liste. La propriété next commence par null parce que vous ne connaissez pas encore le nœud suivant. Vous pouvez ensuite créer une liste liée en utilisant la classe LinkedListNode comme ceci :

// create the first nodeconst head = new LinkedListNode(12);// add a second nodehead.next = new LinkedListNode(99);// add a third nodehead.next.next = new LinkedListNode(37);

Le premier nœud d’une liste liée est généralement appelé la tête, donc l’identifiant head dans cet exemple représente le premier nœud. Le deuxième nœud est créé et assigné à head.next pour créer une liste avec deux éléments. Un troisième nœud est ajouté en l’assignant à head.next.next, qui est le pointeur next du deuxième nœud de la liste. Le pointeur next du troisième nœud de la liste reste null. L’image suivante montre la structure de données résultante.

La structure d’une liste chaînée vous permet de parcourir toutes les données en suivant le pointeur next de chaque nœud. Voici un exemple simple de la façon de parcourir une liste chaînée et d’imprimer chaque valeur sur la console:

let current = head;while (current !== null) { console.log(current.data); current = current.next;}

Ce code utilise la variable current comme pointeur qui se déplace dans la liste chaînée. La variable current est initialisée à la tête de la liste et la boucle while continue jusqu’à ce que current soit null. À l’intérieur de la boucle, la valeur stockée sur le nœud current est imprimée, puis le pointeur next est suivi jusqu’au nœud suivant.

La plupart des opérations de listes chaînées utilisent cet algorithme de traversée ou quelque chose de similaire, donc la compréhension de cet algorithme est importante pour comprendre les listes chaînées en général.

La classe LinkedList

Si vous écriviez une liste chaînée en C, vous pourriez vous arrêter à ce point et considérer que votre tâche est terminée (bien que vous utiliseriez une struct au lieu d’une classe pour représenter chaque nœud). Cependant, dans les langages orientés objet comme JavaScript, il est plus habituel de créer une classe pour encapsuler cette fonctionnalité. Voici un exemple simple:

const head = Symbol("head");class LinkedList { constructor() { this = null; }}

La classe LinkedList représente une liste chaînée et contiendra des méthodes pour interagir avec les données qu’elle contient. La seule propriété est une propriété symbole appelée head qui contiendra un pointeur vers le premier nœud de la liste. Une propriété de symbole est utilisée au lieu d’une propriété de chaîne de caractères pour faire comprendre que cette propriété n’est pas destinée à être modifiée en dehors de la classe.

Ajouter de nouvelles données à la liste

Ajouter un élément dans une liste chaînée nécessite de parcourir la structure pour trouver le bon emplacement, de créer un nouveau nœud et de l’insérer à la place. Le seul cas particulier est lorsque la liste est vide, auquel cas il suffit de créer un nouveau nœud et de l’affecter à head:

const head = Symbol("head");class LinkedList { constructor() { this = null; } add(data) { // create a new node const newNode = new LinkedListNode(data); //special case: no items in the list yet if (this === null) { // just set the head to the new node this = newNode; } else { // start out by looking at the first node let current = this; // follow `next` links until you reach the end while (current.next !== null) { current = current.next; } // assign the node into the `next` pointer current.next = newNode; } }}

La méthode add() accepte un seul argument, n’importe quelle donnée, et l’ajoute à la fin de la liste. Si la liste est vide (this est null) alors vous assignez this égal au nouveau nœud. Si la liste n’est pas vide, alors vous devez traverser la liste déjà existante pour trouver le dernier nœud. La traversée se fait dans une boucle while qui commence à this et suit les liens next de chaque nœud jusqu’à ce que le dernier nœud soit trouvé. Le dernier nœud a une propriété next égale à null, il est donc important d’arrêter la traversée à ce point plutôt que lorsque current est null (comme dans la section précédente). Vous pouvez alors affecter le nouveau nœud à cette propriété next pour ajouter les données dans la liste.

La complexité de la méthode add() est O(n) parce que vous devez traverser toute la liste pour trouver l’emplacement où insérer un nouveau nœud. Vous pouvez réduire cette complexité à O(1) en suivant la fin de la liste (généralement appelée la queue) en plus de la tête, ce qui vous permet d’insérer immédiatement un nouveau nœud à la bonne position.

Récupération des données de la liste

Les listes liées ne permettent pas un accès aléatoire à son contenu, mais vous pouvez toujours récupérer les données dans n’importe quelle position donnée en traversant la liste et en retournant les données. Pour ce faire, vous ajouterez une méthode get() qui accepte un index basé sur zéro des données à récupérer, comme ceci :

class LinkedList { // other methods hidden for clarity get(index) { // ensure `index` is a positive value if (index > -1) { // the pointer to use for traversal let current = this; // used to keep track of where in the list you are let i = 0; // traverse the list until you reach either the end or the index while ((current !== null) && (i < index)) { current = current.next; i++; } // return the data if `current` isn't null return current !== null ? current.data : undefined; } else { return undefined; } }}

La méthode get() vérifie d’abord que index est une valeur positive, sinon elle renvoie undefined. La variable i est utilisée pour garder la trace de la profondeur à laquelle la traversée a été effectuée dans la liste. La boucle elle-même est la même traversée de base que vous avez vue précédemment avec la condition ajoutée que la boucle doit sortir lorsque i est égale à index. Cela signifie qu’il y a deux conditions sous lesquelles la boucle peut sortir :

1. current est null, ce qui signifie que la liste est plus courte que index.
2. i est égal à index, ce qui signifie que current est le nœud dans la position index.

Si current est null alors undefined est retourné et sinon current.data est retourné. Cette vérification garantit que get() ne lancera jamais une erreur pour un index qui n’est pas trouvé dans la liste (bien que vous puissiez décider de lancer une erreur au lieu de retourner undefined).

La complexité de la méthode get() varie de O(1) lors de la suppression du premier nœud (aucune traversée n’est nécessaire) à O(n) lors de la suppression du dernier nœud (la traversée de la liste entière est nécessaire). Il est difficile de réduire la complexité car une recherche est toujours nécessaire pour identifier la bonne valeur à renvoyer.

Suppression de données d’une liste chaînée

Supprimer des données d’une liste chaînée est un peu délicat car vous devez vous assurer que tous les pointeurs next restent valides après la suppression d’un nœud. Par exemple, si vous voulez supprimer le deuxième nœud d’une liste à trois nœuds, vous devez vous assurer que la propriété next du premier nœud pointe désormais vers le troisième nœud au lieu du deuxième. En sautant le deuxième nœud de cette façon, vous le supprimez effectivement de la liste.

L’opération de suppression est en fait deux opérations :

1. Trouver l’indice spécifié (le même algorithme que dans get())
2. Supprimer le nœud à cet indice

Trouver l’indice spécifié est le même que dans la méthode get(), mais dans cette boucle, vous devez également suivre le nœud qui vient avant current car vous devrez modifier le pointeur next du nœud précédent.

Il y a aussi quatre cas particuliers à considérer :

1. La liste est vide (aucune traversée n’est possible)
2. L’indice est inférieur à zéro
3. L’indice est supérieur au nombre d’éléments de la liste
4. L’indice est égal à zéro (suppression de la tête)

Dans les trois premiers cas, l’opération de suppression ne peut pas être achevée, et il est donc logique de lancer une erreur ; le quatrième cas particulier nécessite de réécrire la propriété this. Voici à quoi ressemble l’implémentation d’une méthode remove():

class LinkedList { // other methods hidden for clarity remove(index) { // special cases: empty list or invalid `index` if ((this === null) || (index < 0)) { throw new RangeError(`Index ${index} does not exist in the list.`); } // special case: removing the first node if (index === 0) { // temporary store the data from the node const data = this.data; // just replace the head with the next node in the list this = this.next; // return the data at the previous head of the list return data; } // pointer use to traverse the list let current = this; // keeps track of the node before current in the loop let previous = null; // used to track how deep into the list you are let i = 0; // same loops as in `get()` while ((current !== null) && (i < index)) { // save the value of current previous = current; // traverse to the next node current = current.next; // increment the count i++; } // if node was found, remove it if (current !== null) { // skip over the node to remove previous.next = current.next; // return the value that was just removed from the list return current.data; } // if node wasn't found, throw an error throw new RangeError(`Index ${index} does not exist in the list.`); }}

La méthode remove() vérifie d’abord deux cas particuliers, une liste vide (this est null) et un index qui est inférieur à zéro. Une erreur est lancée dans les deux cas.

Le cas spécial suivant est lorsque index est 0, ce qui signifie que vous supprimez la tête de liste. La nouvelle tête de liste doit être le deuxième nœud de la liste, donc vous pouvez définir this égal à this.next. Cela n’a pas d’importance s’il n’y a qu’un seul nœud dans la liste, car this serait finalement égal à null, ce qui signifie que la liste est vide après la suppression. Le seul piège est de stocker les données de la tête originale dans une variable locale, data, afin qu’elles puissent être retournées.

Avec trois des quatre cas spéciaux pris en charge, vous pouvez maintenant procéder à une traversée similaire à celle trouvée dans la méthode get(). Comme mentionné précédemment, cette boucle est légèrement différente dans la mesure où la variable previous est utilisée pour garder la trace du nœud qui apparaît juste avant current, car cette information est nécessaire pour proprement supprimer un nœud. Similaire à get(), lorsque la boucle sort current peut être null, indiquant que l’index n’a pas été trouvé. Si cela se produit alors une erreur est lancée, sinon, previous.next est mis à current.next, supprimant effectivement current de la liste. Les données stockées sur current sont retournées à la dernière étape.

La complexité de la méthode remove() est la même que celle de get() et va de O(1) lors de la suppression du premier nœud à O(n) lors de la suppression du dernier nœud.

Faire la liste itérable

Pour être utilisées avec la boucle JavaScript for-of et la déstructuration des tableaux, les collections de données doivent être itérables. Les collections JavaScript intégrées telles que Array et Set sont itérables par défaut, et vous pouvez rendre vos propres classes itérables en spécifiant une méthode de génération Symbol.iterator sur la classe. Je préfère d’abord implémenter une méthode de générateur values() (pour correspondre à la méthode trouvée sur les classes de collection intégrées) et ensuite avoir Symbol.iterator appeler values() directement.

La méthode values() n’a besoin que d’effectuer une traversée basique de la liste et yield des données que chaque nœud contient :

class LinkedList { // other methods hidden for clarity *values(){ let current = this; while (current !== null) { yield current.data; current = current.next; } } () { return this.values(); } }

La méthode values() est marquée d’un astérisque (*) pour indiquer que c’est une méthode de générateur. La méthode parcourt la liste, en utilisant yield pour retourner chaque donnée qu’elle rencontre. (Notez que la méthode Symbol.iterator n’est pas marquée comme un générateur car elle renvoie un itérateur de la méthode de générateur values().)

Utilisation de la classe

Une fois terminée, vous pouvez utiliser l’implémentation de la liste chaînée comme ceci:

const list = new LinkedList();list.add("red");list.add("orange");list.add("yellow"); // get the second item in the listconsole.log(list.get(1)); // "orange"// print out all itemsfor (const color of list) { console.log(color);}// remove the second item in the list console.log(list.remove(1)); // "orange" // get the new first item in the listconsole.log(list.get(1)); // "yellow"// convert to an arrayconst array1 = ;const array2 = ;

Cette implémentation de base d’une liste chaînée peut être complétée par une propriété size pour compter le nombre de nœuds dans la liste, et d’autres méthodes familières telles que indexOf(). Le code source complet est disponible sur GitHub à mon projet Computer Science in JavaScript.

Conclusion

Les listes liées ne sont pas quelque chose que vous êtes susceptible d’utiliser tous les jours, mais elles sont une structure de données fondamentale en informatique. Le concept d’utilisation de nœuds qui pointent les uns vers les autres est utilisé dans de nombreuses autres structures de données sont intégrées dans de nombreux langages de programmation de niveau supérieur. Une bonne compréhension du fonctionnement des listes liées est importante pour une bonne compréhension globale de la façon de créer et d’utiliser d’autres structures de données.

Pour la programmation JavaScript, il est presque toujours préférable d’utiliser les classes de collection intégrées telles que Array plutôt que de créer les vôtres. Les classes de collection intégrées ont déjà été optimisées pour une utilisation en production et sont bien prises en charge dans tous les environnements d’exécution.