Comment implémenter une liste liée en JavaScript

Si vous apprenez des structures de données, une liste chaînée est une structure de données que vous devez connaître. Si vous ne le comprenez pas vraiment ou comment il est implémenté en JavaScript, cet article est là pour vous aider.

Dans cet article, nous allons discuter de ce qu'est une liste liée, en quoi elle est différente d'un tableau et comment l'implémenter en JavaScript. Commençons.

Qu'est-ce qu'une liste liée?

Une liste chaînée est une structure de données linéaire similaire à un tableau. Cependant, contrairement aux tableaux, les éléments ne sont pas stockés dans un emplacement mémoire ou un index particulier. Au contraire, chaque élément est un objet distinct qui contient un pointeur ou un lien vers l'objet suivant de cette liste.

Chaque élément (communément appelé nœuds) contient deux éléments: les données stockées et un lien vers le nœud suivant. Les données peuvent être n'importe quel type de données valide. Vous pouvez le voir illustré dans le diagramme ci-dessous.

Image d'une liste liée

Le point d'entrée d'une liste chaînée est appelé la tête. La tête est une référence au premier nœud de la liste chaînée. Le dernier nœud de la liste pointe vers null. Si une liste est vide, la tête est une référence nulle.

En JavaScript, une liste liée ressemble à ceci:

const list = { head: { value: 6 next: { value: 10 next: { value: 12 next: { value: 3 next: null } } } } } };

Un avantage des listes liées

  • Les nœuds peuvent facilement être supprimés ou ajoutés d'une liste liée sans réorganiser toute la structure de données. C'est un avantage qu'il a par rapport aux tableaux.

Inconvénients des listes liées

  • Les opérations de recherche sont lentes dans les listes liées. Contrairement aux tableaux, l'accès aléatoire aux éléments de données n'est pas autorisé. Les nœuds sont accessibles de manière séquentielle à partir du premier nœud.
  • Il utilise plus de mémoire que les tableaux en raison du stockage des pointeurs.

Types de listes liées

Il existe trois types de listes liées:

  • Listes liées individuellement : chaque nœud contient un seul pointeur vers le nœud suivant. C'est ce dont nous avons parlé jusqu'à présent.
  • Listes doublement liées : chaque nœud contient deux pointeurs, un pointeur vers le nœud suivant et un pointeur vers le nœud précédent.
  • Listes liées circulaires: les listes liées circulaires sont une variante d'une liste chaînée dans laquelle le dernier nœud pointe vers le premier nœud ou tout autre nœud avant lui, formant ainsi une boucle.

Implémentation d'un nœud de liste en JavaScript

Comme indiqué précédemment, un nœud de liste contient deux éléments: les données et le pointeur vers le nœud suivant. Nous pouvons implémenter un nœud de liste en JavaScript comme suit:

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

Implémentation d'une liste liée en JavaScript

Le code ci-dessous montre l'implémentation d'une classe de liste liée avec un constructeur. Notez que si le nœud principal n'est pas passé, la tête est initialisée à null.

class LinkedList { constructor(head = null) { this.head = head } }

Mettre tous ensemble

Créons une liste chaînée avec la classe que nous venons de créer. Tout d' abord, nous créons deux nœuds de la liste, node1et node2et un pointeur de noeud 1 au noeud 2.

let node1 = new ListNode(2) let node2 = new ListNode(5) node1.next = node2

Ensuite, nous allons créer une liste liée avec l'extension node1.

let list = new LinkedList(node1)

Essayons d'accéder aux nœuds de la liste que nous venons de créer.

console.log(list.head.next.data) //returns 5

Quelques méthodes LinkedList

Ensuite, nous allons implémenter quatre méthodes d'aide pour la liste chaînée. Elles sont:

  1. Taille()
  2. clair()
  3. getLast ()
  4. getFirst ()

1. taille ()

Cette méthode renvoie le nombre de nœuds présents dans la liste chaînée.

size() { let count = 0; let node = this.head; while (node) { count++; node = node.next } return count; } 

2. effacer ()

Cette méthode vide la liste.

clear() { this.head = null; }

3. getLast ()

Cette méthode renvoie le dernier nœud de la liste chaînée.

getLast() { let lastNode = this.head; if (lastNode) { while (lastNode.next) { lastNode = lastNode.next } } return lastNode }

4. getFirst ()

Cette méthode renvoie le premier nœud de la liste chaînée.

getFirst() { return this.head; }

Sommaire

Dans cet article, nous avons expliqué ce qu'est une liste liée et comment elle peut être implémentée en JavaScript. Nous avons également discuté des différents types de listes chaînées ainsi que de leurs avantages et inconvénients généraux.

J'espère que vous avez aimé le lire.

Vous souhaitez être averti lorsque je publie un nouvel article? Cliquez ici.