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.
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 :)
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.
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.