Différence entre les tableaux et les listes chaînées

Tableaux vs Listes liées

Les tableaux sont la structure de données la plus couramment utilisée pour stocker une collection d'éléments. La plupart des langages de programmation fournissent des méthodes pour déclarer facilement des tableaux et accéder à des éléments dans les tableaux. La liste chaînée, plus précisément une liste chaînée, est également une structure de données pouvant être utilisée pour stocker une collection d'éléments. Il est composé d’une séquence de nœuds et chaque nœud est référencé au nœud suivant de la séquence..

La figure 1 montre un élément de code généralement utilisé pour déclarer et affecter des valeurs à un tableau. La figure 2 montre à quoi ressemble un tableau dans la mémoire.

Le code ci-dessus définit un tableau pouvant stocker 5 nombres entiers. Les index 0 à 4 permettent d'y accéder. Une propriété importante d'un tableau est que tout le tableau est alloué en tant que bloc de mémoire et que chaque élément dispose de son propre espace. 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 assez grand pour être sûr. Mais, la plupart du temps, nous allons utiliser moins d’éléments que ce qui a été alloué. Donc, une quantité considérable de mémoire est réellement gaspillée. D'autre part, si le «tableau assez grand» n'est pas assez grand, le programme planterait.

Une liste chaînée alloue de 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 sous forme de liens dans une chaîne. Comme le montre la figure 3, chaque élément d'une liste chaînée comporte deux champs. 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é en tant qu'en tête de la liste liée..

Figure 3: élément d'une liste chaînée

La figure 4 décrit une liste chaînée avec trois éléments. Chaque élément stocke ses données et tous les éléments sauf le dernier stockent une référence à l'élément suivant. Le dernier élément contient une valeur nulle dans son champ suivant. Vous pouvez accéder à n'importe quel élément de la liste en commençant par l'en-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 chaînées sont similaires en ce sens qu'ils sont tous deux utilisés pour stocker une collection d'éléments, ils présentent des différences en raison des stratégies qu'ils utilisent pour allouer de la mémoire à ses éléments. Les tableaux allouent la mémoire à tous leurs éléments en un seul bloc 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. Dans la mesure où une liste chaînée alloue de la mémoire à ses éléments séparément, elle serait très efficace dans les cas où vous ne connaissez pas la taille de la liste au moment de la compilation. La déclaration et l'accès aux éléments d'une liste chaînée ne seraient pas simples comparés à la manière dont vous accédez directement aux éléments d'un tableau à l'aide de ses index.