Recommandé, 2024

Choix De L'Éditeur

Différence entre tableau et liste chaînée

La principale différence entre Array et Linked list concerne leur structure. Les tableaux sont des structures de données basées sur un index où chaque élément est associé à un index. D'autre part, la liste liée s'appuie sur des références où chaque nœud est constitué des données et des références aux éléments précédent et suivant.

Fondamentalement, un tableau est un ensemble d'objets de données similaires stockés dans des emplacements de mémoire séquentiels sous un en-tête commun ou un nom de variable.

Tandis qu'une liste chaînée est une structure de données qui contient une séquence d'éléments où chaque élément est lié à son élément suivant. Il y a deux champs dans un élément de la liste liée. L'un est le champ de données et l'autre est le champ de liaison. Le champ de données contient la valeur réelle à stocker et à traiter. De plus, le champ lien contient l'adresse de la prochaine donnée dans la liste liée. L'adresse utilisée pour accéder à un nœud particulier est appelée un pointeur.

Une autre différence significative entre un tableau et une liste liée est que le tableau a une taille fixe et doit être déclaré avant, mais la liste chaînée n'est pas limitée à la taille, ni au développement ni au contrat lors de l'exécution.

Tableau de comparaison

Base de comparaisonTableauListe chaînée
De baseC'est un ensemble cohérent d'un nombre fixe d'éléments de données.C'est un ensemble ordonné comprenant un nombre variable d'éléments de données.
TailleSpécifié lors de la déclaration.Pas besoin de spécifier; grandir et rétrécir pendant l'exécution.
Allocation de stockageL'emplacement de l'élément est alloué pendant la compilation.La position de l'élément est attribuée pendant le temps d'exécution.
Ordre des élémentsStockés consécutivementStocké au hasard
Accéder à l'élémentAccès direct ou aléatoire, c.-à-d., Spécifiez l'index ou l'indice de tableau.Accès séquentiel, c'est-à-dire cheminement à partir du premier nœud de la liste par le pointeur.
Insertion et suppression d'élémentLent relativement car le changement est nécessaire.Plus facile, rapide et efficace.
RechercheRecherche binaire et recherche linéairerecherche linéaire
Mémoire requiseMoinsPlus
Utilisation de la mémoireInefficaceEfficace

Définition de tableau

Un tableau est défini comme un ensemble d'un nombre défini d'éléments homogènes ou d'éléments de données. Cela signifie qu'un tableau peut contenir un seul type de données, soit tous les entiers, tous les nombres à virgule flottante ou tous les caractères. La déclaration d'un tableau est la suivante:
int a [10];
Où int spécifie le type de données ou le type d'éléments stockés dans le tableau. “A” est le nom d'un tableau, et le nombre spécifié entre crochets est le nombre d'éléments qu'un tableau peut stocker, cela s'appelle également la taille ou la longueur du tableau.

Voyons quelques-uns des concepts à retenir sur les tableaux:

  • Vous pouvez accéder aux différents éléments d’un tableau en décrivant le nom du tableau, suivi d’un index ou d’un indice (déterminant l’emplacement de l’élément dans le tableau) entre crochets. Par exemple, pour récupérer le 5ème élément du tableau, nous devons écrire une instruction a [4].
  • Dans tous les cas, les éléments d'un tableau seront stockés dans un emplacement de mémoire consécutif.
  • Le tout premier élément du tableau a l'indice zéro [0]. Cela signifie que le premier et le dernier élément seront spécifiés sous la forme d'un [0] et d'un [9] respectivement.
  • Le nombre d'éléments pouvant être stockés dans un tableau, c'est-à-dire la taille ou la longueur d'un tableau, est donné par l'équation suivante:
    (borne supérieure-borne inférieure) + 1
    Pour le tableau ci-dessus, il serait (9-0) + 1 = 10. Où 0 est la limite inférieure du tableau et 9, la limite supérieure du tableau.
  • Les tableaux peuvent être lus ou écrits à travers la boucle. Si nous lisons le tableau à une dimension, il faut une boucle pour lire et une autre pour écrire (imprimer) le tableau, par exemple:
    une. Pour lire un tableau
    pour (i = 0; i <= 9; i ++)
    {scanf (“% d”, & a [i]); }
    b. Pour écrire un tableau
    pour (i = 0; i <= 9; i ++)
    {printf (“% d”, a [i]); }
  • Dans le cas d'un tableau à deux dimensions, il faudrait deux boucles et, de même, un tableau à n dimensions nécessiterait n boucles.

Les opérations effectuées sur les tableaux sont les suivantes:

  1. Création de tableau
  2. Traverser un tableau
  3. Insertion de nouveaux éléments
  4. Suppression des éléments requis.
  5. Modification d'un élément.
  6. Fusion de tableaux

Exemple

Le programme suivant illustre la lecture et l’écriture du tableau.

#include
#include
void main ()
{
int a[10], i;
printf("Enter the array");
for ( i= 0; i <= 9; i++)
{
scanf ( "%d", &a[ i ] ) ;
}
printf( "Enter the array" );
for (i = 0 ; i <= 9 ; i++)
{
printf ( "%d\n", a[ i ] ) ;
}
getch ();
}

Définition de la liste chaînée

Liste liée est une liste particulière de certains éléments de données liés les uns aux autres. Dans cet élément, chaque élément pointe vers l'élément suivant qui représente l'ordre logique. Chaque élément est appelé un nœud, qui comporte deux parties.

Partie INFO qui stocke les informations et POINTER qui pointe vers l’élément suivant. Comme vous le savez pour stocker l'adresse, nous avons une structure de données unique en C appelée pointeurs. Par conséquent, le deuxième champ de la liste doit être un type de pointeur.

Les types de listes chaînées sont Liste simple, Liste double, Liste circulaire, Liste double.

Les opérations effectuées sur la liste chaînée sont les suivantes:

  1. Création
  2. Traverser
  3. Insertion
  4. Effacement
  5. Recherche
  6. Enchaînement
  7. Afficher

Exemple

L'extrait suivant illustre la création d'une liste liée:

struct node
{
int num;
stuct node *next;
}
start = NULL;
void create()
{
typedef struct node NODE;
NODE *p, *q;
char choice;
first = NULL;
do
{
p = (NODE *) malloc (sizeof (NODE));
printf ("Enter the data item\n");
scanf ("%d", & p -> num);
if (p == NULL)
{
q = start;
while (q -> next ! = NULL)
{ q = q -> next
}
p -> next = q -> next;
q -> = p;
}
else
{
p -> next = start;
start = p;
}
printf ("Do you want to continue (type y or n) ? \n");
scanf ("%c", &choice) ;
}
while ((choice == 'y') || (choice == 'Y'));
}

Principales différences entre un tableau et une liste chaînée

  1. Un tableau est la structure de données contient une collection d'éléments de données de type similaire alors que la liste liée est considérée comme une structure de données non primitive contient une collection d'éléments liés non ordonnés appelés nœuds.
  2. Dans le tableau, les éléments appartiennent aux index. En d'autres termes, si vous souhaitez entrer dans le quatrième élément, vous devez écrire le nom de la variable avec son index ou son emplacement entre crochets.
    Cependant, dans une liste chaînée, vous devez commencer par la tête et continuer votre chemin jusqu'au quatrième élément.
  3. Bien que l'accès à un tableau d'éléments soit rapide, alors que la liste liée prend un temps linéaire, elle est donc un peu plus lente.
  4. Des opérations telles que l'insertion et la suppression dans des tableaux prennent beaucoup de temps. D'autre part, les performances de ces opérations dans les listes liées sont rapides.
  5. Les tableaux sont de taille fixe. En revanche, les listes chaînées sont dynamiques et flexibles et peuvent augmenter et réduire leur taille.
  6. Dans un tableau, la mémoire est allouée pendant la compilation tandis que dans une liste liée, elle est allouée pendant l'exécution ou l'exécution.
  7. Les éléments sont stockés consécutivement dans des tableaux alors qu'il est stocké de manière aléatoire dans des listes liées.
  8. Les besoins en mémoire sont moindres du fait que les données réelles sont stockées dans l'index du tableau. Par contre, il est nécessaire de disposer de plus de mémoire dans les listes liées en raison du stockage d’éléments de référence supplémentaires précédents et précédents.
  9. De plus, l'utilisation de la mémoire est inefficace dans le tableau. Inversement, l'utilisation de la mémoire est efficace dans le tableau.

Conclusion

Les listes Array et Linked sont les types de structures de données qui diffèrent par leur structure, leurs méthodes d'accès et de manipulation, leurs besoins en mémoire et leur utilisation. Et avoir un avantage et un inconvénient particuliers sur sa mise en œuvre. Par conséquent, l'un ou l'autre peut être utilisé selon les besoins.

Top