Tableau et Liste chaînée sont les deux manières d’organiser les données dans la mémoire. Avant de comprendre les différences entre les Tableau et le Liste liée , on regarde d'abord dans un tableau et une liste chaînée .
bouton central en CSS
Qu'est-ce qu'un tableau ?
Une structure de données qui contient les éléments du même type. Une structure de données est une manière d'organiser les données ; un tableau est une structure de données car il organise les données de manière séquentielle. Un tableau est une grande partie de la mémoire dans laquelle la mémoire est divisée en petits blocs, et chaque bloc est capable de stocker une certaine valeur.
Supposons que nous ayons créé un tableau composé de 10 valeurs, chaque bloc stockera la valeur d'un type entier. Si nous essayons de stocker la valeur dans un tableau de types différents, alors ce n'est pas un tableau correct et générera une erreur de compilation.
Déclaration de tableau
Un tableau peut être déclaré comme suit :
data_type name of the array[no of elements]
Pour déclarer un tableau, nous devons d’abord spécifier le type du tableau puis le nom du tableau. À l’intérieur des crochets, nous devons spécifier le nombre d’éléments que notre tableau doit contenir.
Comprenons à travers un exemple.
int a[5];
Dans le cas ci-dessus, nous avons déclaré un tableau de 5 éléments avec ' un 'nom d'un entier Type de données.
Qu'est-ce que la liste chaînée ?
Une liste chaînée est une collection de nœuds stockés de manière aléatoire. Chaque nœud est constitué de deux champs, c'est-à-dire données et lien . Ici, les données sont la valeur stockée sur ce nœud particulier et le lien est le pointeur qui contient l'adresse du nœud suivant.
Différences entre un tableau et une liste chaînée
Nous ne pouvons pas dire quelle structure de données est la meilleure, c'est-à-dire un tableau ou liste chaînée . Il peut être possible qu'une structure de données soit meilleure pour un type d'exigence, tandis que l'autre structure de données est meilleure pour un autre type d'exigence. Il existe divers facteurs tels que les opérations fréquentes effectuées sur la structure des données ou la taille des données, ainsi que d'autres facteurs sur la base desquels la structure des données est sélectionnée. Nous allons maintenant voir quelques différences entre le tableau et la liste chaînée en fonction de certains paramètres.
1. Coût d'accès à un élément
Dans le cas d'un tableau, quelle que soit sa taille, un tableau prend un temps constant pour accéder à un élément. Dans un tableau, les éléments sont stockés de manière contiguë, donc si nous connaissons l'adresse de base de l'élément, nous pouvons facilement obtenir l'adresse de n'importe quel élément d'un tableau. Nous devons effectuer un calcul simple pour obtenir l’adresse de n’importe quel élément d’un tableau. Ainsi, accéder à l’élément dans un tableau est O(1) en termes de complexité temporelle.
Dans la liste chaînée, les éléments ne sont pas stockés de manière contiguë. Il se compose de plusieurs blocs et chaque bloc est représenté comme un nœud. Chaque nœud a deux champs, c'est-à-dire qu'un est destiné au champ de données et un autre stocke l'adresse du nœud suivant. Pour trouver un nœud dans la liste chaînée, nous devons d’abord déterminer le premier nœud appelé nœud principal. Si nous devons trouver le deuxième nœud de la liste, alors nous devons parcourir à partir du premier nœud, et dans le pire des cas, pour trouver le dernier nœud, nous traverserons tous les nœuds. Le cas moyen pour accéder à l’élément est O(n).
css changer la taille de l'image
Nous concluons que le coût d’accès à un élément d’un tableau est inférieur à celui d’une liste chaînée. Par conséquent, si nous avons besoin d’accéder aux éléments, alors le tableau est un meilleur choix.
2. Coût d'insertion d'un élément
Il peut y avoir trois scénarios dans l'insertion :
Dans le cas d'une liste chaînée, pour insérer un élément au début de la liste chaînée, on va créer un nouveau nœud, et l'adresse du premier nœud est ajoutée au nouveau nœud. De cette façon, le nouveau nœud devient le premier nœud. Ainsi, la complexité temporelle n’est pas proportionnelle à la taille de la liste. La complexité temporelle serait constante, c'est-à-dire O(1).
Si le tableau n'est pas plein, nous pouvons alors ajouter directement le nouvel élément via l'index. Dans ce cas, la complexité temporelle serait constante, c'est-à-dire O(1). Si le tableau est plein, nous devons d'abord copier le tableau dans un autre tableau et ajouter un nouvel élément. Dans ce cas, la complexité temporelle serait O(n).
Pour insérer un élément à la fin de la liste chaînée, il faut parcourir toute la liste. Si la liste chaînée se compose de n éléments, alors la complexité temporelle serait O(n).
Supposons que nous voulions insérer l'élément au ièmeposition du tableau ; nous devons décaler les n/2 éléments vers la droite. La complexité temporelle est donc proportionnelle au nombre d’éléments. La complexité temporelle serait de O(n) pour le cas moyen.
tri à bulles en Java
Dans le cas d'une liste chaînée, nous devons accéder à cette position où nous devons insérer le nouvel élément. Même si nous n’avons pas besoin d’effectuer de déplacement, nous devons plutôt passer à la position n/2. Le temps nécessaire est proportionnel au nombre n d'éléments, et la complexité temporelle pour le cas moyen serait O(n).
La liste chaînée résultante est :
La mise en œuvre d’un tableau est simple par rapport à la liste chaînée. Lors de la création d'un programme à l'aide d'une liste chaînée, le programme est plus sujet aux erreurs telles qu'une erreur de segmentation ou une fuite de mémoire. Il faut donc faire très attention lors de la création d’un programme dans la liste chaînée.
La liste chaînée est de taille dynamique alors que le tableau est statique. Ici, statique ne signifie pas que nous ne pouvons pas décider de la taille au moment de l'exécution, mais nous ne pouvons pas la modifier une fois la taille décidée.
3. Exigences en matière de mémoire
Comme les éléments d’un tableau sont stockés dans un bloc de mémoire contigu, le tableau est de taille fixe. Supposons que nous ayons un tableau de taille 7 et que le tableau se compose de 4 éléments, le reste de l'espace est inutilisé. La mémoire occupée par les 7 éléments :
Espace mémoire = 7*4 = 28 octets
Où 7 est le nombre d'éléments dans un tableau et 4 est le nombre d'octets d'un type entier.
En cas de liste chaînée, il n'y a pas de mémoire inutilisée mais la mémoire supplémentaire est occupée par les variables de pointeur. Si les données sont de type entier, alors la mémoire totale occupée par un nœud est de 8 octets, soit 4 octets pour les données et 4 octets pour la variable de pointeur. Si la liste chaînée est composée de 4 éléments, alors l'espace mémoire occupé par la liste chaînée serait :
pilote Web
Espace mémoire = 8*4 = 32 octets
La liste chaînée serait un meilleur choix si la partie données est plus grande. Supposons que les données soient de 16 octets. L'espace mémoire occupé par le tableau serait de 16*7=112 octets tandis que la liste chaînée occupe 20*4=80, nous avons spécifié ici 20 octets comme 16 octets pour la taille des données plus 4 octets pour la variable de pointeur. Si nous choisissons une taille de données plus grande, la liste chaînée consommera moins de mémoire ; sinon, cela dépend des facteurs que nous adoptons pour déterminer la taille.
Examinons les différences entre le tableau et la liste chaînée sous forme de tableau.
| Tableau | Liste chaînée |
|---|---|
| Un tableau est une collection d’éléments d’un type de données similaire. | Une liste chaînée est une collection d'objets connue sous le nom de nœud, où le nœud se compose de deux parties, à savoir les données et l'adresse. |
| Les éléments du tableau sont stockés dans un emplacement mémoire contigu. | Les éléments de liste chaînée peuvent être stockés n'importe où dans la mémoire ou stockés de manière aléatoire. |
| Array fonctionne avec une mémoire statique. Ici, la mémoire statique signifie que la taille de la mémoire est fixe et ne peut pas être modifiée au moment de l'exécution. | La liste chaînée fonctionne avec la mémoire dynamique. Ici, la mémoire dynamique signifie que la taille de la mémoire peut être modifiée au moment de l'exécution en fonction de nos besoins. |
| Les éléments du tableau sont indépendants les uns des autres. | Les éléments de la liste chaînée dépendent les uns des autres. Comme chaque nœud contient l'adresse du nœud suivant, pour accéder au nœud suivant, nous devons accéder à son nœud précédent. |
| Le tableau prend plus de temps lors de l'exécution d'une opération telle que l'insertion, la suppression, etc. | La liste chaînée prend moins de temps lors de l'exécution d'une opération telle que l'insertion, la suppression, etc. |
| L'accès à n'importe quel élément d'un tableau est plus rapide car l'élément d'un tableau est directement accessible via l'index. | L'accès à un élément dans une liste chaînée est plus lent car il commence à parcourir à partir du premier élément de la liste chaînée. |
| Dans le cas d'un tableau, la mémoire est allouée au moment de la compilation. | Dans le cas d'une liste chaînée, la mémoire est allouée au moment de l'exécution. |
| L'utilisation de la mémoire est inefficace dans la baie. Par exemple, si la taille du tableau est de 6 et que le tableau se compose de 3 éléments seulement, le reste de l'espace sera inutilisé. | L'utilisation de la mémoire est efficace dans le cas d'une liste chaînée car la mémoire peut être allouée ou désallouée au moment de l'exécution selon nos besoins. |