Listes chaînées

Une liste chaînée (ou liste liée) est une structure de données composées d’une séquence d’éléments de liste.

Chaque enregistrement d’une liste chaînée est souvent appelé élément , nœud ou maillon.

La tête d’une liste est son premier nœud. La queue d’une liste peut se référer soit au reste de la liste après la tête, soit au dernier nœud de la liste.

Le champ de chaque nœud qui contient l’adresse du nœud suivant ou précédent est généralement appelé lien ou pointeur. Le contenu est placé dans un ou plusieurs autres champs appelés données, informations ou valeur.

Liste chaînée

Chaque élément (ou maillon) M  de la liste est composé :

  • d’un contenu utile M.val  (de n’importe quel type),
  • d’un pointeur M.suiv  pointant vers l’élément suivant de la séquence.

Le dernier élément de la liste possède un pointeur M.suiv vide :

 

Une liste chainée L  est entièrement définie par son maillon de tête L.tete, c’est à dire l’adresse de son premier maillon.

On peut également lui ajouter un attributAttribut Un attribut est un identifiant (un nom) décrivant une information stockée dans une base. Les attributs correspondent aux colonnes si la relation à laquelle il appartient est représentée sous forme de table. L.cur  pour mémoriser l’adresse d’un maillon « courant ».

 

Interface (primitives)

Il n’existe pas de normalisation pour les primitives de manipulation de liste; les plus fréquentes sont :

  • est_vide(L)  : renvoie vrai si la liste est vide
  • taille(L)  : renvoie le nombre d’éléments de la liste
  • get_dernier_maillon(L)  : renvoie le dernier élément de la liste
  • get_maillon_indice(L, i)  : renvoie le maillon d’indice i
  • ajouter_debut(L, d)  : ajoute un élément au début de la liste
  • ajouter_fin(L, d)  : ajout un maillon à la fin de la liste
  • inserer_apres(L, i, M)  : insert un maillon à l’indice i
  • supprimer_apres(L, M)  : supprime le maillon suivant le maillon M

Insertion d’un maillon

Pour insérer un maillon nM  après un maillon M , il faut :

  1. Faire pointer le pointeur nM.suiv  vers M.suiv
  2. Faire pointer le pointeur M.suiv  vers nM

    

Suppression d’un maillon

Pour supprimer le maillon suivant un maillon M , il faut :

  1. Faire pointer le pointeur M.suiv  vers M.suiv.suiv
  2. Détruire (effacer de la mémoire) le maillon M.suiv

     

Remarque : dans certains langages disposants d’un dispositif de ramasse-miettes (comme Python par exemple), le simple fait de ne plus être référencé détruit l’objet Maillon. Dans d’autres langages, il faut explicitement détruire l’objet, et par conséquent, en garder une référence avant l’étape 1.

 

Implémentationimplémentation Réalisation d'un produit informatique à partir de documents, mise en œuvre, développement. Codage d'un algorithme dans un langage informatique.

Python

On peut implémenter un maillon de liste chaînée en Python à l’aide d’une classe Maillon  :

Son attribut suiv  est de type Maillon , ou bien vaut None  si le maillon est le dernier de la liste.

 

Et une liste chaînée s’implémente par une classe ListeC  :

Son attribut tete  est de type Maillon , ou bien vaut None  si la liste est vide.

 

On peut alors créer une liste ainsi :

 

On implémente la fonction est_vide(L) simplement de cette manière :

 

 

Implémenter en Python les fonctions taille(L) et get_dernier_maillon(L).

 

Correction
Ordre de complexité : \(\mathcal{O}(n)\) (\(n\) = taille de la liste)

 

Implémenter en Python la fonction get_maillon_indice(L, i).

 

Correction
Ordre de complexité : \(\mathcal{O}(n)\) (\(n\) = taille de la liste)

 

En suivant les schémas des interfaces d’insertion et de suppression de maillon, implémenter en Python les fonctions ajouter_debut(L, nM) , ajouter_fin(L, nM)  et ajouter_apres(L, M, nM), puis supprimer_debut(L) , supprimer_fin(L)  et supprimer_apres(L, M) (ces dernières fonctions doivent retourner le maillon supprimé).

 

Correction
Ordre de complexité : \(\mathcal{O}(1)\)

 

Ordre de complexité : \(\mathcal{O}(n)\) (\(n\) = taille de la liste)

 

Ordre de complexité : \(\mathcal{O}(1)\)

 

Ordre de complexité : \(\mathcal{O}(1)\)

 

Ordre de complexité : \(\mathcal{O}(n)\) (\(n\) = taille de la liste)

 

Ordre de complexité : \(\mathcal{O}(1)\)

 

 

 

Implémenter les fonctions suivantes :

  • renverser(L)  : renverse, sur place, la liste chainée L
  • concatener(L1, L2)  : retourne une nouvelle liste, résultat de la concaténation des listes L1  et L2 .

 

 

 

Récursivité

La structure même de liste chainée est récursive : chaque maillon d’une liste chainée est le début d’une nouvelle liste chainée.

Réécrire l’ensemble des définitions (classes et fonctions d’interface) précédentes en programmation orientée objet, et sous forme récursive !

 

 

C, C++

On peut implémenter un maillon de liste chaînée en C à l’aide d’un objet structure Maillon  :

Son attribut suiv  est de type Maillon.

Remarque : *suiv  est de type structure Maillon, tandis que suiv  est un pointeur, c’est à dire l’adresse de *suiv.

 

Et une liste chaînée s’implémente par une structure ListeC  :

Son attribut tete  est de type Maillon.

 

On peut alors créer une liste ainsi :

Remarque : &M1  signifie « adresse de M1 »

 

 


Liste doublement chaînée

Chaque élément (ou maillon) M  de la liste est composé :

  • d’un contenu utile M.val  (de n’importe quel type),
  • d’un pointeur M.suiv pointant vers l’élément suivant de la séquence,
  • d’un pointeur M.prec pointant vers l’élément précédent de la séquence.

Le dernier élément de la liste possède un pointeur M.suiv vide : 

et le premier un pointeur M.prec vide : 

 

Interface

Il n’existe pas de normalisation pour les primitives de manipulation de liste; les plus fréquentes sont :

  • est_vide(L)  : renvoie vrai si la liste est vide
  • taille(L)  : renvoie le nombre d’éléments de la liste
  • get_dernier_maillon(L)  : renvoie le dernier élément de la liste
  • get_maillon_indice(L, i)  : renvoie le maillon d’indice i
  • ajouter_debut(L, d)  : ajoute un élément au début de la liste
  • ajouter_fin(L, d)  : ajout un maillon à la fin de la liste
  • inserer_apres(L, i, M)  : insert un maillon à l’indice i
  • supprimer_apres(L, M)  : supprime le maillon suivant le maillon M

Implémentation

Implémenter en Python les fonctions précédentes.

Vous aimerez aussi...

Laisser un commentaire

Votre adresse de messagerie ne sera pas publiée. Les champs obligatoires sont indiqués avec *

*

code