Structure de données et algorithmes - Liste liée

Une liste chaînée est une séquence de structures de données, qui sont reliées entre elles via des liens.

La liste liée est une séquence de liens contenant des éléments. Chaque lien contient une connexion à un autre lien. La liste liée est la deuxième structure de données la plus utilisée après le tableau. Voici les termes importants pour comprendre le concept de liste liée.

  • Link - Chaque lien d'une liste liée peut stocker une donnée appelée élément.

  • Next - Chaque lien d'une liste liée contient un lien vers le lien suivant appelé Suivant.

  • LinkedList - Une liste liée contient le lien de connexion vers le premier lien appelé Premier.

Représentation de liste liée

La liste liée peut être visualisée comme une chaîne de nœuds, où chaque nœud pointe vers le nœud suivant.

Conformément à l'illustration ci-dessus, voici les points importants à considérer.

  • La liste liée contient un élément de lien appelé en premier.

  • Chaque lien porte un (des) champ (s) de données et un champ de lien appelé ensuite.

  • Chaque lien est lié à son lien suivant en utilisant son lien suivant.

  • Le dernier lien porte un lien nul pour marquer la fin de la liste.

Types de liste liée

Voici les différents types de liste chaînée.

  • Simple Linked List - La navigation des articles est uniquement en avant.

  • Doubly Linked List - Les éléments peuvent être parcourus en avant et en arrière.

  • Circular Linked List - Le dernier élément contient le lien du premier élément comme suivant et le premier élément a un lien vers le dernier élément comme précédent.

Opérations de base

Voici les opérations de base prises en charge par une liste.

  • Insertion - Ajoute un élément au début de la liste.

  • Deletion - Supprime un élément au début de la liste.

  • Display - Affiche la liste complète.

  • Search - Recherche un élément en utilisant la clé donnée.

  • Delete - Supprime un élément en utilisant la clé donnée.

Opération d'insertion

L'ajout d'un nouveau nœud dans une liste liée est une activité en plusieurs étapes. Nous allons apprendre cela avec des schémas ici. Tout d'abord, créez un nœud en utilisant la même structure et trouvez l'emplacement où il doit être inséré.

Imaginez que nous insérons un nœud B (NewNode), entre A (LeftNode) et C(RightNode). Puis pointez B. suivant vers C -

NewNode.next −> RightNode;

Cela devrait ressembler à ceci -

Maintenant, le nœud suivant à gauche doit pointer vers le nouveau nœud.

LeftNode.next −> NewNode;

Cela placera le nouveau nœud au milieu des deux. La nouvelle liste devrait ressembler à ceci -

Des étapes similaires doivent être prises si le nœud est inséré au début de la liste. Lors de son insertion à la fin, l'avant-dernier nœud de la liste doit pointer vers le nouveau nœud et le nouveau nœud pointera vers NULL.

Opération de suppression

La suppression est également un processus en plusieurs étapes. Nous apprendrons avec la représentation picturale. Tout d'abord, localisez le nœud cible à supprimer à l'aide d'algorithmes de recherche.

Le nœud gauche (précédent) du nœud cible doit maintenant pointer vers le nœud suivant du nœud cible -

LeftNode.next −> TargetNode.next;

Cela supprimera le lien qui pointait vers le nœud cible. Maintenant, en utilisant le code suivant, nous allons supprimer ce sur quoi le nœud cible pointe.

TargetNode.next −> NULL;

Nous devons utiliser le nœud supprimé. Nous pouvons garder cela en mémoire, sinon nous pouvons simplement désallouer la mémoire et effacer complètement le nœud cible.

Opération inverse

Cette opération est approfondie. Nous devons faire en sorte que le dernier nœud soit pointé par le nœud principal et inverser toute la liste chaînée.

Tout d'abord, nous allons à la fin de la liste. Il doit pointer vers NULL. Maintenant, nous allons le faire pointer vers son nœud précédent -

Nous devons nous assurer que le dernier nœud n'est pas le dernier. Nous aurons donc un nœud temporaire, qui ressemble au nœud principal pointant vers le dernier nœud. Maintenant, nous allons faire pointer tous les nœuds du côté gauche vers leurs nœuds précédents un par un.

À l'exception du nœud (premier nœud) pointé par le nœud principal, tous les nœuds doivent pointer vers leur prédécesseur, ce qui en fait leur nouveau successeur. Le premier nœud pointera vers NULL.

Nous allons faire pointer le nœud principal vers le nouveau premier nœud en utilisant le nœud temporaire.

La liste chaînée est maintenant inversée. Pour voir l'implémentation des listes liées dans le langage de programmation C, veuillez cliquer ici .