Je suis un débutant en Java. Veuillez me suggérer quelle(s) collection(s) peut/doivent être utilisée(s) pour maintenir une liste triée en Java. J'ai essayé Map et Set mais ce n'était pas ce que je recherchais.
Réponse
Trop de publicités?
Jakub Zaverka
Points
5909
Ce que vous voulez, c'est un arbre de recherche binaire. Il maintient l'ordre trié tout en offrant un accès logarithmique pour les recherches, les suppressions et les insertions (sauf si vous avez un arbre dégénéré - dans ce cas, c'est linéaire). Il est assez facile à mettre en œuvre et vous pouvez même lui faire implémenter l'interface List, mais l'accès à l'index devient alors compliqué.
La deuxième approche consiste à utiliser une liste de tableaux et à mettre en œuvre un tri à bulles. Comme vous insérez ou supprimez un élément à la fois, les temps d'accès pour les insertions et les suppressions sont linéaires. Les recherches sont logarithmiques et l'accès à l'index est constant (les temps peuvent être différents pour les LinkedList). Le seul code dont vous avez besoin est 5, peut-être 6 lignes de tri à bulles.
- Réponses précédentes
- Plus de réponses
