Français
Menu

Qu'est-ce que Liste chaînée (linked list) ?

Structure de données dans laquelle chaque élément contient une valeur et un pointeur vers l'élément suivant, les éléments étant reliés en suivant les pointeurs. Une fois la position connue, l'insertion et la suppression sont des modifications de pointeurs en O(1), mais lire le i-ème élément oblige à parcourir la liste depuis le début, en O(n). Les éléments ont tendance à être dispersés en mémoire, si bien que les caches fonctionnent moins bien qu'avec les tableaux.

Nom japonais: 連結リスト

« Liste chaînée (linked list) » apparaît dans 10 questions d'entraînement réparties sur 5 thèmes, dont Structures de données et algorithmes, Hiérarchie mémoire, Bases de la programmation (trace de pseudo-code).

Domaine: Structures de données et algorithmes

S'entraîner : questions sur Liste chaînée (linked list)

Par rapport à un tableau, quelle description d'une liste chaînée (liste dont chaque élément contient un pointeur vers l'élément suivant) est correcte ?

  1. ASi l'élément situé juste avant le point d'insertion est connu, on peut insérer un nouvel élément en modifiant seulement des pointeurs, sans déplacer les autres éléments ; en revanche, lire le i-ème élément oblige à parcourir la liste depuis le début
  2. BLa position du i-ème élément se calcule, si bien que n'importe quel élément se lit en temps constant, O(1)
  3. CLes éléments sont rangés de façon contiguë en mémoire, si bien que le cache et le préchargement fonctionnent bien lors d'une lecture dans l'ordre
Afficher la réponse et l'explication

Réponse : A. Si l'élément situé juste avant le point d'insertion est connu, on peut insérer un nouvel élément en modifiant seulement des pointeurs, sans déplacer les autres éléments ; en revanche, lire le i-ème élément oblige à parcourir la liste depuis le début

Dans une liste chaînée, une fois la position connue, l'insertion et la suppression ne demandent que la réécriture des pointeurs voisins, en O(1). Lire le i-ème élément oblige en revanche à suivre i pointeurs depuis le début, en O(n). Un tableau calcule l'adresse du i-ème élément à partir de son adresse de départ et de la taille d'un élément, et lit donc n'importe quel élément en O(1), mais une insertion au milieu coûte O(n) pour décaler les éléments suivants. De plus, les éléments d'un tableau étant contigus, le cache et le préchargement fonctionnent bien, alors que les nœuds d'une liste chaînée ont tendance à être dispersés en mémoire, si bien que même un parcours en O(n) peut être beaucoup plus lent.

Quelle comparaison du chaînage (relier par une liste chaînée les éléments d'une même position) et de l'adressage ouvert (chercher une autre position libre dans la table), comme méthodes de résolution des collisions d'une table de hachage, est correcte ? Le facteur de charge est le nombre d'éléments stockés divisé par la taille de la table.

  1. ALe chaînage peut stocker des éléments même quand le facteur de charge dépasse 1, alors que l'adressage ouvert ne peut pas stocker plus d'éléments que la taille de la table, et son nombre de sondages augmente fortement quand le facteur de charge approche de 1
  2. BL'adressage ouvert n'a pas de collisions, si bien qu'une recherche demande toujours un seul sondage, quel que soit le facteur de charge
  3. CAvec le chaînage, le coût d'une recherche reste le même, aussi élevé que soit le facteur de charge
Afficher la réponse et l'explication

Réponse : A. Le chaînage peut stocker des éléments même quand le facteur de charge dépasse 1, alors que l'adressage ouvert ne peut pas stocker plus d'éléments que la taille de la table, et son nombre de sondages augmente fortement quand le facteur de charge approche de 1

Le chaînage relie en listes les éléments d'une même position : il peut donc stocker plus d'éléments que la taille de la table, mais la longueur moyenne des listes croît proportionnellement au facteur de charge, et le coût de recherche aussi. L'adressage ouvert range tout à l'intérieur de la table : il peut contenir au plus autant d'éléments que la taille de la table, et le nombre de sondages nécessaires pour trouver un emplacement libre augmente fortement quand le facteur de charge approche de 1. Quelle que soit la méthode, on agrandit généralement la table et on réinsère tous les éléments (rehachage) dès que le facteur de charge dépasse une limite choisie, par exemple de 0,5 à 0,75 environ. Les collisions se produisent aussi en adressage ouvert ; celui-ci les traite en cherchant une position libre.

« Liste chaînée (linked list) » dans les explications

Questions mentionnant « Liste chaînée (linked list) » (10)

  1. Pourquoi le parcours de la liste chaînée ci-dessus est-il généralement bien plus lent que la lecture séquentielle d’un tableau comportant le même nombre d’éléments ?
  2. Par rapport à un tableau, quelle description d'une liste chaînée (liste dont chaque élément contient un pointeur vers l'élément suivant) est correcte ?
  3. Quelle comparaison du chaînage (relier par une liste chaînée les éléments d'une même position) et de l'adressage ouvert (chercher une autre position libre dans la table), comme méthodes de résolution des collisions d'une table de hachage, est correcte ? Le facteur de charge est le nombre d'éléments stockés divisé par la taille de la table.
  4. Pour une table de hachage contenant de nombreux éléments et maintenue à un facteur de charge d'environ 0,5, quelle est la raison la plus appropriée pour laquelle l'adressage ouvert avec sondage linéaire tend à être plus rapide que le chaînage (relier les éléments par des listes chaînées) ?
  5. Le programme suivant affiche une liste chaînée, dont les éléments sont reliés par le tableau next, en la parcourant à partir de l'élément d'indice 1. Les indices du tableau commencent à 1. Une valeur 0 dans next marque la fin de la liste. Quelle suite de valeurs est affichée ?
  6. Le programme suivant insère « F », placé en val[6], juste après « C » (indice 3) dans la liste chaînée A → C → E → D → B, reliée par le tableau next, puis affiche la liste à partir de l'élément d'indice 1. Les indices du tableau commencent à 1. Une valeur 0 dans next marque la fin de la liste. Que faut-il écrire à la place de 【a】 pour que l'affichage soit A, C, F, E, D, B ?
  7. Pour quel type d’accès le préchargement matériel est-il particulièrement efficace ?
  8. Quelle description du problème ABA, qui affecte les structures de données sans verrou utilisant CAS, est correcte ?
  9. Quel traitement tend à être peu efficace lorsqu'il est exécuté sur GPU ?
  10. On insère dans cet ordre les valeurs 1, 2, 3, …, 1000 dans un arbre binaire de recherche vide (sans aucun rééquilibrage). Lors de la recherche de 1000 dans cet arbre, combien de nœuds sont comparés, à partir de la racine, avant de le trouver ?

Termes associés

Tableau Préchargement (prefetch) Pointeur Table de hachage (hash table) Ligne de cache Complexité temporelle (notation grand O) Problème ABA Sans verrou (lock-free) LR/SC GPU

Retour au glossaire