Pour avoir une compréhension claire de la liste chaînée unique, je vais implémenter la classe LinkedList en JavaScript.

Chaque nœud de la liste chaînée aura deux attributs : value &suivant, et la liste chaînée aura des attributs head, tail et length.

Push

Comment pouvons-nous pousser un nouveau nœud à la fin de notre liste? Faisons une fonction push. Tout d’abord, nous devons créer un nouveau nœud en utilisant la valeur donnée, vérifier si la liste a une tête (est-elle vide?) et n’oubliez pas d’incrémenter la taille de la liste.

Pop

En poussant, nous devons penser à éclater, en supprimant le dernier élément. S’il n’y a pas de nœud, retournez undefined, else, parcourez la liste jusqu’à ce que nous atteignions la queue, définissez la propriété suivante de l’avant-dernier nœud sur null, faites en sorte que l’avant-dernier soit la queue, n’oubliez pas de décrémenter la taille de la liste.

Shift

Pour supprimer le premier élément, décaler, comme d’habitude, vérifiez si la liste est vide. Tout d’abord, stockez la tête actuelle dans une variable, définissez la tête pour qu’elle soit la suivante de la tête actuelle, décrémentez la longueur.

Unshift

Pour insérer un nœud au début de la liste, vérifiez si la liste est vide, sinon, nous définissons la tête actuelle comme étant l’attribut suivant du nœud entrant, incrémente la taille.

Get

Même si la liste chaînée n’a pas d’index, nous sommes toujours en mesure de trouver le nœud par index donné. Assurez-vous d’abord que l’index donné est supérieur à zéro et inférieur ou égal à la longueur de la liste. Que nous parcourons la liste jusqu’à ce que nous atteignions l’index.

Set

Que faire si nous voulons changer un nœud dans notre liste? Nous trouvons le nœud avec get() et définissons le nœud avec des données données.

Insert

Lorsque nous voulons insérer un nouveau nœud dans la liste, vérifiez d’abord si l’index est supérieur à 0 et inférieur à la longueur. Si index est la longueur, nous utilisons simplement push(), si l’index est 0, nous utilisons unshift(). Pour les autres index, nous devons obtenir le nœud à l’index-1, et définir la propriété suivante de ce nœud pour être le nouveau nœud, et la propriété suivante du nouveau nœud pour être la propriété suivante précédente, puis nous incrémentons la longueur.

Remove

Contrairement à pop et unshift, la fonction remove supprimera le nœud par index donné. Comme d’habitude, vérifiez si l’index est valide, si l’index est égal à la longueur – 1 ou 0, utilisez pop ou shift. Sinon, nous obtenons le nœud à l’index-1, définissons la propriété suivante sur ce nœud pour être la propriété suivante de la propriété suivante, après, nous décrétons la taille.

Inverse

La question inverse ultime! Comment inverser la liste? Tout d’abord, nous échangeons la tête et la queue, déclarons suivant et précédent, définissons le précédent comme null. Nous parcourons la liste.