Structure de données qui permet l'insertion, la suppression et l'accès aléatoire.

Question

Actuellement, je cherche la structure de données suivante.

1. Rapide à insérer à la queue.
2. Rapide à retirer de la tête.
3. Capable d'effectuer des accès aléatoires.

Je réalise ArrayBlockingQueue est bon en (1) et (2), et ArrayList est bon à (3). Existe-t-il une structure de données unique, issue de la bibliothèque standard, des bibliothèques Apache ou des bibliothèques Google, qui me permette de répondre aux trois exigences à la fois ?

Answer 1

Je pense que la meilleure structure de données pour votre cas est une tampon annulaire/tampon circulaire . Le tampon circulaire effectue ces trois opérations en temps constant.

Une mise en œuvre peut être trouvée aquí et bien d'autres aquí

éditer : Le problème des tampons circulaires est que vous devez savoir dès le départ combien d'éléments se trouvent dans ce tampon dans le pire des cas. Mais il existe aussi des tampons dynamiques.

Answer 2

LinkedList peut convenir, si la vitesse n'est pas importante pour 3. Notez que ArrayBlockingQueue est conçu pour des environnements où plusieurs threads accèdent à la liste. ArrayList et LinkedList ne le sont pas. Vous devrez les envelopper en utilisant Collections.synchronizedList() si vous devez y accéder à partir de plusieurs threads.

Answer 3

Cartouche de hachage est celui que vous devez essayer. Il vous donne le meilleur de tous.

Combinaison de la structure de données Hash et Double LinkedList.