javaiterationlinkedhashset

Cost of inserting element at 0th position of LinkedHashSet, or can we iterate it backwards?


I'm using LinkedHashSet. I want to insert items at the 0th position, like:

Set<String> set = new LinkedHashSet<String>();
for (int i = 0; i < n; i++) {
    set.add(0, "blah" + i);
}

I'm not sure how LinkedHashSet is implemented, is inserting going to physically move all addresses of current items, or is it the same cost as inserting as in a linked-list implementation?

Edit

Complete mess up by me: was referencing the ArrayList docs. The Set interface has no add(index, object) method. Is there a way to iterate over the set backwards then? Right now to iterate I'm doing:

for (String it : set) {
}

Can we do that in reverse?


Solution

  • Sets are, by definition, independent of order. Thus, Set doesn't have add(int , Object) method available.

    This is also true of LinkedHashSet http://download.oracle.com/javase/6/docs/api/java/util/LinkedHashSet.html

    LinkedHashSet maintains insertion order and thus all elements are added at the end of the linked list. This is achieved using the LinkedHashMap. You can have a look at the method linkEntry in LinkedHashMap http://www.docjar.com/html/api/java/util/LinkedHashMap.java.html

    Edit: in response to edited question

    There is no API method available to do this. But you can do the following

    1. Add Set to a List using new ArrayList(Set)
    2. Use Collections.reverse(List)
    3. Iterate this list