D'abord vous devez considérer si vous allez supprimer du centre de la liste souvent par rapport à la longueur de la liste. Si votre liste contient N, mais que vous supprimez moins souvent 1/N, ne vous inquiétez pas. Utilisez LinkedList ou ArrayDeque comme vous préférez. (Si vos listes sont parfois énormes et puis rétrécissent, mais sont généralement petites, LinkedList est préférable car il est facile de récupérer la mémoire, sinon, ArrayDeque n'a pas besoin d'objets supplémentaires, donc c'est un peu plus rapide et plus compact - sauf le sous-jacent tableau ne rétrécit)
Si, d'autre part, vous supprimez un peu plus souvent que 1/N, alors vous devriez envisager un LinkedHashSet, qui maintient une file d'attente de liste chaînée au-dessus d'un ensemble de hachage -. mais est un ensemble, alors gardez à l'esprit que vous ne pouvez pas stocker des éléments en double. Cela a les frais généraux de LinkedList et ArrayDeque mis ensemble, mais si vous faites des suppressions centrales souvent, ça va probablement en valoir la peine.La structure optimale, cependant - si vous avez vraiment besoin de chaque once de vitesse et que vous êtes prêt à passer le temps de codage pour l'obtenir - serait une matrice "redimensionnable" (c'est-à-dire réallouée quand elle était trop petite) avec un tampon circulaire où vous pouvez effacer les éléments du milieu en les mettant à null. (Vous pouvez également réaffecter la mémoire tampon lorsque trop était vide si vous avez un cas d'utilisation perverse alors.) Je ne conseille pas de coder ceci, sauf si vous aimez vraiment coder des structures de données hautes performances ou si vous avez de bonnes preuves que c'est l'un des goulots d'étranglement dans votre code et donc vous en avez vraiment besoin.
Vous pensez à un skiplist? http://en.wikipedia.org/wiki/Skip_list Les causes ajoutent et suppriment être O (log n) –
ouais j'ai étudié les skiplists par pugh et al, ils semblent être une solution viable –