structure de données liées

Une liste chaînée est une collection de structures ordonnées non pas selon leur emplacement physique en mémoire, mais selon des liens logiques stockés dans les données de la structure elle-même. Il n'est pas nécessaire que les éléments soient stockés dans des emplacements mémoire adjacents. Chaque structure possède un champ de données et un champ d'adresse. Le champ d'adresse contient l'adresse de son successeur .

Une liste chaînée peut être simplement, doublement ou multiplement chaînée et peut être linéaire ou circulaire.

Propriétés de base

• Les objets, appelés nœuds , sont liés selon une séquence linéaire.
• Une référence au premier nœud de la liste est toujours conservée. On l'appelle la « tête » ou le « début ».

Une liste chaînée à trois nœuds contient deux champs chacun : une valeur entière et un lien vers le nœud suivant.

Un arbre de recherche est une structure de données arborescente dans laquelle les nœuds peuvent être stockés à partir d'un ensemble ordonné , tel que lors d'un parcours infixe de l'arbre, les nœuds sont visités dans l'ordre croissant des valeurs stockées.

Propriétés de base

• Les objets, appelés nœuds, sont stockés dans un ensemble ordonné.
• Le parcours infixe permet une lecture ascendante des données dans l'arbre.

Comparativement aux tableaux, les structures de données chaînées offrent une plus grande flexibilité dans l'organisation des données et l'allocation d'espace. Avec les tableaux, la taille doit être spécifiée précisément dès le départ, ce qui peut entraîner un gaspillage de mémoire ou une limitation arbitraire susceptible d'entraver le fonctionnement du système. Une structure de données chaînée est construite dynamiquement et sa taille n'excède jamais les besoins du programme. De plus, il n'est pas nécessaire de deviner l'espace à allouer lors de sa création. Cette caractéristique est essentielle pour éviter le gaspillage de mémoire.

Dans un tableau, les éléments doivent être processus ou un thread peut ajouter ou supprimer des nœuds dans une partie de la structure de données, même si d'autres processus ou threads travaillent sur d'autres parties.

En revanche, l'accès à un nœud particulier d'une structure de données chaînée nécessite de suivre une chaîne de références stockées dans chaque nœud. Si la structure comporte n nœuds, et que chaque nœud contient au plus b liens, certains nœuds seront inaccessibles en moins de log _b n étapes, ce qui ralentit considérablement leur accès. Ce ralentissement peut parfois être important, notamment pour les structures contenant un grand nombre de nœuds. Dans de nombreuses structures, l'accès à certains nœuds peut nécessiter jusqu'à n − 1 étapes dans le pire des cas . À l'inverse, de nombreuses structures de données de type tableau permettent d'accéder à n'importe quel élément en un nombre constant d'opérations, indépendamment du nombre d'éléments du tableau.

De manière générale, la mise en œuvre de ces structures de données liées repose sur des structures de données dynamiques . Cela permet de réutiliser l'espace mémoire. L'utilisation de la mémoire est ainsi optimisée. La mémoire est allouée en fonction des besoins et libérée lorsqu'elle n'est plus nécessaire.

Les structures de données chaînées peuvent engendrer une surcharge mémoire importante (si les nœuds sont alloués individuellement) et perturber les algorithmes de pagination et de mise en cache du processeur (en raison de leur faible localité de référence ). Dans certains cas, elles peuvent également consommer plus de mémoire (pour les champs de liaison) que les tableaux. Ceci s'explique par le fait que les données chaînées ne sont pas contiguës : contrairement aux tableaux, elles peuvent être réparties dans toute la mémoire.

Dans les tableaux, le n-ième élément est accessible immédiatement, tandis que dans une structure de données chaînée, il faut suivre plusieurs pointeurs, de sorte que le temps d'accès à l'élément varie en fonction de sa position dans la structure.

Dans certains modèles théoriques de calcul qui imposent les contraintes des structures liées, comme la machine à pointeurs , de nombreux problèmes nécessitent plus d'étapes que dans le modèle de machine à accès aléatoire non contrainte .