Bug in LinkedHashSet javadoc?

Question

Maybe I'm being picky, but in javadoc there is a following information about LinkedHashSet implementation:

This implementation differs from HashSet in that it maintains a doubly-linked list running through all of its entries.

I can't find any double-linked list in LinkedHashSet class. Can somebody help?

Answer 1

Yeah, it's a bit wonky when you look at the source without drilling down. Notice it calls that package protected HashSet constructor that takes a meaningless boolean called dummy:

public LinkedHashSet(int initialCapacity, float loadFactor) {
    super(initialCapacity, loadFactor, true);
}

That then uses a LinkedHashMap instead of a HashMap to back the set. Effectively, LinkedHashSet is actually inside HashSet, it's just package protected so you have to use LinkedHashSet to get at it.

Answer 2

The doubly-linked list is on the implementation side, not necessarily exposed for you to get and use.

It keeps the doubly linked list so it can keep track of the order your items are inserted into the set (and also for order of accessing elements in access-order LinkedHashMaps). A regular HashSet has no need for a doubly-linked list since it makes no guarantee about the order of its contents.

They probably included that bit in the javadoc just so you were aware of how they did it, and that there is a little more going on behind the scenes with a LinkedHashSet than a regular HashSet.

You can take a peek at the source code at Google Code Search (you will notice that a LinkedHashSet is actually just wrapped around a LinkedHashMap, but that's not a very important detail).

In the end, it's not a mistake in the javadocs and you shouldn't worry about the fact there is a doubly-linked list working within the LinkedHashSet and LinkedHashMap. We can just merrily take advantage of the LinkedHashMap maintaining order of insertion, paying no mind to what is happening behind the scenes.