CODEWITHSUNDEEP
javaalgorithmcollections
user7993435
user7993435

Reputation:

Java LinkedHashSet remove(Object obj) method constant/linear time complexity?

In the docs, it is stated that

Like HashSet, [LinkedHashSet] provides constant-time performance for the basic operations (add, contains and remove), assuming the hash function disperses elements properly among the buckets.

I understand how HashSet can provide constant-time performance for remove(Object obj), but since LinkedHashSet needs to maintain a linked list as well, and removing a specific element involves traversing the list, then it seems to me that remove(Object obj) should take linear time. Am I missing anything?

The only explanation I can think of is that each entry in the hash table (maintained by LinkedHashSet) contains a reference to the corresponding node in the linked list, so it takes constant time to locate the node in the linked list. But I am not sure if it is really the implementation...

Thanks!

Upvotes: 5

Views: 4005

Answers (1)

Hulk
Hulk

Reputation: 6573

LinkedHashSet maintains links between the nodes in addition to the hash table. It is not necessary to traverse the whole list for removal, only the list neighbors need to be updated. Accessing a specific element is no more expensive than for the HashSet.

Upvotes: 5

Related Questions