Différence entre la liste de tableaux et la liste liée

Comment les données sont-elles stockées??

Liste de tableaux et Liste liée sont des termes courants en matière de stockage et de récupération de données. Bien qu'il existe de nombreux périphériques de stockage, ils dépendent en fin de compte du mécanisme de stockage. Ces deux mécanismes de stockage placent vos données dans les périphériques de stockage et les récupèrent en cas de besoin. Voyons comment ils stockent des données dans leur mémoire. La liste de tableaux utilise un stockage séquentiel et les éléments de données sont stockés les uns après les autres. C'est peut-être une forme plus simple de stockage - cela évite la confusion. Oui, nous pouvons récupérer l'élément ou les données suivants de l'emplacement de mémoire suivant de la liste de tableaux. Cependant, il est stocké à l'aide de pointeurs dans la liste liée. Ici, nous avons besoin de deux emplacements de mémoire pour le stockage - un pour les données, l’autre pour le pointeur. Un pointeur indique l'emplacement mémoire des données suivantes. Nous pouvons facilement comprendre que la liste liée ne stocke jamais les données de manière séquentielle; il utilise plutôt un mécanisme de stockage aléatoire. Les pointeurs sont les éléments clés pour localiser les emplacements de données dans la mémoire..

Tableau dynamique et liste chaînée

Nous avons déjà discuté de la manière dont les deux mécanismes de stockage insèrent des données et nous pouvons donner le terme «tableau dynamique» pour le schéma de stockage interne de la liste Array. Il ne fait que mettre les éléments de données les uns après les autres - d'où le nom - alors que la liste liée utilise une liste interne à l'aide de pointeurs pour suivre l'élément suivant. Par conséquent, il utilise une liste liée interne, comme une liste simple ou double, pour nous montrer les données suivantes..

Utilisation de la mémoire

Comme la liste de tableaux ne stocke que les données réelles, nous avons besoin d'espace uniquement pour les données que nous stockons. Inversement, dans la liste liée, nous utilisons également des pointeurs. Par conséquent, deux emplacements de mémoire sont requis et nous pouvons dire que la liste chaînée consomme plus de mémoire que la liste Array. Un des avantages de la liste liée est qu’elle ne nécessite jamais d’emplacement de mémoire continue pour stocker nos données, contrairement à la liste Array. Les pointeurs sont capables de maintenir la position du prochain emplacement de données et nous pouvons même utiliser des emplacements de mémoire plus petits qui ne sont pas continus. En ce qui concerne l'utilisation de la mémoire, les pointeurs jouent le rôle principal dans la liste liée, tout comme leur efficacité..

Taille de la liste de tableaux initiale et de la liste liée

Avec la liste Array, même une liste vide nécessite une taille de 10, mais avec une liste liée, nous n'avons pas besoin d'un espace aussi vaste. Nous pouvons créer une liste liée vide avec une taille de 0. Plus tard, nous pouvons augmenter la taille si nécessaire.

Récupération de données

La récupération des données est plus simple dans la liste Array car elle est stockée séquentiellement. Tout ce qu'il fait est d'identifier le premier emplacement de données; de là, le prochain emplacement est accédé séquentiellement pour récupérer le reste. Il calcule comme la première position de données + 'n', où 'n' est l'ordre des données dans la liste Array. La liste liée fait référence au pointeur initial pour trouver le premier emplacement de données, puis au pointeur associé à chaque donnée pour rechercher le prochain emplacement de données. Le processus de récupération dépend principalement des pointeurs ici, et ils nous indiquent efficacement l'emplacement de données suivant..

Fin des données

La liste de tableaux utilise une valeur null pour marquer la fin des données, tandis que la liste liée utilise un pointeur null à cette fin. Dès que le système reconnaît les données nulles, la liste de tableaux arrête la récupération des données suivante. De la même manière, le pointeur nul empêche le système de passer à la prochaine extraction de données..

Traversée inversée

La liste chaînée nous permet de parcourir les directions inverses à l’aide de décroissant (). Cependant, nous n'avons pas une telle installation dans une liste de tableaux - la traversée inversée devient un problème ici.

Syntaxe

Regardons la syntaxe Java des deux mécanismes de stockage.

Création de liste de tableaux:

Liste arraylistsample = new ArrayList ();

Ajout d'objets à la liste de tableaux:

Arraylistsample.add («name1»);

Arraylistsample.add («name2»);

Voici à quoi ressemblera la liste de tableaux résultante - [nom1, nom2].

Création de liste chaînée:

List linkedlistsample = new linkedList ();

Ajout d'objets à la liste liée:

Linkedlistsample.add («name3»);

Linkedlistsample.add («name4»);

Voici à quoi ressemblera la liste chaînée résultante - [nom3, nom4].

 Quel est le meilleur pour l'opération Get ou Search?

La liste Array prend O (1) pour exécuter une recherche de données, tandis que la liste Liée prend u O (n) pour le n^th recherche de données. Par conséquent, une liste de tableaux utilise toujours un temps constant pour toute recherche de données, mais dans la liste Liée, le temps pris dépend de la position des données. Par conséquent, les listes de tableaux constituent toujours un meilleur choix pour les opérations Get ou Search..

Quel est le meilleur pour l'opération d'insertion ou d'addition?

La liste de tableaux et la liste liée prennent toutes deux un temps supplémentaire (0) pour l'ajout de données. Mais si le tableau est plein, la liste des tableaux prend un temps considérable pour la redimensionner et copier les éléments dans le plus récent. Dans un tel cas, la liste liée est le meilleur choix.

Quel est le meilleur pour l'opération de suppression?

L'opération de suppression prend presque le même temps dans les listes Array et Linked. Dans la liste Array, cette opération supprime les données, puis en décale la position pour former le tableau le plus récent. Elle prend O (n) fois. Dans la liste Liée, cette opération parcourt les données particulières et modifie les positions du pointeur pour former la liste la plus récente. Le temps pour la traversée et l’enlèvement est O (n) ici aussi.

Lequel est plus vite?

Nous savons qu'une liste de tableaux utilise un tableau interne pour stocker les données réelles. Par conséquent, si des données sont supprimées, toutes les données à venir nécessitent un décalage de mémoire. Évidemment, cela prend beaucoup de temps et ralentit les choses. Un tel décalage de mémoire n'est pas requis dans la liste liée, car il ne modifie que l'emplacement du pointeur. Par conséquent, une liste liée est plus rapide qu'une liste de tableaux dans tout type de stockage de données. Toutefois, cela dépend purement du type d’opération, c’est-à-dire que, pour l’opération Get ou Search, la liste liée prend beaucoup plus de temps qu’une liste Array. Quand on regarde la performance globale, on peut dire que la liste liée est plus rapide.

Quand utiliser une liste de matrices et une liste liée?

Une liste de tableaux convient mieux aux besoins de données moins importants, lorsque la mémoire continue est disponible. Mais lorsque nous traitons d'énormes quantités de données, la disponibilité de la mémoire continue met en œuvre les mécanismes de stockage de données, qu'ils soient petits ou énormes. Ensuite, choisissez lequel choisir: la liste de tableaux ou la liste liée. Vous pouvez aller de l'avant avec une liste de tableaux lorsque vous avez juste besoin de stockage et de récupération de données. Mais une liste peut vous aider au-delà en manipulant des données. Une fois que vous avez décidé de la fréquence à laquelle les données doivent être manipulées, il est important de vérifier le type de récupération de données que vous effectuez habituellement. Lorsqu'il s'agit simplement d'obtenir ou de rechercher, la liste de tableaux est le meilleur choix; pour d'autres opérations telles que l'insertion ou la suppression, continuez avec la liste liée.

Voyons les différences sous forme de tableau.

S.No	Concepts	Différences
		Liste de tableaux	Liste liée
1	Mode de stockage de données	Utilise le stockage de données séquentiel	Utilise un stockage de données non séquentiel
2	Schéma de stockage interne	Maintient un tableau dynamique interne	Maintient une liste liée
3	Utilisation de la mémoire	Nécessite de la mémoire rien que pour les données	Nécessite de la mémoire pour les données ainsi que pour les pointeurs
4	Taille de la liste initiale	Besoin d'espace pour au moins 10 articles	N'a pas besoin d'espace et on peut même créer une liste liée vide de taille 0.
5	Récupération de données	Calcule comme la première position de données + 'n', où 'n' est l'ordre des données dans la liste de tableaux	La traversée du premier ou du dernier jusqu'à ce que les données requises soit requise
6	Fin des données	Les valeurs nulles marquent la fin	Le pointeur nul marque la fin
7	Traversée inversée	Ne le permet pas	Le permet avec l'aide de décroissant ()
8	Syntaxe de création de liste	Liste arraylistsample = new ArrayList ();	List linkedlistsample = new linkedList ();
9	Ajout d'objets	Arraylistsample.add («name1»);	Linkedlistsample.add («name3»);
dix	Obtenir ou rechercher	Prend O (1) fois et est meilleur en performance	Prend O (n) temps et la performance dépend de la position des données
11	Insérer ou ajout	Consomme du temps O (1) sauf lorsque le tableau est plein	Consomme O (1) fois en toutes circonstances
12	Suppression ou suppression	Prend O (n) temps	Prend O (n) temps
13	Quand utiliser?	Lorsque de nombreuses opérations Get ou Search sont impliquées; la mémoire disponible devrait être plus élevée même au début	Lorsqu'il y a beaucoup d'opérations d'insertion ou de suppression et que la disponibilité de la mémoire n'a pas besoin d'être continue