LinkedList vs Pile
En java, vous pouvez utiliser la pile mise en œuvre par LinkedList. En d'autres termes, vous pouvez utiliser linkedlist pour obtenir toutes les fonctionnalités de la pile. En ce sens, pourquoi nous avons encore besoin de pile de la classe, pourquoi ne pas simplement s'en tenir à liste liée de garder la simplicité?
Grâce
- C'est un peu comme dire pourquoi avons-nous besoin ArrayList si on peut le faire avec des Tableaux.
- La plupart du temps, une Pile est mis en œuvre à l'aide d'une LinkedList.
- Pourquoi devons-nous utiliser des briques quand on peut simplement s'en tenir à des maisons pour des raisons de simplicité?
- Je dirais que l'utilisation de
Stack
plus communique clairement l'intention et forme un contrat avec le reste de l'application de la approprié des opérations. Même avec les techniques modernes d'Deque
interface etLinkedList
mise en œuvre, je serais encore de mettre en œuvre un bétonStack
classe si j'avais besoin de faire respecter ce PRINCIPE.
Vous devez vous connecter pour publier un commentaire.
Tout d'abord, dans l'introduction de
Stack
la documentation, il est dit:Qui nous dit que le
Stack
classe est principalement un reste qui est devenu plus ou moins redondantes avec la nouvelle Java Collections Cadre.Deuxième, “en offrant la même fonctionnalité” n'est pas une bonne mesure pour évaluer si une classe doit être là ou pas. Alors qu'un
LinkedList
fournit toutes les opérations qui sont nécessaires pour faire une pile, il sera de piètre qualité. Les listes chaînées sont bonnes pour l'insertion et la suppression d'éléments à des positions aléatoires. Dans une pile, nous ne jamais ajouter ou de supprimer à partir de la fin qui fait unArrayList
beaucoup plus attrayant pour implémenter une pile.À ce point, nous nous rendons compte que
ArrayList
etLinkdList
à la fois de fournir la fonctionnalité d'unList
qui nous amène à proximité du cœur de la bonne conception orientée objet:List
).ArrayList
ouLinkedList
).Stack
simplement déléguant àArrayList
, mais de fournir un type qui dit clairement dans son nom de ce que sa destinée à être et ne fournit pas d'opérations (comme l'accès aléatoire) qui serait susceptible de violer le concept d'une pile. (Ce n'est pas cejava.util.Stack
ne qui nous ramène à la citation de la documentation.Noter que la relation d'héritage entre
List
et la plus récenteDeque
interface est plus cohérent que entreList
etStack
.LinkedList
implémenteDeque
ce qui est correct depuis unDeque
exige des éléments peuvent être ajoutés ou supprimés à partir de /vers le début ou la fin etLinkedList
se qualifie pour la présente offre d'insertion et de suppression à des positions aléatoires. D'autre partStack
implémenteList
qui devrait être considérée comme discutable.De retard de mise à Jour: Depuis que je suis passer de votes pour la déclaration que “les listes chaînées sont bonnes pour l'insertion et la suppression d'éléments à des positions aléatoires. Dans une pile, nous ne jamais ajouter ou de supprimer à partir de la fin qui fait un
ArrayList
beaucoup plus attrayant pour implémenter une pile.”, Je voudrais étendre sur ce point.Listes liées permettre l'insertion et la suppression d'éléments à l'arbitraire des positions en temps constant. Sur l'autre main, il prend le temps linéaire pour trouver un élément, en fonction de son index. Quand je dis qu'ils sont bons pour l'insertion et le retrait à des positions aléatoires, je veux dire une position donnée par un itérateur, pas un indice. Si un indice est donné, l'insertion et la suppression sera linéaire-temps de l'opération pour les deux, listes et des tableaux, mais le facteur constant pour une liste chaînée sera beaucoup supérieur.
Basée sur la baie aux listes pour amorti constante de temps de l'insertion et de la suppression à la fin de la constante de temps d'accès par index. L'ajout et la suppression d'éléments à des positions aléatoires est un linéaire de la durée de fonctionnement, indépendamment de savoir si la position est donnée par un indice ou par un itérateur (qui est fondamentalement juste un indice pour un tableau).
Dans une pile de mise en œuvre, le seul avantage d'une liste chaînée – il la possibilité d'insérer et de supprimer des éléments à des positions arbitraires (donné par les itérateurs) en temps constant – n'est pas nécessaire. D'autre part, sa surcharge de la mémoire est considérablement plus élevé et de son accès à la mémoire est nettement inférieur à celui d'une ligne de tableau. Étant donné que la complexité asymptotique pour l'ajout et la suppression d'éléments de la fin de la liste est amorti constant dans les deux cas, un tableau liste est un meilleur choix pour la mise en œuvre du stockage d'une pile.
Une meilleure structure de données serait un nombre variable de taille fixe de tampons, enchaînés les uns aux autres via des pointeurs. Une telle structure de données est souvent utilisé pour mettre en œuvre un soi-disant deque. Il offre la plupart des avantages des tableaux avec très peu de charges supplémentaires et l'ajout et la suppression de /à partir de la fin (ou le début) n'est pas seulement un amorti, mais toujours une constante de temps de l'opération.
La
Stack
classe étendVector
, de sorte qu'il est synchronisé. LeLinkedList
classe ne l'est pas. Le choix optimal dépend de ce que vous êtes en train de faire et les contraintes, mais en général, il y a un peu plus de surcharge pour la synchronisation de classes. Aussi, comme @NESPowerGlove mentionné,Deque
et sa mise en oeuvre sont préférés auxStack
En utilisant une structure de données lorsque vous pouvez utiliser un plus étroitement l'étendue ou plus bonne structure de données est problématique pour deux raisons:
Le mieux adapté structure de données peut être plus optimisé pour le sous-ensemble des opérations ou des opérations spécifiques qu'il a (par exemple, supposons que votre application a besoin d'une Liste, et c'primaire juste insère des données dans le milieu de la liste tout à fait couramment, vous souhaitez mai à envisager une LinkedList rapport à une liste de tableaux, les mêmes opérations, mais LinkedList est plus adapté que l'insert(n) le fonctionnement est optimisé sur les autres opérations/les fonctionnalités).
Un futur lecteur de code seront confus sur les raisons de la moindre adapté la structure de données a été utilisé comme une odeur de code. Le lecteur va passer plus de temps à la lecture de votre code et peut même se substituer à elle, même si les opérations actuellement utilisés ne sont pas des plus optimisé lors de la commutation au mieux la structure des données.
Sur une note de côté, le plus moderne de la pile mise en œuvre en Java est java.util.Deque.