Qu'est-ce qu'une structure de données liée?
Une structure de données liée est un ensemble de données organisées dans un format semblable à une liste. Chaque donnée de la liste est appelée nœud, chaque nœud étant connecté au suivant sur la liste. par référence à l’adresse mémoire de ce nœud suivant. Des structures de données liées sont utilisées à la place d’un tableau lorsque le nombre de nœuds d’une liste est inconnu ou risque de croître ou de se réduire au cours du processus. Le type de structure de données lié le plus courant est appelé liste chaînée.
Un nœud d’une structure de données liée contient généralement deux informations: une référence aux données réelles en cours de stockage et une référence au prochain nœud de la liste. Une liste liée est parcourue ou recherchée par un pas à pas. Par le biais de chacun des nœuds de données, en commençant par le premier, ou par l’en-tête de la liste, il n’existe aucun moyen de rechercher des informations dans une liste chaînée sans effectuer un déplacement séquentiel de ces nœuds du début à la fin.
La plupart des structures de données liées utilisent le moins de mémoire possible pendant l'exécution du programme. Si une liste liée est créée avec un seul noeud et qu'aucun autre noeud n'est ajouté, cette liste prendra la place suivante. mémoire requise pour un seul nœud, contrairement à une structure de données de tableau dans laquelle la taille de tout le tableau doit être déclarée et allouée au début du programme et ne peut pas être modifiée .
Les listes chaînées paient pour leur utilisation efficace des ressources de mémoire en nécessitant plus de puissance de calcul. Pour retrouver une donnée spécifique dans une liste chaînée, vous devez parcourir la liste en entier à chaque fois, il peut donc être plus lent d'accéder aux informations. Supprimer ou réorganiser des données dans une liste chaînée peut également nécessiter plus de temps de calcul que la gestion d'un tableau dans lequel des éléments peuvent être facilement échangés.
Une structure de données liée n'est pas obligée d'avoir une seule référence au prochain nœud; Certaines listes chaînées ont deux références de nœud, l’une au nœud suivant de la liste et l’autre au nœud précédent. C’est ce que l’on appelle les listes doublement chaînées. liste dans un sens ou dans l’autre beaucoup plus rapidement, bien qu’au prix d’une utilisation accrue de la mémoire pour la structure de données.
Il est possible que les listes chaînées aient au moins trois références à d'autres nœuds, ce qui crée une structure semblable à un arbre comportant des branches entières de nœuds générés à partir d'un seul. les structures sont appelées listes chaînées multiples. Les listes chaînées multiples sont particulièrement utiles pour les algorithmes de tri complexes utilisés pour structurer les données. Les arbres de recherche sont possibles en grande partie grâce à l'utilisation de structures de données liées. pour créer plusieurs branches de longueur variable.