CODEWITHSUNDEEP
javadata-structureslinked-list
user3473949
user3473949

Reputation: 205

Java delete node from linked list by reference

How do I efficiently remove a node from java's LinkedList by reference to an object, or to a specific node? using remove(object) uses a traversal over the whole list, as evidenced by the documentation: "removes the first element e such that (o==null ? e==null : o.equals(e))". Can I remove by specific reference to a node? I don't mind storing the reference to the node in the object itself. I can't use the index of the list, as it may change. If not, is there another data structure which would allow me to do this?

Upvotes: 3

Views: 1479

Answers (2)

tskuzzy
tskuzzy

Reputation: 36476

Try using a LinkedHashSet. It's basically a HashSet with a deterministic ordering to its elements. Or alternatively, you can view it as a LinkedList backed with by an element look-up table.

I believe the remove(Object) operation will be constant-time.

Upvotes: 2

cheseaux
cheseaux

Reputation: 5315

You may want to use a HashSet

Deletion, insertion are in general in constant time, as stated by the official API :

This class offers constant time performance for the basic operations (add, remove, contains and size), assuming the hash function disperses the elements properly among the buckets

If you decide to use a HashSet, don't forget to override both equals AND hashcode methods in your object.

Upvotes: 2

Related Questions