4

What is the most efficient way of maintaining a list that does not allow duplicates, but maintains insertion order and also allows the retrieval of the last inserted element in Java?

Wayne
  • 914
  • 2
  • 13
  • 25

3 Answers3

10

Try LinkedHashSet, which keeps the order of input.

Note that re-inserting an element would update its position in the input order, thus you might first try and check whether the element is already contained in the set.

Edit:

You could also try the Apache commons collections class ListOrderedSet which according to the JavaDoc (if I didn't missread anything again :) ) would decorate a set in order to keep insertion order and provides a get(index) method.

Thus, it seems you can get what you want by using new ListOrderedSet(new HashSet());

Unfortunately this class doesn't provide a generic parameter, but it might get you started.

Edit 2:

Here's a project that seems to represent commons collections with generics, i.e. it has a ListOrderedSet<E> and thus you could for example call new ListOrderedSet<String>(new HashSet<String>());

Thomas
  • 87,414
  • 12
  • 119
  • 157
  • 3
    That last part is wrong. Straight from the JavaDoc: "Note that insertion order is not affected if an element is re-inserted into the set." – Joachim Sauer Apr 22 '11 at 11:36
  • Thanks, this is almost what I wanted but I noticed that it has no get(index) method. I need a way to retrieve the last inserted element without iterating through the whole Set. I've updated the question to reflect this. – Wayne Apr 22 '11 at 12:25
  • Unfortunately the JRE doesn't come with a class that implements `List` and doesn't allow duplicates. In that case you'll have to implement it yourself (probably by combining a `List` implementation with a `Set` implementation). – Joachim Sauer Apr 22 '11 at 12:37
  • As of version 4.0 of the Apache commons collections library, [ListOrderedSet](https://commons.apache.org/proper/commons-collections/javadocs/api-release/org/apache/commons/collections4/set/ListOrderedSet.html) now supports generics. – Wesley Womack Apr 29 '15 at 13:21
  • FYI… Regarding that strikeout portion about a duplicate element replacing the original while being added last, here is a Question actually asking for that behavior: [LinkedHashSet - insertion order and duplicates - keep newest “on top”](http://stackoverflow.com/q/36399845/642706). The solution is to subclass and override `LinkedHashSet::add` method. – Basil Bourque Apr 04 '16 at 19:15
0

I don't think there's anything in the JDK which does this.

However, LinkedHashMap, which is used as the basis for LinkedHashSet, comes close: it maintains a circular doubly-linked list of the entries in the map. It only tracks the head of the list not the tail, but because the list is circular, header.before is the tail (the most recently inserted element).

You could therefore implement what you need on top of this. LinkedHashMap has not been designed for extension, so this is somewhat awkward. You could copy the code into your own class and add a suitable last() method (be aware of licensing issues here), or you could extend the existing class, and add a method which uses reflection to get at the private header and before fields.

That would get you a Map, rather than a Set. However, HashSet is already a wrapper which makes a Map look like a Set. Again, it is not designed for general extension, but you could write a subclass whose constructor calls the super constructor, then uses more reflection to replace the superclass's value of map with an instance of your new map. From there on, the class should do exactly what you want.

As an aside, the library classes here were all written by Josh Bloch and Neal Gafter. Those guys are two of the giants of Java. And yet the code in there is largely horrible. Never meet your heroes.

Tom Anderson
  • 46,189
  • 17
  • 92
  • 133
-1

Just use a TreeSet.

Joachim Sauer
  • 302,674
  • 57
  • 556
  • 614
Jakob Alexander Eichler
  • 2,988
  • 3
  • 33
  • 49