Structures de données, IMA S6
Listes chaînées
d’après un cours d’A. Miné, ÉNS Ulm.
Laure Gonnord
http://laure.gonnord.org/pro/teaching/
Université Lille 1 - Polytech Lille
Février 2011
Plan
1
Introduction
2 Listes simplement chaînées
Structure
Opérations
3 Divers sur les listes chaînées
Laure Gonnord (Lille1/Polytech)
Structures de données IMA S6 Listes Chaînées
Février 2011 (cid:17) 2 / 36 (cid:16)
Introduction
1
Introduction
2 Listes simplement chaînées
3 Divers sur les listes chaînées
Laure Gonnord (Lille1/Polytech)
Structures de données IMA S6 Listes Chaînées
Février 2011 (cid:17) 3 / 36 (cid:16)
Introduction
Pourquoi ?
Rappel : la liste contiguë.
typedef struct Distribution {
int dernpers;
char listpers[MAXNUMPERS][TAILLENOM];
} Distribution;
Complexité en nombre de cases vues :
Impression
Recherche
Insertion dans le cas d’une liste non pleine
Laure Gonnord (Lille1/Polytech)
Structures de données IMA S6 Listes Chaînées
Février 2011 (cid:17) 4 / 36 (cid:16)
Introduction
Pourquoi ? - 2
Hypothèse supplémentaire : liste contiguë triée
Impression
Recherche
Insertion dans le cas d’une liste non pleine
Laure Gonnord (Lille1/Polytech)
Structures de données IMA S6 Listes Chaînées
Février 2011 (cid:17) 5 / 36 (cid:16)
Introduction
Pourquoi ? - 3
Et si la liste contiguë est pleine ? on réalloue.
(cid:73) La liste chaînée va nous donner un moyen de gérer
l’allocation case par case (de manière non contiguë).
Laure Gonnord (Lille1/Polytech)
Structures de données IMA S6 Listes Chaînées
Février 2011 (cid:17) 6 / 36 (cid:16)
Introduction
Notations algorithmiques
Pointeurs :
p : pointeur de Entier (pointeur)
p ↑ (valeur pointée)
Allocation/Libération de mémoire :
Fonction allouer() renvoie un pointeur vers une nouvelle
cellule allouée
Action liberer(P) récupère la cellule mémoire pointée par
P.
Structures :
Structure pointComplexe
x : Entier
y : Entier
FStruct
pc : pointComplexe (déclaration)
pc.x, pc.y (pour les accès)
Laure Gonnord (Lille1/Polytech)
Structures de données IMA S6 Listes Chaînées
Février 2011 (cid:17) 7 / 36 (cid:16)
Listes simplement chaînées
1
Introduction
2 Listes simplement chaînées
Structure
Opérations
3 Divers sur les listes chaînées
Laure Gonnord (Lille1/Polytech)
Structures de données IMA S6 Listes Chaînées
Février 2011 (cid:17) 8 / 36 (cid:16)
Listes simplement chaînées
Structure
Principe
Liste = séquence ordonnée d’éléments de même type.
Exemple : liste d’entiers (12, 43, 27, 9).
l’ordre des éléments compte : (12, 43, 27, 9) (cid:54)= (12, 27, 43, 9)
la multiplicité des éléments compte
(12, 43, 27, 9) (cid:54)= (12, 43, 27, 9, 9)
Liste simplement chaînée =
représentation où chaque élément pointe sur le suivant.
Laure Gonnord (Lille1/Polytech)
Structures de données IMA S6 Listes Chaînées
Février 2011 (cid:17) 9 / 36 (cid:16)
9432712Listes simplement chaînées
Structure
Représentation des listes - 1
Exemple : cellule de liste d’entiers :
Structure Cellule
valeur : Entier
suivant : pointeur de Cellule
FStruct
valeur est le contenu de la cellule, (ici, un entier)
suivant pointe vers la cellule suivante,
ou vaut NULL (fin de liste).
Le type de cell est récursif (autoréférentiel).
Laure Gonnord (Lille1/Polytech)
Structures de données IMA S6 Listes Chaînées
Février 2011 (cid:17) 10 / 36 (cid:16)
Listes simplement chaînées
Structure
Représentation des listes - 2
Implantation en C d’une liste d’entiers :
structure de cellule pour représenter un élément.
typedef struct
Cell* next;
int
} Cell ;
{
data;
data est le contenu de la cellule, (ici, un entier)
next pointe vers la cellule suivante,
ou vaut NULL (fin de liste).
Laure Gonnord (Lille1/Polytech)
Structures de données IMA S6 Listes Chaînées
Février 2011 (cid:17) 11 / 36 (cid:16)
Listes simplement chaînées
Structure
Représentation des listes - 3
Une liste est représentée par un pointeur de tête Cell*
= pointeur sur la première cellule.
Tous les éléments sont accessibles depuis la tête de liste.
Par convention, head vaut NULL si la liste est vide.
Laure Gonnord (Lille1/Polytech)
Structures de données IMA S6 Listes Chaînées
Advertisement
Février 2011 (cid:17) 12 / 36 (cid:16)
1243279headNULLListes simplement chaînées
Opérations
Opérations sur les listes
Structure de données = type + algorithmes de manipulation.
On va développer des fonctions pour les opérations suivantes :
calcul de la longueur d’une liste,
recherche d’un élément,
insertion d’un élément,
suppression d’un élément,
concaténation de deux listes,
destruction d’une liste.
Toutes nos fonctions prennent une tête de liste en argument.
Laure Gonnord (Lille1/Polytech)
Structures de données IMA S6 Listes Chaînées
Février 2011 (cid:17) 13 / 36 (cid:16)
Listes simplement chaînées
Opérations
Calcul de la longueur d’une liste - 1
Principe : on suit les pointeurs next jusqu’à rencontrer NULL
et on compte le nombre de cellules rencontrées.
Laure Gonnord (Lille1/Polytech)
Structures de données IMA S6 Listes Chaînées
Février 2011 (cid:17) 14 / 36 (cid:16)
1243279headNULLc0iListes simplement chaînées
Opérations
Calcul de la longueur d’une liste - 1
Principe : on suit les pointeurs next jusqu’à rencontrer NULL
et on compte le nombre de cellules rencontrées.
Laure Gonnord (Lille1/Polytech)
Structures de données IMA S6 Listes Chaînées
Février 2011 (cid:17) 14 / 36 (cid:16)
1243279headNULLci1Listes simplement chaînées
Opérations
Calcul de la longueur d’une liste - 1
Principe : on suit les pointeurs next jusqu’à rencontrer NULL
et on compte le nombre de cellules rencontrées.
Laure Gonnord (Lille1/Polytech)
Structures de données IMA S6 Listes Chaînées
Février 2011 (cid:17) 14 / 36 (cid:16)
1243279headNULLci2Listes simplement chaînées
Opérations
Calcul de la longueur d’une liste - 1
Principe : on suit les pointeurs next jusqu’à rencontrer NULL
et on compte le nombre de cellules rencontrées.
Laure Gonnord (Lille1/Polytech)
Structures de données IMA S6 Listes Chaînées
Février 2011 (cid:17) 14 / 36 (cid:16)
1243279headNULLci3Listes simplement chaînées
Opérations
Calcul de la longueur d’une liste - 1
Principe : on suit les pointeurs next jusqu’à rencontrer NULL
et on compte le nombre de cellules rencontrées.
Laure Gonnord (Lille1/Polytech)
Structures de données IMA S6 Listes Chaînées
Février 2011 (cid:17) 14 / 36 (cid:16)
1243279headNULLciNULL4Listes simplement chaînées
Opérations
Calcul de la longueur d’une liste - 2
(cid:73) Écrire la fonction en C (TP)
Laure Gonnord (Lille1/Polytech)
Structures de données IMA S6 Listes Chaînées
Février 2011 (cid:17) 15 / 36 (cid:16)
Listes simplement chaînées
Opérations
Recherche d’un élément
Spécification :
renvoie true si la liste contient un élément
égal à elem, false sinon.
Principe on suit les pointeurs next jusqu’à rencontrer NULL
ou l’élement.
Laure Gonnord (Lille1/Polytech)
Structures de données IMA S6 Listes Chaînées
Février 2011 (cid:17) 16 / 36 (cid:16)
Listes simplement chaînées
Opérations
Rappels sur la mémoire dynamique
Pour plus de flexibilité, les cellules sont allouées
dynamiquement.
#include <stdlib.h>
void* malloc (size_t size);
void free
(void*
ptr);
Effet :
malloc alloue sur le tas un bloc de size octets, renvoie un
pointeur non typé vers la zone allouée. Faire un cast !
free libère le bloc,
le bloc est accessible uniquement par pointeur.
(cid:73) Allouer dynamiquement un tableau de 50 entiers ?
Laure Gonnord (Lille1/Polytech)
Structures de données IMA S6 Listes Chaînées
Février 2011 (cid:17) 17 / 36 (cid:16)
Listes simplement chaînées
Opérations
Création d’une liste (exemple à ne pas suivre)
Pour construire/allouer la liste : (12, 43, 27, 9) :
Cell* head;
head = (Cell*) malloc(sizeof(Cell));
head->data = 12;
head->next = malloc(sizeof(Cell));
head->next->data = 43;
head->next->next = malloc(sizeof(Cell));
head->next->next->data = 27;
head->next->next->next = malloc(sizeof(Cell));
head->next->next->next->data = 9;
head->next->next->next->next = NULL;
(cid:73) Peu pratique. On préfère construire une liste par insertions
successives.
Laure Gonnord (Lille1/Polytech)
Structures de données IMA S6 Listes Chaînées
Février 2011 (cid:17) 18 / 36 (cid:16)
Listes simplement chaînées
Opérations
Insertion en tête de liste - Principe
Cell* head = NULL;
head = insere(head, 9);
head = insere(head, 27);
head = insere(head, 43);
head = insere(head, 12);
Laure Gonnord (Lille1/Polytech)
Structures de données IMA S6 Listes Chaînées
Février 2011 (cid:17) 19 / 36 (cid:16)
headNULLListes simplement chaînées
Opérations
Insertion en tête de liste - Principe
Cell* head = NULL;
head = insere(head, 9);
head = insere(head, 27);
head = insere(head, 43);
head = insere(head, 12);
Laure Gonnord (Lille1/Polytech)
Structures de données IMA S6 Listes Chaînées
Février 2011 (cid:17) 19 / 36 (cid:16)
9NULLhNULLcListes simplement chaînées
Opérations
Insertion en tête de liste - Principe
Cell* head = NULL;
head = insere(head, 9);
head = insere(head, 27);
head = insere(head, 43);
Advertisement
head = insere(head, 12);
Laure Gonnord (Lille1/Polytech)
Structures de données IMA S6 Listes Chaînées
Février 2011 (cid:17) 19 / 36 (cid:16)
9NULLheadListes simplement chaînées
Opérations
Insertion en tête de liste - Principe
Cell* head = NULL;
head = insere(head, 9);
head = insere(head, 27);
head = insere(head, 43);
head = insere(head, 12);
Laure Gonnord (Lille1/Polytech)
Structures de données IMA S6 Listes Chaînées
Février 2011 (cid:17) 19 / 36 (cid:16)
279NULLchListes simplement chaînées
Opérations
Insertion en tête de liste - Principe
Cell* head = NULL;
head = insere(head, 9);
head = insere(head, 27);
head = insere(head, 43);
head = insere(head, 12);
Laure Gonnord (Lille1/Polytech)
Structures de données IMA S6 Listes Chaînées
Février 2011 (cid:17) 19 / 36 (cid:16)
279NULLheadListes simplement chaînées
Opérations
Insertion en tête de liste - Principe
Cell* head = NULL;
head = insere(head, 9);
head = insere(head, 27);
head = insere(head, 43);
head = insere(head, 12);
Laure Gonnord (Lille1/Polytech)
Structures de données IMA S6 Listes Chaînées
Février 2011 (cid:17) 19 / 36 (cid:16)
43279NULLchListes simplement chaînées
Opérations
Insertion en tête de liste - Principe
Cell* head = NULL;
head = insere(head, 9);
head = insere(head, 27);
head = insere(head, 43);
head = insere(head, 12);
Laure Gonnord (Lille1/Polytech)
Structures de données IMA S6 Listes Chaînées
Février 2011 (cid:17) 19 / 36 (cid:16)
43279NULLheadListes simplement chaînées
Opérations
Insertion en tête de liste - Principe
Cell* head = NULL;
head = insere(head, 9);
head = insere(head, 27);
head = insere(head, 43);
head = insere(head, 12);
Laure Gonnord (Lille1/Polytech)
Structures de données IMA S6 Listes Chaînées
Février 2011 (cid:17) 19 / 36 (cid:16)
ch1243279NULLListes simplement chaînées
Opérations
Insertion en tête de liste - Principe
Cell* head = NULL;
head = insere(head, 9);
head = insere(head, 27);
head = insere(head, 43);
head = insere(head, 12);
Laure Gonnord (Lille1/Polytech)
Structures de données IMA S6 Listes Chaînées
Février 2011 (cid:17) 19 / 36 (cid:16)
head1243279NULLListes simplement chaînées
Opérations
Insertion en tête de liste - Principe
Cell* head = NULL;
head = insere(head, 9);
head = insere(head, 27);
head = insere(head, 43);
head = insere(head, 12);
Remarques :
la liste est dans l’ordre inverse de celui des
insertions,
insere fonctionne sur une liste vide ou non-vide,
la tête de liste est modifiée à chaque insertion,
le coût d’une insertion est constant.
Laure Gonnord (Lille1/Polytech)
Structures de données IMA S6 Listes Chaînées
Février 2011 (cid:17) 19 / 36 (cid:16)
head1243279NULLListes simplement chaînées
Opérations
Insertion en tête de liste - Implantation
Laure Gonnord (Lille1/Polytech)
Structures de données IMA S6 Listes Chaînées
Février 2011 (cid:17) 20 / 36 (cid:16)
Listes simplement chaînées
Opérations
Insertion en queue de liste
Deux cas à considérer :
liste vide : on fait pointer la tête de liste sur la nouvelle
cellule,
liste non vide : on fait pointer le champ next de la dernière
cellule sur la nouvelle cellule.
Laure Gonnord (Lille1/Polytech)
Structures de données IMA S6 Listes Chaînées
Février 2011 (cid:17) 21 / 36 (cid:16)
liste vide liste non videNULLheadNULLheadListes simplement chaînées
Opérations
Insertion en queue de liste
Deux cas à considérer :
liste vide : on fait pointer la tête de liste sur la nouvelle
cellule,
liste non vide : on fait pointer le champ next de la dernière
cellule sur la nouvelle cellule.
Laure Gonnord (Lille1/Polytech)
Structures de données IMA S6 Listes Chaînées
Février 2011 (cid:17) 21 / 36 (cid:16)
liste vide liste non videNULLNULLheadNULLheadListes simplement chaînées
Opérations
Exemple d’insertion en queue de liste
Cell* head = NULL;
head = insere(head, 12);
head = insere(head, 43);
head = insere(head, 27);
head = insere(head, 9);
Laure Gonnord (Lille1/Polytech)
Structures de données IMA S6 Listes Chaînées
Février 2011 (cid:17) 22 / 36 (cid:16)
12headcNULLNULLListes simplement chaînées
Opérations
Exemple d’insertion en queue de liste
Cell* head = NULL;
head = insere(head, 12);
head = insere(head, 43);
head = insere(head, 27);
head = insere(head, 9);
Laure Gonnord (Lille1/Polytech)
Structures de données IMA S6 Listes Chaînées
Février 2011 (cid:17) 22 / 36 (cid:16)
12head43NULLlcListes simplement chaînées
Opérations
Exemple d’insertion en queue de liste
Cell* head = NULL;
Advertisement
head = insere(head, 12);
head = insere(head, 43);
head = insere(head, 27);
head = insere(head, 9);
Laure Gonnord (Lille1/Polytech)
Structures de données IMA S6 Listes Chaînées
Février 2011 (cid:17) 22 / 36 (cid:16)
12head2743NULLlcListes simplement chaînées
Opérations
Exemple d’insertion en queue de liste
Cell* head = NULL;
head = insere(head, 12);
head = insere(head, 43);
head = insere(head, 27);
head = insere(head, 9);
Laure Gonnord (Lille1/Polytech)
Structures de données IMA S6 Listes Chaînées
Février 2011 (cid:17) 22 / 36 (cid:16)
129NULLheadc2743lListes simplement chaînées
Opérations
Exemple d’insertion en queue de liste
Cell* head = NULL;
head = insere(head, 12);
head = insere(head, 43);
head = insere(head, 27);
head = insere(head, 9);
Remarques :
la liste est dans le même ordre que celui des
insertions,
la tête de liste n’est modifiée que lors de la première
insertion,
le coût d’une insertion est linéaire,
O(n)
Laure Gonnord (Lille1/Polytech)
Structures de données IMA S6 Listes Chaînées
Février 2011 (cid:17) 22 / 36 (cid:16)
129NULLheadc2743lListes simplement chaînées
Opérations
Insertion en queue de liste
Laure Gonnord (Lille1/Polytech)
Structures de données IMA S6 Listes Chaînées
Février 2011 (cid:17) 23 / 36 (cid:16)
Listes simplement chaînées
Opérations
Coût de construction d’une liste
Pour construire une liste à n éléments :
Par ajout en tête de liste : O(n) mais ordre inverse !
par ajout en queue de liste : O(n2)
Laure Gonnord (Lille1/Polytech)
Structures de données IMA S6 Listes Chaînées
Février 2011 (cid:17) 24 / 36 (cid:16)
Listes simplement chaînées
Opérations
Insertion après un élément - 1
Spécification :
Insère un élément dans une liste , à l’aide d’un pointeur
vers la cellule précédente.
Laure Gonnord (Lille1/Polytech)
Structures de données IMA S6 Listes Chaînées
Février 2011 (cid:17) 25 / 36 (cid:16)
predListes simplement chaînées
Opérations
Insertion après un élément - 1
Spécification :
Insère un élément dans une liste , à l’aide d’un pointeur
vers la cellule précédente.
Laure Gonnord (Lille1/Polytech)
Structures de données IMA S6 Listes Chaînées
Février 2011 (cid:17) 25 / 36 (cid:16)
elemcpredListes simplement chaînées
Opérations
Insertion après un élément - 1
Spécification :
Insère un élément dans une liste , à l’aide d’un pointeur
vers la cellule précédente.
Laure Gonnord (Lille1/Polytech)
Structures de données IMA S6 Listes Chaînées
Février 2011 (cid:17) 25 / 36 (cid:16)
elemcpredListes simplement chaînées
Opérations
Insertion après un élément - 1
Spécification :
Insère un élément dans une liste , à l’aide d’un pointeur
vers la cellule précédente.
Laure Gonnord (Lille1/Polytech)
Structures de données IMA S6 Listes Chaînées
Février 2011 (cid:17) 25 / 36 (cid:16)
elemcpredListes simplement chaînées
Opérations
Insertion après un élément - 1
Spécification :
Insère un élément dans une liste , à l’aide d’un pointeur
vers la cellule précédente.
Notes :
coût constant, hors calcul de pred,
pred peut être obtenu par une variante de recherche
(par exemple si on cherche à insérer dans une liste
triée) cf TP,
on suppose qu’on n’insère pas en première position.
(⇒ on suppose que la liste n’est pas vide)
Laure Gonnord (Lille1/Polytech)
Structures de données IMA S6 Listes Chaînées
Février 2011 (cid:17) 25 / 36 (cid:16)
Listes simplement chaînées
Opérations
Insertion après un élément - 2
(cid:73) L’insertion avant une cellule donnée est plus complexe...
Laure Gonnord (Lille1/Polytech)
Structures de données IMA S6 Listes Chaînées
Février 2011 (cid:17) 26 / 36 (cid:16)
Listes simplement chaînées
Opérations
Suppression d’un élément - 1
Spécification :
Supprime une cellule de la liste , à l’aide d’un pointeur
vers la cellule précédente.
Laure Gonnord (Lille1/Polytech)
Structures de données IMA S6 Listes Chaînées
Février 2011 (cid:17) 27 / 36 (cid:16)
predcListes simplement chaînées
Opérations
Suppression d’un élément - 1
Spécification :
Supprime une cellule de la liste , à l’aide d’un pointeur
vers la cellule précédente.
Laure Gonnord (Lille1/Polytech)
Structures de données IMA S6 Listes Chaînées
Février 2011 (cid:17) 27 / 36 (cid:16)
predcListes simplement chaînées
Opérations
Suppression d’un élément - 1
Spécification :
Supprime une cellule de la liste , à l’aide d’un pointeur
vers la cellule précédente.
Laure Gonnord (Lille1/Polytech)
Structures de données IMA S6 Listes Chaînées
Février 2011 (cid:17) 27 / 36 (cid:16)
predListes simplement chaînées
Opérations
Suppression d’un élément - 1
Spécification :
Advertisement
Supprime une cellule de la liste , à l’aide d’un pointeur
vers la cellule précédente.
Notes :
coût constant, hors calcul de pred,
on suppose qu’on ne détruit pas en première position,
(⇒ on suppose que la liste n’est pas vide)
on suppose que pred a un suivant,
(pred->next(cid:54)=NULL)
(on peut par contre avoir c->next=NULL).
Laure Gonnord (Lille1/Polytech)
Structures de données IMA S6 Listes Chaînées
Février 2011 (cid:17) 27 / 36 (cid:16)
Listes simplement chaînées
Opérations
Suppression d’un élément - 2
(cid:73) Il reste à faire la version suppression complète .
Laure Gonnord (Lille1/Polytech)
Structures de données IMA S6 Listes Chaînées
Février 2011 (cid:17) 28 / 36 (cid:16)
Listes simplement chaînées
Opérations
Suppression d’un élément - 3
Spécification :
supprime le premier élément égal à elem dans la liste si il existe.
calcule automatiquement pred,
gère les cas limites :
liste vide, liste à un seul élément,
elem en tête ou en fin de liste,
elem non présent dans la liste,
la tête de liste peut changer,
coût linéaire au pire, à cause de la recherche de pred.
Laure Gonnord (Lille1/Polytech)
Structures de données IMA S6 Listes Chaînées
Février 2011 (cid:17) 29 / 36 (cid:16)
Listes simplement chaînées
Opérations
Suppression d’un élément - 4
Laure Gonnord (Lille1/Polytech)
Structures de données IMA S6 Listes Chaînées
Février 2011 (cid:17) 30 / 36 (cid:16)
Listes simplement chaînées
Opérations
Concaténation de listes
(cid:73) Cf TD.
Laure Gonnord (Lille1/Polytech)
Structures de données IMA S6 Listes Chaînées
Février 2011 (cid:17) 31 / 36 (cid:16)
12124327head1NULLhead227NULLcListes simplement chaînées
Opérations
Concaténation de listes
(cid:73) Cf TD.
Laure Gonnord (Lille1/Polytech)
Structures de données IMA S6 Listes Chaînées
Février 2011 (cid:17) 31 / 36 (cid:16)
12124327head1head227NULLcListes simplement chaînées
Opérations
Destruction totale d’une liste
Directement en C :
void detruit(Cell* head)
{
Cell *c;
while (head) {
c = head->next;
free(head);
head = c;
}
}
Coût ?
Laure Gonnord (Lille1/Polytech)
Structures de données IMA S6 Listes Chaînées
Février 2011 (cid:17) 32 / 36 (cid:16)
Divers sur les listes chaînées
1
Introduction
2 Listes simplement chaînées
3 Divers sur les listes chaînées
Laure Gonnord (Lille1/Polytech)
Structures de données IMA S6 Listes Chaînées
Février 2011 (cid:17) 33 / 36 (cid:16)
Divers sur les listes chaînées
Erreurs courantes sur les listes
Erreurs courantes sur les pointeurs et la mémoire
dynamique :
déréférencer un pointeur NULL,
utiliser un bloc après l’avoir libéré,
libérer deux fois le même bloc,
oublier de libérer un bloc (fuites de mémoire).
Introduction de cycles :
(génère des boucles infinies lors des parcours,
cause des fuites de mémoire, . . . )
Laure Gonnord (Lille1/Polytech)
Structures de données IMA S6 Listes Chaînées
Février 2011 (cid:17) 34 / 36 (cid:16)
Divers sur les listes chaînées
Erreurs courantes sur les listes
Partage de cellules entre plusieurs listes :
(effets de bord lors de la modification d’une liste,
cause des libérations multiples de blocs, . . . )
Oubli des cas limites :
liste vide, listes à un élément,
insertion/suppression en première/dernière position,
etc.
Laure Gonnord (Lille1/Polytech)
Structures de données IMA S6 Listes Chaînées
Février 2011 (cid:17) 35 / 36 (cid:16)
Divers sur les listes chaînées
Comparaison entres listes et tableaux
Coût comparé des listes simplement chaînées et des tableaux.
recherche d’une valeur
accès par indice
insertion en tête
insertion en queue
insertion au milieu
recherche si trié
insertion (indice p) si trié
liste chaînée
O(n)
O(n)
O(1)
O(n)
O(1) / O(n)
O(n) (pas dicho)
O(n)
liste contiguë
O(n)
O(1)
O(n)
O(n)
O(n)
O(ln n)
O(n) (décalages)
Les listes sont particulièrement efficaces pour :
l’insertion et la suppression en tête de liste,
l’insertion et la suppression en milieu de liste,
si la cellule précédente est connue.
Laure Gonnord (Lille1/Polytech)
Structures de données IMA S6 Listes Chaînées
Février 2011 (cid:17) 36 / 36 (cid:16)