Différence entre les tableaux et les listes liées

Arrays vs listes liées

Les tableaux sont la structure de données la plus couramment utilisée pour stocker la collecte d'éléments. La plupart des langages de programmation fournissent des méthodes pour déclarer facilement les tableaux et les éléments d'accès dans les tableaux. La liste liée, plus précisément liée à la liaison individuelle, est également une structure de données qui peut être utilisée pour stocker la collecte d'éléments. Il est composé d'une séquence de nœuds et chaque nœud a une référence au nœud suivant dans la séquence.

Illustré à la figure 1, est un morceau de code généralement utilisé pour déclarer et attribuer des valeurs à un tableau. La figure 2 illustre à quoi ressemblerait un tableau dans la mémoire.

Le code ci-dessus définit un tableau qui peut stocker 5 entiers et ils sont accessibles en utilisant des indices 0 à 4. Une propriété importante d'un tableau est que l'ensemble du tableau est alloué comme un seul bloc de mémoire et chaque élément obtient son propre espace dans le tableau. Une fois qu'un tableau est défini, sa taille est fixe. Donc, si vous n'êtes pas sûr de la taille du tableau au moment de la compilation, vous devrez définir un tableau suffisamment grand pour être en toute sécurité. Mais, la plupart du temps, nous allons réellement utiliser moins de nombre d'éléments que nous avons alloués. Donc une quantité considérable de mémoire est en fait gaspillée. D'un autre côté, si le «tableau suffisamment grand» n'est pas réellement assez grand, le programme se bloquerait.

Une liste liée alloue la mémoire à ses éléments séparément dans son propre bloc de mémoire et la structure globale est obtenue en liant ces éléments comme des liens dans une chaîne. Chaque élément d'une liste liée a deux champs comme le montre la figure 3. Le champ de données contient les données réelles stockées et le champ suivant contient la référence à l'élément suivant de la chaîne. Le premier élément de la liste liée est stocké comme le chef de la liste liée.

Figure 3: élément d'une liste liée

La figure 4 illustre une liste liée à trois éléments. Chaque élément stocke ses données et tous les éléments à l'exception du dernier stockage une référence à l'élément suivant. Last Element détient une valeur nulle dans son prochain champ. Tout élément de la liste peut être accessible en commençant à la tête et en suivant le pointeur suivant jusqu'à ce que vous rencontriez l'élément requis.

Même si les tableaux et les listes liées sont similaires dans le sens où les deux sont utilisés pour stocker la collecte d'éléments, ils engagent des différences en raison des stratégies qu'ils utilisent pour allouer de la mémoire à ses éléments. Les tableaux allouent de la mémoire à tous ses éléments en tant que bloc unique et la taille du tableau doit être déterminée au moment de l'exécution. Cela rendrait les tableaux inefficaces dans des situations où vous ne connaissez pas la taille du tableau au moment de la compilation. Étant donné qu'une liste liée alloue la mémoire à ses éléments séparément, il serait beaucoup efficace dans les situations dans lesquelles vous ne connaissez pas la taille de la liste au moment de la compilation. La déclaration et l'accès aux éléments dans une liste liée ne seraient pas simples par rapport à la façon dont vous accédez directement aux éléments dans un tableau utilisant ses indices.