javalinked-listdequelinkedhashset

Why doesn't LinkedHashSet have addFirst method?


As the documentation of LinkedHashSet states, it is

Hash table and linked list implementation of the Set interface, with predictable iteration order. This implementation differs from HashSet in that it maintains a doubly-linked list running through all of its entries.

So it's essentially a HashSet with FIFO queue of keys implemented by a linked list. Considering that LinkedList is Deque and permits, in particular, insertion at the beginning, I wonder why doesn't LinkedHashSet have the addFirst(E e) method in addition to the methods present in the Set interface. It seems not hard to implement this.


Solution

  • As Eliott Frisch said, the answer is in the next sentence of the paragraph you quoted:

    … This linked list defines the iteration ordering, which is the order in which elements were inserted into the set (insertion-order). …

    An addFirst method would break the insertion order and thereby the design idea of LinkedHashSet.

    If I may add a bit of guesswork too, other possible reasons might include:

    That said, you are asking the question the wrong way around. They designed a class with a functionality for which they saw a need. They moved on to implement it using a hash table and a linked list. You are starting out from the implementation and using it as a basis for a design discussion. While that may occasionally add something useful, generally it’s not the way to good designs.

    While I can in theory follow your point that there might be a situation where you want a double-ended queue with set property (duplicates are ignored/eliminated), I have a hard time imagining when a Deque would not fulfil your needs in this case (Eliott Frisch mentioned the under-used ArrayDeque). You need pretty large amounts of data and/or pretty strict performance requirements before the linear complexity of contains and remove would be prohibitive. And in that case you may already be better off custom designing your own data structure.