Cours implémentation des structures de données, tutoriel & guide de travaux pratiques en pdf.

Implémentation des types collection ordonnée

Rappel: il s’agit de la pile, queue et séquence
Implémentation avec:
•tableaux
•listes chaînées
Discussion:
•avec tableaux, facile à implémenter mais – taille fixée à la compilation – insertion/suppression au milieu de la structure coûteuse (séquence), aux deux extrémités astucieuses (queue, séquence)
•avec listes chaînées: – taille variable – insertion/suppression au milieu de la structure OK – insertion/suppression aux deux extrémités OK (à condition d’avoir une référence directe au début ET à la fin de liste) – mais accès au i-ème élément demande le parcours séquentiel de la liste depuis le début

Remarque:
Nous ne verrons pas l’implémentation avec les tableaux
Liste chaînée
Une liste chaînée est composée d’un ensemble de noeuds qui contiennent chacun un élément et le lien vers le noeud suivant..