Bonjour à tous,
On m'a soumis un problème il y a peu, sur lequel je me suis penché, et sur lequel je tombe en désaccord avec la Javadoc (oui, je sais, ça penche plutôt en leur faveur).
Concrêtement, la question est "Quelle classe Java faut-il utiliser pour implémenter une file? Une pile?".
D'après la javadoc, il faut utiliser une implémentation de l'interface Deque, soit une ArrayDeque, soit une LinkedList.
Toujours d'après la javadoc, en ce qui concerne ArrayDeque, on peut lire :(pas de comparaison LinkedList/ArrayDeque en ce qui concerne les piles par contre).Citation:
This class is likely to be faster than Stack when used as a stack, and faster than LinkedList when used as a queue.
Par curiosité je me suis penché vers le code de ces deux classes pour comprendre un peu mieux, et j'ai été assez surpris.
LinkedList est en fait une implémentation d'une liste circulaire doublement chaînée (ajout en début et fin, suppression en début et fin en temps constant, et recherche en O(n)).
ArrayDeque est une implémentation de file avec pointer sur la tête et sur la queue : ajout en début et fin en temps constant (en général), suppression en début en O(n), en fin constant, et enfin recherche en O(n).
Je dis "en général" et que la suppression en début de file n'est pas constante car on a sans cesse des déplacements de tableau (#System.arrayCopy).
D'ailleurs on peut lire :
Or pour une file, l'élément supprimé est toujours le premier, autrement dit on a un O(n) bien assumé (car vérifié à chaque suppression).Citation:
Most ArrayDeque operations run in amortized constant time. Exceptions include remove, removeFirstOccurrence, removeLastOccurrence, contains, iterator.remove(), and the bulk operations, all of which run in linear time.
D'où mes conclusions: l'utilisation d'un ArrayDeque est plus coûteuse que l'utilisation d'une LinkedList pour une file, ce qui est totalement contradictoire avec ce que spécifie la javadoc.
Qu'en pensez-vous ?
