Which data structure to use for keeping a list unique with insertion order intact

Question

I need to add objects to a list (with List semantics) while keeping all objects in the list unique. I figured LinkedHashSet would do, but the "re-insert" clause breaks this:

LinkedHashSet<String>list = new LinkedHashSet<String>();
list.add("a");
list.add("b");
list.add("c");
list.add("a");
list.add("a");
System.out.println (list);

Output from the above is: [a, b, c], not [b, c, a] as I would like it.

Is there any such data-structure in Java which handles this case?

Answer 1

try

    Set<String> set = Collections.newSetFromMap(new LinkedHashMap<String, Boolean>(16, 0.75f, true));
    set.add("a");
    set.add("b");
    set.add("c");
    set.add("a");
    set.add("a");
    System.out.println(set);

output

[b, c, a]

Answer 2

I don't think there is an out of the box data structure that does what you want as it seems a little odd. I would suggest you create a wrapper around LinkedHashSet that pops the element when you try to re-inserts it and than inserts it again.

Answer 3

Actually there is an out of the box data structure provided by the JDK libraries. If you look at this LinkedHashMap constructor:

/**
 * Constructs an empty <tt>LinkedHashMap</tt> instance with the
 * specified initial capacity, load factor and ordering mode.
 *
 * @param  initialCapacity the initial capacity
 * @param  loadFactor      the load factor
 * @param  accessOrder     the ordering mode - <tt>true</tt> for
 *         access-order, <tt>false</tt> for insertion-order
 * @throws IllegalArgumentException if the initial capacity is negative
 *         or the load factor is nonpositive
 */
public LinkedHashMap(int initialCapacity,
                     float loadFactor,
                     boolean accessOrder) {
    super(initialCapacity, loadFactor);
    this.accessOrder = accessOrder;
}

there is an extra parameter accessOrder. Based on this, a newly added object will be moved to the end of the list (accessOrder - true) or remain at the old location (accessOrder - false).

In order to create a Set with these characteristics, you would need to use this factory method from java.util.Collections: newSetFromMap(LinkedHashMap(initialCapacity, loadFactor, accessOrder))

Keep in mind that the accessOrder property is responsible for all interactions with given element - if you'd call get on HashMap it will do reordering as well (that shouldn't affect you anyway because the Set interface does not expose a get method on a wrapped HashMap, just saying).