Comment les données sont-elles stockées ?
Les termes « liste de tableaux » et « liste chaînée » sont courants lorsqu’il s’agit de stocker et d’extraire des données. Bien qu’il existe de nombreux dispositifs 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 dispositifs de stockage et les récupèrent en cas de besoin. Voyons comment ils stockent les données dans leur mémoire. La liste Array utilise un stockage séquentiel et les données sont stockées l’une après l’autre. Il s’agit peut-être d’une forme de stockage plus simple, qui évite toute confusion. Oui, nous pouvons récupérer l’élément ou les données suivants à partir de l’emplacement de mémoire suivant de la liste de tableaux ; cependant, ils sont stockés à l’aide de pointeurs dans la liste liée. Ici, nous avons besoin de deux emplacements mémoire pour le stockage – l’un pour les données, l’autre pour le pointeur. Un pointeur adresse l’emplacement mémoire de la donnée suivante. Il est facile de comprendre que la liste chaînée ne stocke jamais les données de manière séquentielle ; elle utilise plutôt un mécanisme de stockage aléatoire. Les pointeurs sont les éléments clés de la localisation des 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 placent les données et nous pouvons utiliser le terme « tableau dynamique » pour désigner le système de stockage interne de la liste de tableaux. Il se contente de placer les données les unes à la suite des autres – d’où son nom – alors que la liste liée utilise une liste interne à l’aide de pointeurs pour suivre l’élément suivant. Par conséquent, elle utilise une liste interne liée, comme une liste simple ou doublement liée, pour nous montrer les données suivantes.
Utilisation de la mémoire
Comme la liste Array ne stocke que les données réelles, nous n’avons besoin d’espace que pour les données que nous stockons. À l’inverse, dans la liste chaînée, nous utilisons également des pointeurs. Par conséquent, deux emplacements de mémoire sont nécessaires, et nous pouvons dire que la liste liée consomme plus de mémoire que la liste de tableaux. L’avantage de la liste chaînée est qu’elle ne nécessite jamais d’emplacements mémoire continus pour stocker nos données, contrairement à la liste de tableaux. Les pointeurs sont capables de conserver la position de l’emplacement de données suivant, 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 initiale de tableaux et de la liste chaînée
Avec la liste de tableaux, 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 important. Nous pouvons créer une liste liée vide avec une taille de 0. Plus tard, nous pourrons augmenter la taille si nécessaire.
Récupération de données
La recherche de données est plus simple dans une liste de tableaux, car elle stocke les données de manière séquentielle. Il suffit d’identifier le premier emplacement des données ; à partir de là, on accède à l’emplacement suivant de manière séquentielle 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 de tableaux. La liste liée fait référence au pointeur initial pour trouver la première position des données, et à partir de là, elle fait référence au pointeur associé à chaque donnée pour trouver la position suivante. Le processus de recherche dépend principalement des pointeurs, qui nous indiquent effectivement l’emplacement suivant des données.
Fin des données
La liste en tableau utilise une valeur nulle pour marquer la fin des données, alors que la liste liée utilise un pointeur nul à cette fin. Dès que le système reconnaît des données nulles, la liste en tableau interrompt l’extraction des données suivantes. De la même manière, le pointeur nul empêche le système de passer à l’extraction suivante des données.
Traversée inversée
La liste chaînée nous permet de parcourir la liste dans le sens inverse à l’aide de la fonction descendingiterator(). Cependant, nous ne disposons pas d’une telle facilité dans une liste Array – la traversée inverse devient alors un problème.
Syntaxe
Examinons la syntaxe Java des deux mécanismes de stockage.
Création d’une liste de tableaux :
Listarraylistsample = new ArrayList() ;
Ajout d’objets à la liste de tableaux :
Arraylistsample.add(« name1 ») ;
Arraylistsample.add(« nom2 ») ;
Voici à quoi ressemblera la liste de tableaux résultante – .
Création d’une liste chaînée :
Exemple de liste liée = nouvelle liste liée() ;
Ajout d’objets à la liste liée :
Linkedlistsample.add(« nom3 ») ;
Exemple de liste liée.add(« nom4 ») ;
Voici à quoi ressemblera la liste liée résultante – .
Qu’est-ce qui est mieux pour l’opération Get ou Search ?
La liste en tableau prend O(1) pour effectuer une recherche de données, alors que la liste liée prend O(n) pour la nième recherche de données. Par conséquent, une liste en tableau utilise toujours un temps constant pour toute recherche de données, alors que dans une liste liée, le temps nécessaire dépend de la position des données. Par conséquent, les listes en tableau constituent toujours un meilleur choix pour les opérations d’obtention ou de recherche.
Quel est le meilleur choix pour l’opération d’insertion ou d’addition ?
La liste en tableau et la liste liée nécessitent toutes deux un temps O(1) pour l’ajout de données. Mais si le tableau est plein, la liste en tableau prend un temps considérable pour le redimensionner et copier les éléments dans le nouveau tableau. Dans ce cas, la liste chaînée est le meilleur choix.
Quand utiliser une liste de tableaux et une liste liée ?
Une liste matricielle est mieux adaptée aux besoins en données de petite taille, lorsque l’on dispose d’une mémoire continue. Mais lorsque nous traitons d’énormes quantités de données, la disponibilité d’une mémoire continue permet de mettre en œuvre les mécanismes de stockage des données, qu’elles soient petites ou énormes. Ensuite, vous devez choisir entre la liste en tableau et la liste liée. Vous pouvez opter pour une liste de tableaux lorsque vous avez simplement besoin de stocker et d’extraire des données. Mais une liste peut aussi vous aider à manipuler des données. Une fois que vous avez déterminé la fréquence des manipulations de données nécessaires, il est important de vérifier le type de recherche de données que vous effectuez habituellement. S’il s’agit uniquement d’obtenir ou de rechercher des données, la liste de tableaux est le meilleur choix ; pour d’autres opérations telles que l’insertion ou la suppression, optez pour la liste liée.
Examinons les différences sous forme de tableau.