Une liste chaînée Java qui supporte la suppression rapide de n'importe quel nœud ?

Question

La liste java.util.LinkedList ne permet pas de supprimer rapidement un objet donné de la liste. La méthode remove(object) effectue une recherche linéaire pour trouver l'objet dans la liste afin de pouvoir le supprimer. Comme il s'agit d'une liste chaînée double, il serait agréable de supprimer un objet en mettant simplement à jour les pointeurs (node.prev et node.next).

Quelle est la solution standard de Java pour ce problème ?

NOTE1 : Je ne veux pas supprimer pendant l'itération. Je sais que c'est rapide, mais je ne suis pas en train d'itérer à travers mes éléments en premier lieu.

NOTE2 : Pour faire simple : Étant donné un objet O dont je sais qu'il se trouve dans une liste chaînée double, je veux retirer rapidement O de cette liste (en mettant à jour les pointeurs) sans avoir à le rechercher linéairement dans la liste, comme le fait java.util.LinkedList.

Answer 1

Vous devriez jeter un coup d'œil à la LinkedHashSet classe. En gros, c'est un HashSet qui maintient une liste doublement liée parmi ses entrées. Elle supporte la récupération (et donc aussi la suppression) d'un élément en O(1) (si tout va bien). Vérifiez le lien pour la spécification sur la façon dont il gère l'ordre des éléments en cas de réinsertion d'une entrée et d'autres détails.

EDIT :

Si vous avez besoin de stocker des doublons, vous pouvez jeter un coup d'œil à la section Goyave LinkedHashMultiset (jamais utilisé jusqu'à présent). Le guide de l'utilisateur Guava sur Multiset est le suivant ici .

Answer 2

Je vous parie que l'implémentation de LinkedList#remove() le supprime en mettant à jour les pointeurs vers les éléments précédents et suivants - le problème est qu'il doit boucler sur tous les objets jusqu'à ce qu'il trouve celui qu'il faut supprimer.

Si vous voulez une collection qui se retire plus rapidement, sans itérer sur tous les objets, utilisez une Set ou un Map .

Answer 3

Il semble que vous ayez besoin d'un objet composite. Créez une classe qui contient votre liste, tout en maintenant un index dans cette liste.

Ainsi, pour effectuer un retrait rapide, vous effectuez une recherche d'index en temps constant, pour obtenir une référence à l'élément de la liste que vous souhaitez retirer, suivie d'un retrait en temps constant.

Answer 4

En général, vous voulez travailler en utilisant le ListIterator si possible. C'est remove sera un temps constant.

La bibliothèque standard de Java ne dispose pas d'une structure distincte de nœuds de liste liée, donc je pense que ListIterator est la meilleure option.

Answer 5

Une carte serait peut-être appropriée. Elle donne attendu Temps de retrait O(1). Mais là encore, vous n'avez pas précisé ce que rapide signifie.

Une liste soutenue par une BST pourrait également fonctionner. Cela donnerait un temps de suppression log(n).

Pour les solutions listées ici, j'ai supposé quelque chose de plus rapide que l'itération dans la liste, donc tout ce qui est plus rapide que O(n) ;