CODEWITHSUNDEEP
javaiterationlinkedhashset
user291701
user291701

Reputation: 39721

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?

Upvotes: 3

Views: 10324

Answers (7)

wkl
wkl

Reputation: 80031

To answer your latest question, there is no reverse iterator feature available from LinkedHashSet, even though internally the implementation uses a doubly linked list.

There is an open Request For Enhancement about this: JDK-4848853.

The Guava library has a Lists.reverse method, though it actually generates a reverse list.

Upvotes: 0

M. Justin
M. Justin

Reputation: 21315

Starting with Java 21, the reversed() method can be used to return a reversed view on the set, which can then be iterated over in the standard manners (such as using an enhanced for statement):

for (String it : set.reversed()) {
    System.out.println(it);
}

Upvotes: 0

M. Justin
M. Justin

Reputation: 21315

Java 21 added the addFirst method to LinkedHashSet, which adds an element to the start of the set.

Adds an element as the first element of this collection (optional operation). After this operation completes normally, the given element will be a member of this collection, and it will be the first element in encounter order.

Upvotes: 2

Gaurav Saxena
Gaurav Saxena

Reputation: 4297

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

Upvotes: 7

ColinD
ColinD

Reputation: 110094

You can't add elements to the front of a LinkedHashSet... it has no method such as add(int, Object) nor any other methods that make use of the concept of an "index" in the set (that's a List concept). It only provides consistent iteration order, based on the order in which elements were inserted. The most recently inserted element that was not already in the set will be the last element when you iterate over it.

And the Javadoc for LinkedHashSet explicitly states:

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

Edit: There is not any way to iterate over a LinkedHashSet in reverse short of something like copying it to a List and iterating over that in reverse. Using Guava you could do that like:

for (String s : Lists.reverse(ImmutableList.copyOf(set))) { ... }

Note that while creating the ImmutableList does require iterating over each element of the original set, the reverse method simply provides a reverse view and doesn't iterate at all itself.

Upvotes: 0

Stas
Stas

Reputation: 1725

As already mentioned, LinkedHashSet is build on LinkedHashMap, which is built on HashMap :) Javadocs says that it takes constant time to add an element into HashMap, assuming that your hash function is implemented properly. If your hash function is not implemented well, it may take up to O(n). Iteration backwards in not supported at this moment.

Upvotes: -1

Nick
Nick

Reputation: 2845

Judging by the source code of LinkedHashMap (which backs LinkedHashSet -- see http://www.docjar.com/html/api/java/util/LinkedHashMap.java.html ), inserts are cheap, like in a linked list.

Upvotes: 0

Related Questions