Is there an insertion order preserving Set that also implements List?

I'm trying to find an implementation of java.util.List and java.util.Set at the same time in Java. I want this class to allow only unique elements (as Set) and preserve their order (like List). Does it exist in JDK 6?

It's important to have List<T>#add(int, T) so I can insert into a specific position.

TreeSet is sorted by element order; LinkedHashSet retains insertion order. Hopefully one of those is what you were after.

You've specified that you want to be able to insert at an arbitrary location, I suspect you'll have to write your own - just create a class containing a HashSet<T> and an ArrayList<T>; when adding an item, check whether or not it's in the set before adding it to the list.

Alternatively Apache's commons-collections4 offers ListOrderedSet and SetUniqueList, which behave similarly and should meet the given requirements.

LinkedHashSet is the answer.

Iteration ordering and uniqueness.

http://download.oracle.com/javase/6/docs/api/java/util/LinkedHashSet.html

Do you means like LinkedHashSet? This preserves the order of entry, but doesn't allow duplicates.

IMHO, its an unusual requirement but you can write a List without duplicates.

class SetList<T> extends ArrayList<T> {
    @Override
    public boolean add(T t) {
        return !super.contains(t) && super.add(t);
    }

    @Override
    public void add(int index, T element) {
        if (!super.contains(element)) super.add(index, element);
    }

    @Override
    public boolean addAll(Collection<? extends T> c) {
        boolean added = false;
        for (T t : c)
            added |= add(t);
        return added;
    }

    @Override
    public boolean addAll(int index, Collection<? extends T> c) {
        boolean added = false;
        for (T t : c)
            if (!super.contains(t)) {
                super.add(index++, t);
                added = true;
            }
        return added;
    }
}

You cannot implement List and Set at once without contract violation. See, for example, the Set.hashCode contract:

> The hash code of a set is defined to be the sum of the hash codes of the elements in the set, where the hash code of a null element is defined to be zero.

On the other hand here's the contract of List.hashCode:

> The hash code of a list is defined to be the result of the following calculation: > > int hashCode = 1; > for (E e : list) > hashCode = 31*hashCode + (e==null ? 0 : e.hashCode());

So it's impossible to implement single class which guarantees both contracts to be fulfilled. The same problem for equals implementation.

If you won't limit yourself to JDK 6 you could use Apache common collections library which offers exact match for your need - ListOrderedSet. It's like List and Set combined together :)

Another option (minus the List interface requirement) is Guava's ImmutableSet, which preserves insertion order. From their wiki page:

> Except for sorted collections, order is preserved from construction time. For example, > > ImmutableSet.of("a", "b", "c", "a", "d", "b") > > will iterate over its elements in the order "a", "b", "c", "d".

I had a similar problem, so I wrote my own. See here. The IndexedArraySet extends ArrayList and implements Set, so it should support all the operations that you need. Note that inserting elements into locations in the middle of an ArrayList can be slow for big lists because all the following elements need to be moved over. My IndexedArraySet doesn't change that.