Collection that uses ListIterator and is a unique list

Java considers List to allow non-unique items and Set to not. Sets obviously don't support ListIterators and therefore code that uses ListIterator can assume that the underlying collection is not a Set.

Java 8 doesn't use ListIterator for sorting anymore, but if you're stuck with Java 7 that doesn't really help you. Basically depending a lot on your context and usage, it might be useful to either use a Set like Thor Stan said in his response, creating a List on demand when needed.

Another option is to just provide your own ListIterator that accesses the list through a method that doesn't check for duplicates. This would have the advantage of not creating extraneous objects, but the Set option would most likely result in shorter code and is highly unlikely to be significant performance-wise.

There are probably other options too, but I can't think of any elegant ones.

As Thor Stan mentioned, a TreeSet gets you most of what you want. It ensures elements are unique, it keeps them sorted, and you can iterate it in either direction using iterator() or descendingIterator().

It's not entirely clear why you're asking for ListIterator though. Most things about a ListIterator are very positional: the notion of an index, or adding something at the current position, or setting the current element. These don't make sense for a sorted set.

One aspect of a ListIterator that you might be looking for, though, is the ability to reverse directions in the midst of iteration. You can't do this directly with a TreeSet iterator, since it offers access only via an ordinary Iterator instead of a ListIterator.

However, a TreeSet implements the NavigableSet interface, which lets you step through the elements in order, in either direction. The NavigableSet interface is a subinterface of SortedSet, which provides the first() and last() methods to get you started at one of the "ends" of the set. Once you have an element in the set, you can step in either direction using the lower(E) and higher(E) methods. Or, if you want to start somewhere in the middle, you can't start at a position by index, but you can start with a value (which needn't be a member of the set) and then call lower(E) or higher(E).

For example:

    TreeSet<String> set = new TreeSet<>(
        Arrays.asList("a", "z", "b", "y"));
    String cur;

    cur = set.first();     // a
    cur = set.higher(cur); // b
    cur = set.higher(cur); // y
    cur = set.higher(cur); // z
    cur = set.lower(cur);  // y
    cur = set.lower(cur);  // b
    cur = set.lower(cur);  // a
    cur = set.lower(cur);  // null

When you need unique values you should try to switch to a Set. You can use a TreeSet together with a Comparator instance to sort the entries. The descendingSet() method of TreeSet will give you the reverse order. If you really need a ListIterator at some point you could create a temporary list from the set.

This is a problem with no easy answers.

The problem is that you have broken the contract for add(int, E). This method must either add the element or throw an exception - it is not allowed to return without adding the element.

If you override set(int, E) so that sometimes it doesn't set the element, it would break the contract for that method too, and it would prevent Collections.sort() from working as you identified.

I would not recommend breaking these contracts - it may cause other methods that act on lists to behave in unpredictable ways.

Others have experienced these difficulties - see the java docs for SetUniqueList for example.

Another problem with your implementation is that it would be extremely slow because ArrayList.contains() is a linear search.

One solution would be to write a class that uses both an ArrayList and a HashSet, and write your own versions of add and set, rather than breaking the contracts for the usual versions. This is not tested, but you get the idea.

public final class MyList<E extends Comparable<? super E>> extends AbstractList<E> {

    private final List<E> list = new ArrayList<>();
    private final Set<E> set = new HashSet<>();

    public E get(int i) {
        return list.get(i);
    }

    public int size() {
        return list.size();
    } 

    public boolean tryAdd(E e) {
        return set.add(e) && list.add(e);
    }

    public boolean tryAdd(int i, E e) {
        if (set.add(e)) {
            list.add(i, e);
            return true;
        }
        return false;
    }

    public boolean trySet(int i, E e) {
        return set.add(e) && set.remove(list.set(i, e));
    }

    public boolean remove(Object o) {
        return set.remove(o) && list.remove(o);
    }

    public void sort() {
        Collections.sort(list);
    }

    // One bonus of this approach is that contains() is now O(1)
    public boolean contains(Object o) {
        return set.contains(o);
    }

    // rest omitted.
}

Something like this would not break the contract for List. Note that with this version, add and set throw an UnsupportedOperationException, because this is the behaviour inherited from AbstractList. You would be able to sort by calling myList.sort(). Also, the listIterator method would work, but you would not be able to use it to set or add (although remove would work).

If you needed to add or set elements while iterating over this List, you would need to use an explicit index, rather than a ListIterator. Personally, I do not consider this a major problem. ListIterator is necessary for lists like LinkedList that do not have a constant time get method, but for ArrayList it's nice but not essential.