Tableaux vs listes chaîné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 aux éléments des tableaux. La liste chaînée, plus précisément la liste chaînée simple, est également une structure de données qui peut être utilisée pour stocker une collection 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.
Montré à la figure 1, est un morceau de code généralement utilisé pour déclarer et affecter des valeurs à un tableau. La figure 2 montre à quoi ressemblerait un tableau dans la mémoire.
Le code ci-dessus définit un tableau qui peut stocker 5 entiers et on y accède en utilisant les indices 0 à 4. Une propriété importante d'un tableau est que le tableau entier 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 du bon côté. Mais, la plupart du temps, nous allons en fait utiliser moins d'éléments que nous n'en avons alloués. Ainsi, 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 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 reliant ces éléments comme des liens dans une chaîne. Chaque élément d'une liste chaînée comporte deux champs, comme illustré à 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 chaînée est stocké en tant que tête de la liste chaînée.
| données | suivant |
Figure 3: Élément d'une liste chaînée
La figure 4 représente 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. Tout élément de la liste est accessible 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 dans le sens où les deux sont 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 de la mémoire à tous ses é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 les situations où vous ne connaissez pas la taille du tableau au moment de la compilation. Puisqu'une liste chaînée alloue de la mémoire à ses éléments séparément, elle serait très efficace dans les situations 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 par rapport à la façon dont vous accédez directement aux éléments d'un tableau à l'aide de ses indices.
