Listes chaînées : implémentation et opérations en Terminale
Listes chaînées : implémentation et opérations, c'est une notion de nsi du chapitre « Structures de données (listes, piles, files, arbres, graphes) », au programme de Terminale. Voici le cours, un exemple et de quoi t'entraîner.
Listes chaînées : implémentation et opérations : le cours
Une liste chaînée est une structure où chaque élément (nœud) contient une donnée et un lien vers l'élément suivant. Contrairement aux listes classiques, les éléments ne sont pas stockés de façon contiguë en mémoire.
Exemple
Une chaîne de wagons de train : chaque wagon connaît le wagon suivant, mais ils ne sont pas attachés au même endroit. Pour accéder au dernier wagon, tu dois passer par tous les précédents.
À retenir
Accès en O(n) car il faut traverser depuis le début, mais insertion/suppression en O(1) si on connaît la position.
S'entraîner sur listes chaînées : implémentation et opérations
Fais l'exercice, puis demande au tuteur de te corriger pas à pas.
Exercice 1
On considère un ABR contenant les valeurs 50, 30, 70, 20, 40, 60, 80. Dessinez l'arbre puis donnez le parcours infixe. Quel est l'intérêt du parcours infixe sur un ABR ?
Corrige cet exercice avec le tuteur →Exercice 2
Représentez le graphe suivant par (1) une matrice d'adjacence, (2) une liste d'adjacence. Sommets : A, B, C, D Arêtes : A-B, A-C, B-C, B-D, C-D Le graphe est-il orienté ou non orienté ? Quel mode de représentation est le plus efficace ici ?
Corrige cet exercice avec le tuteur →Cette notion fait partie du chapitre Structures de données (listes, piles, files, arbres, graphes) (NSI Terminale).