Quand utiliser une liste chaînée sur un tableau / une liste de tableaux?

Question

J'utilise beaucoup de listes et de tableaux, mais je n'ai pas encore rencontré de scénario dans lequel la liste de tableaux ne pourrait pas être utilisée aussi facilement, sinon plus facilement que la liste chaînée. J'espérais que quelqu'un pourrait me donner des exemples de cas où la liste chaînée est nettement meilleure.

Answer 1

Les listes chaînées sont préférables au fil des tableaux lorsque:

a) vous avez besoin de constante de temps insertions/délétions de la liste (comme dans l'informatique en temps réel où le temps de prévisibilité est absolument critique)

b) vous ne savez pas comment le nombre d'éléments dans la liste. Avec les tableaux, vous pouvez avoir besoin de re-déclarer et copie de la mémoire si le tableau devient trop gros

c) vous n'avez pas besoin d'un accès aléatoire à l'un des éléments

d) vous voulez être en mesure d'insérer des éléments dans le milieu de la liste (comme une file d'attente de priorité)

Les tableaux sont préférables lorsque:

a) vous avez besoin indexé/aléatoire l'accès aux éléments

b) vous connaissez le nombre d'éléments dans le tableau à l'avance de sorte que vous pouvez allouer le montant exact de la mémoire pour le tableau

c) vous avez besoin de vitesse lors d'une itération à travers tous les éléments dans la séquence. Vous pouvez utiliser le pointeur de calcul sur le tableau pour accéder à chaque élément, alors vous avez besoin de rechercher le nœud en fonction du pointeur pour chaque élément dans la liste liée, ce qui peut entraîner des erreurs de page qui peut entraîner une dégradation de leurs performances.

d) la mémoire est un sujet de préoccupation. Remplis les tableaux de prendre moins de mémoire que les listes chaînées. Chaque élément du tableau est juste les données. Chaque liste liée nœud a besoin de données ainsi qu'une (ou plusieurs) des pointeurs vers d'autres éléments dans la liste chaînée.

Tableau des Listes (comme ceux dans .Net vous donner les avantages de tableaux, mais d'allouer dynamiquement des ressources pour vous afin que vous n'avez pas besoin de trop s'inquiéter de la taille de la liste et vous pouvez supprimer des éléments à n'importe quel indice, sans aucun effort ou re-brassage des éléments qui nous entourent. Performance sage, arraylists sont plus lents que les premières rangées.

Answer 2

Les tableaux ont un accès aléatoire O (1), mais sont vraiment coûteux d'ajouter ou de supprimer des éléments.

Les listes chaînées sont vraiment peu coûteuses pour ajouter ou supprimer des éléments n'importe où et pour itérer, mais l'accès aléatoire est O (n).

Answer 3

Pour ajouter d'autres réponses, plus de tableau liste les implémentations de la réserve de la capacité supplémentaire à la fin de la liste, de sorte que de nouveaux éléments peuvent être ajoutés à la fin de la liste en O(1) fois. Lorsque la capacité d'un tableau liste est dépassé, un nouveau, plus grand tableau est affecté à l'interne, et de tous les anciens éléments sont copiés sur. Généralement, le nouveau tableau est le double de la taille de l'ancien. Cela signifie qu' en moyenne, l'ajout de nouveaux éléments à la fin d'une liste de tableau est un O(1) le fonctionnement de ces implémentations. Donc, même si vous ne connaissez pas le nombre d'éléments à l'avance, un tableau liste peut encore être plus rapide qu'une liste chaînée pour ajouter des éléments, aussi longtemps que vous ajoutez à la fin. De toute évidence, l'insertion de nouveaux éléments à des emplacements arbitraires dans un tableau la liste est encore un O(n) opérations.

L'accès aux éléments dans un tableau la liste est également plus rapide que d'une liste liée, même si l'accès séquentiel. C'est parce que les éléments du tableau sont stockées dans la mémoire contiguë et peut être mis en cache facilement. Lié liste des nœuds peuvent être dispersés sur plusieurs pages différentes.

Je recommanderais seulement à l'aide d'une liste liée si vous savez que vous allez être à l'insertion ou la suppression d'éléments à des emplacements arbitraires. Tableau liste sera plus rapide pour à peu près tout le reste.

Answer 4

L'avantage des listes apparaît si vous devez insérer des éléments au milieu et ne souhaitez pas commencer à redimensionner le tableau et à en déplacer les éléments.

Vous avez raison de dire que ce n'est généralement pas le cas. J'ai eu quelques cas très spécifiques comme celui-là, mais pas trop.

Answer 5

Hmm, Arraylist peut être utilisé dans les cas suivants, je suppose:

1. vous ne savez pas combien d'éléments seront présents
2. mais vous devez accéder à tous les éléments au hasard grâce à l'indexation

Par exemple, vous devez importer et accéder à tous les éléments d'une liste de contacts (dont la taille vous est inconnue).