Imaginons un tableau contenant des milliards d'éléments. Comment supprimer un élément en plein milieu du tableau ? Pourquoi pas créer un deuxième tableau dans lequel on recopie toutes nos valeurs (sauf celles que l'on veut supprimer) ? Cela marche bien, mais cette opération est longue et coûteuse en mémoire. On peut essayer de décaler le tableau en réécrivant sur la valeur que l'on veut supprimer, grâce à ça on fait des économies de mémoire mais cela prend beaucoup de temps. Et comment ajouter un élément dans notre tableau ? De même, on peut recréer un tableau en recopiant nos valeurs et en ajoutant au passage le nouvel élément. On peut aussi faire des économies de mémoire en décalant les éléments vers la droite pour laisser un espace au milieu afin d'insérer notre nouvel élément. Cependant, cette solution prend trop de temps et ceci nous pousse à comprendre que les tableaux ne sont pas adaptés à toutes les situations.
Face à ces problèmes de temps, et de mémoire, on a besoin d'une nouvelle structure de données souple, dynamique, et qui nous permet d'insérer et de supprimer des éléments facilement : la liste chaînée.
Une liste chaînée (linked list en anglais) est une structure de données auto référentielle, c'est-à-dire que chacun de ses éléments pointe vers l'élément suivant que l'on appelle des nœuds (node). À partir de cette définition on peut déjà établir le contenu d'un élément d'une liste chaînée :
Le dernier pointeur de la liste chaînée pointe sur la valeur
NULL, pour indiquer la fin de la liste.
Les deux structures de données sont différentes, et ont leurs avantages et leurs inconvénients, aucune n'est meilleure que l'autre mais il faut savoir quand utiliser la bonne structure au bon moment :
tableau[2]).
Pour manipuler correctement les listes chaînées, il faut connaître quelques fonctions basiques pour ajouter un élément, le supprimer, rechercher un élément précis dans la liste, etc.
créerListe :
Initialiser la liste à NULL
supprimerListe :
Pour chaque élément de la liste
Supprimer l'élément actuel
ajoutTête (élément) :
Faire pointer le nouvel élément vers le premier élément de la liste
ajoutFin (élément) :
Parcourir la liste jusqu'à la fin
Faire pointer le dernier élément vers l'élément donné en paramètre
Faire pointer l'élément donné en paramètre sur NULL
ajoutÉlément (élément, index) :
Parcourir la liste jusqu'à arriver à l'élément situé avant l'index donné
Faire pointer l'élément actuel sur le nouvel élément
Faire pointer le nouvel élément sur le prochain
supprimerTête :
Supprimer l'élément en tête de liste
supprimerFin :
Parcourir la liste jusqu'à l'avant-dernier élément
Supprimer l'élément suivant
Faire pointer l'élément sur NULL (pour indiquer la fin de la liste)
supprimerÉlément (index) :
Parcourir la liste jusqu'à arriver à l'élément situé avant l'index donné
Faire pointer l'élément actuel sur le pointeur de l'élément à supprimer
Supprimer l'élément suivant
estVide :
Si le premier élément de la liste est NULL
Retourner vrai
Sinon
Retourner fauxSoit \(N\) le nombre d'éléments de la liste chaînée.
créerListe : \(O(1)\)supprimerListe : \(O(N)\)ajoutTête : \(O(1)\)ajoutFin : \(O(N)\)ajoutÉlément : \(O(N)\)supprimerTête : \(O(1)\)supprimerFin : \(O(N)\)supprimerÉlément : \(O(N)\)estVide : \(O(1)\)Une implémentation en C des fonctions présentées au-dessus :
#include <stdio.h>
#include <stdlib.h>
typedef struct Noeud Noeud;
struct Noeud
{
Noeud *suivant;
int donnee;
};
typedef Noeud *Liste;
void creerListe(Liste *liste)
{
*liste = NULL;
}
void supprimerListe(Liste *liste)
{
Noeud *iListe;
for(iListe = *liste; iListe != NULL; ) {
Noeud *temp;
temp = iListe->suivant;
free(iListe);
iListe = temp;
}
}
void ajouterTete(Liste *liste, int donnee)
{
Noeud *nouveau;
nouveau = malloc(sizeof(Noeud));
nouveau->suivant = *liste;
nouveau->donnee = donnee;
*liste = nouveau;
}
void ajouterFin(Liste *liste, int donnee)
{
Noeud *nouveau;
Noeud *iListe;
nouveau = malloc(sizeof(Noeud));
nouveau->suivant = NULL;
nouveau->donnee = donnee;
for(iListe = *liste; iListe->suivant != NULL; iListe = iListe->suivant)
;
iListe->suivant = nouveau;
}
void ajouterElement(Liste *liste, int donnee, int index)
{
Noeud *nouveau;
Noeud *iListe;
int iEle;
iListe = *liste;
for(iEle = 0; iEle < index - 1; ++iEle)
iListe = iListe->suivant;
nouveau = malloc(sizeof(Noeud));
nouveau->suivant = iListe->suivant;
nouveau->donnee = donnee;
iListe->suivant = nouveau;
}
void supprimerTete(Liste *liste)
{
Noeud *temp;
temp = (*liste)->suivant;
free(*liste);
*liste = temp;
}
void supprimerFin(Liste *liste)
{
Noeud *iListe;
for(iListe = *liste; iListe->suivant->suivant != NULL; iListe = iListe->suivant)
;
free(iListe->suivant);
iListe->suivant = NULL;
}
void supprimerElement(Liste *liste, int index)
{
Noeud *iListe;
int iEle;
iListe = *liste;
for(iEle = 0; iEle < index - 1; ++iEle)
iListe = iListe->suivant;
Noeud *temp;
temp = iListe->suivant;
iListe->suivant = temp->suivant;
free(temp);
}
int estVide(Liste *liste)
{
if(*liste == NULL)
return 1;
else
return 0;
}
int main(void)
{
Liste liste;
creerListe(&liste);
printf("%d\n", estVide(&liste));
// 1
ajouterTete(&liste, 42);
// 42
ajouterTete(&liste, 2);
// 2 42
ajouterFin(&liste, 69);
// 2 42 69
ajouterElement(&liste, 7, 2);
// 2 42 7 69
supprimerTete(&liste);
// 42 7 69
supprimerFin(&liste);
// 42 7
ajouterFin(&liste, 2);
supprimerElement(&liste, 1);
// 42 2
printf("%d\n", estVide(&liste));
// 0
supprimerListe(&liste);
return 0;
}Le code est relativement simple à comprendre et à utiliser, une connaissance des pointeurs est cependant nécessaire.
Si vous programmez en C++, la STL (Standard Template Library) fournit une implémentation de liste chaînée ainsi que des fonctions de base pour les manipuler : http://www.cplusplus.com/reference/list/list/.
Il existe plusieurs variantes de la liste chaînée qui sont pratiques dans certains problèmes précis.
La liste double chaînée (doubly linked list) consiste à ce que chaque élément de la liste possède deux pointeurs :
Cette structure est légèrement plus coûteuse en mémoire et en opération, mais rend le déplacement au sein de la liste plus pratique car on peut la parcourir dans les deux sens et on peut insérer/supprimer des éléments avant d'autres et non uniquement après.
La structure d'une liste doublement chaînée ressemble à cela :
typedef struct Noeud Noeud;
struct Noeud
{
Noeud *suivant;
Noeud *precedent;
int donnee;
}
typedef Noeud *Liste;La liste doublement chaînée est notamment la base de la file et permet une implémentation efficace de cette structure.
La liste chaînée circulaire (circular linked list) est une liste chaînée ne possédant pas de fin. En effet, le pointeur de fin de liste pointe vers le début de la liste formant ainsi un cycle.
On peut utiliser cette variante de la liste chaînée pour stocker par exemple le tour de chaque joueur dans un jeu, imaginons un jeu de carte qui se joue au tour par tour dans lequel plusieurs joueurs participent, une liste chaînée circulaire permettrait de stocker l'ordre de jeu des joueurs facilement.
Une liste doublement chaînée circulaire (doubly circular linked list) est simplement un regroupement des deux dernières variantes.
circulaire
Exemple de représentation d'une liste doublement chaînée circulaire
En plus de ces variantes assez "courantes", on peut retrouver d'autres variantes plus compliquées mais qui peuvent toujours servir :
La liste chaînée est donc une structure de données très souple, et efficace pour insérer et supprimer des éléments simplement. De plus, on peut la modifier afin de créer de nouvelles structures de données différentes comme la liste doublement chaînée, la liste chaînée circulaire, mais aussi pour créer une pile ou encore une file.
Les listes chaînées sont aussi la base de structures de données plus complexes comme les arbres, les graphes, les tables de hachage et de nombreuses variantes de listes chaînées existent.