Comment implémenter une structure de données de liste liée dans JavaScript?

JavaScript est un langage de programmation Web qui est utilisé pour rendre nos pages Web et nos applications Web dynamiques et interactives en leur donnant la possibilité de penser et d'agir. Comme tout autre langage de programmation, JavaScript propose des tableaux américains qui sont une collection d'éléments différents stockés en une seule variable. La limitation d'un tableau est qu'elle est stockée consécutivement dans une mémoire particulière de notre système, donc pour résoudre ce problème, nous utilisons une liste liée.

Liste liée

Les listes liées sont comme des tableaux, sauf que dans une liste liée, les éléments ne sont pas enregistrés dans un emplacement ou un index de mémoire spécifique et chaque élément est un objet indépendant distinct qui est connecté à l'élément suivant en ayant un pointeur ou un lien vers cet élément.

Chaque liste liée contient une tête (premier nœud), une longueur (taille de la liste liée) et une propriété de queue (dernier nœud), et chaque élément d'une liste liée est appelé un nœud et chaque nœud a une valeur stockée dedans et le lien vers le nœud suivant. Si le nœud actuel est la queue, le lien sera nul qui ne pointera pas vers aucun autre nœud. La liste liée ne contient pas d'index contrairement aux tableaux qui ont des index E.G 0,1,2… et ainsi de suite.

Les listes liées dans JavaScript peuvent être démontrées comme suit:

// Liste liée
const LinkedList =
// Chaque nœud a une valeur et un pointeur
// Le premier pointeur est l'en-tête
diriger:
Valeur: 6
suivant:
Valeur: 10
suivant:
Valeur: 12
suivant:
Valeur: 3
Suivant: null





;

L'avantage de la liste liée est que les éléments (nœuds) sont facilement ajoutés et supprimés de la liste liée sans ajuster toute la liste liée. L'inconvénient d'une liste liée est qu'elle a besoin de plus de mémoire pour le stockage, car nous avons maintenant un pointeur supplémentaire que nous stockons avec la valeur de l'élément.

Les listes liées sont de trois types décrits ci-dessous:

• La liste liée individuellement n'a qu'un seul pointeur pointant vers le nœud à côté.
• Le doublement lié est basé sur deux points dans lesquels le premier pointe vers le nœud qui est derrière et le second pointe vers le nœud à côté.
• La liste liée à la circulaire dont la queue contient un pointeur vers la tête et forme donc un cycle.

Implémentation de la liste liée

Laissez d'abord créer un nœud qui a deux propriétés une valeur et un pointeur pour lesquels nous créerons une classe avec le nom de Listnode Cela a ces deux propriétés:

class listNode
constructeur (valeur)
ce.valeur = valeur
ce.suivant = null

Maintenant que nous savons comment créer un nœud, créons une liste liée où la valeur par défaut de la tête sera nul:

classe LinkedList
constructeur (tête = null)
ce.tête = tête

Laissez maintenant initialiser la liste liée avec deux nœuds et ajouter un pointeur de la tête ou du nœud 1 au deuxième nœud:

var node1 = new listNode (3);
var node2 = new listNode (4);
node1.Next = node2;

L'étape suivante consiste à initialiser la liste liée avec Node1 de la manière suivante:

var list = new LinkedList (Node1);

L'ensemble du code est donné ci-dessous avec la connexion de la console la valeur Node2:

// Création de nœud
class listNode
constructeur (valeur)
// la valeur d'initialisation du constructeur et le pointeur suivant
ce.valeur = valeur
ce.suivant = null


classe LinkedList
// Constructeur de liste liée
constructeur (tête = null)
ce.tête = tête


// initialisation des nœuds créés
var node1 = new listNode (3);
var node2 = new listNode (4);
node1.Next = node2;
// initialisation de la liste liée
var list = new LinkedList (Node1);
// montrant la sortie du deuxième nœud
console.journal (liste.diriger.suivant.valeur) // 4

Méthodes de liste liée

Maintenant que nous avons terminé avec la mise en œuvre de la liste liée, jouons ou manipulons la liste liée en implémentant plus de méthodes pour utiliser les listes liées (méthodes d'aide):

La première méthode d'assistance que nous définirons est le taille() Méthode dans la classe Listin lié qui renverra la longueur de la liste liée:

size = () =>
Soit Count = 0;
Laissez Node = ceci.diriger;
// boucle pour itérer la liste liée
while (node)
Count ++;
nœud = nœud.suivant

Return Count;

Dans ce code d'abord, nous déclarons une variable fictive compter stocker 0 dedans puis stocker le pointeur de la tête dans le nœud variable. Ensuite, nous avons déclaré une boucle qui iratera sur la liste liée et incrément le compter variable.

La méthode suivante sera la méthode getFirst () Méthode où le pointeur de tête sera retourné:

getFirst = () =>
retourner ceci.diriger.valeur;

Nous pouvons également obtenir le dernier nœud de la liste liée de la manière suivante:

getLast = () =>
Laissez LastNode = ceci.diriger;
if (lastNode)
while (LastNode.suivant)
LastNode = LastNode.suivant


retourner LastNode.valeur

L'ensemble du code est maintenant donné ci-dessous avec affichant la sortie de la deuxième valeur de nœud, la taille de la liste liée, la première valeur de nœud et la dernière valeur de nœud dans le même ordre:

// Création de nœud
class listNode
constructeur (valeur)
ce.valeur = valeur
ce.suivant = null


// Création de la liste liée
classe LinkedList
constructeur (tête = null)
ce.tête = tête

size = () =>
Soit Count = 0;
Laissez Node = ceci.diriger;
// boucle pour itérer la liste liée
while (node)
Count ++;
nœud = nœud.suivant

Return Count;

getFirst = () =>
retourner ceci.diriger.valeur;

getLast = () =>
Laissez LastNode = ceci.diriger;
if (lastNode)
while (LastNode.suivant)
LastNode = LastNode.suivant


retourner LastNode.valeur


// initialisation des nœuds créés
var node1 = new listNode (3);
var node2 = new listNode (4);
node1.Next = node2;
// initialisation de la liste liée
var list = new LinkedList (Node1);
// montrant la sortie du deuxième nœud
console.log ("Deuxième valeur de nœud:", liste.diriger.suivant.valeur) // 4
// montrant la taille de la liste liée
console.journal ("Taille de la liste liée:", liste.taille());
// Affichage de la valeur du premier nœud
console.log ("Valeur du premier nœud:", liste.getFirst ());
// montrant la dernière valeur de nœud
console.journal ("Valeur du nœud dernier:", liste.getLast ());

Conclusion

Après les tableaux, une liste liée est la deuxième structure de données la plus utilisée dans n'importe quel langage de programmation. Une liste liée est comme un tableau qui stocke une collection d'éléments différents avec la différence étant que chaque élément (nœud) d'une liste liée est un objet contenant une valeur de l'élément et un pointeur pointant vers le nœud suivant, liant donc chaque élément et La deuxième différence est que les éléments ne sont pas enregistrés dans un emplacement de mémoire spécifique dans une liste liée.

Dans cet article, nous avons vu quelles sont les listes liées, les avantages et les inconvénients des listes liées, les types de listes liées et comment implémenter la structure des données de la liste liée en JavaScript.