Discussion :

[Marco la baraque]

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 :

This class is likely to be faster than Stack when used as a stack, and faster than LinkedList when used as a queue.

(pas de comparaison LinkedList/ArrayDeque en ce qui concerne les piles par contre).

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 :

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.

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).

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 ?

[pseudocode]

Les 2 classes ont a même complexité (en nombre d'operation) pour les méthodes push/pop.

Par contre, la "LinkedList" fait à chaque fois des créations/suppressions d'instances de "Entry", ce qui est moins performant que la réutilisation des cases du tableau de "ArrayDeque" (au détriment de l'occupation mémoire).

[Marco la baraque]

Merci pseudocode.
Ce qui me posait problème en ce qui concerne la complexité, ce n'est pas au niveau des méthodes push et pop, mais removeFirst/pollFirst (dans le cas des FIFO, c'est le premier élément qu'on enlève).

L'ArrayDeque fait en effet une copie du tableau entier pour le décaler lors de la suppression d'un élément, ce qui peut-être coûteux. Cependant, après vérification, lors de la suppression du premier élément du tableau, il n'y a aucun System.arrayCopy (ça commence à partir du 2ème élément), donc en fait au niveau de la complexité tu as raison, c'est la même que pour la LinkedList.

Merci de tes éclaircissements.