Java combination of Set and List interfaces

I have a data structure, for which I am currently using an ArrayList. I realised that in this structure I do not want any duplicates to be present. My first thought was to use some form of set, however the order is also important. After a bit of googling and searching the Collections docs I found LinkedHashSet which almost does the job. Unfortunately, one of the primary reasons for preserving order is because I am using the get(int index)开发者_如何转开发 method of the ArrayList for random access, and I can't see any way around this.

More concisely - I need a set that preserves order and allows random access. None of the classes I have so far looked at provide this functionality. Does anyone know of a class that offers this, or will I have to make it myself? If it is the latter case are there any pitfalls when creating such a structure that people are aware of?

(Alternatively, a quick and easy way of checking for and removing duplicates form an ArrayList or similar structure would suffice)

EDIT: for clarity, it is the order that elements are added to the list that is important, not how they compare to one another

---

SetUniqueList from commons-collections:

List<Foo> uniqueList = SetUniqueList.decorate(new ArrayList<Foo>());

(unfortunately, commons-collections still doesn't support generics, so you'll have to suppress a warning here)

---

I'd just extend ArrayList.

public class SetList<E> extends ArrayList<E> {

    @Override
    public boolean add(E e) {
        return contains(e) ? false : super.add(e);
    }

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

    @Override
    public boolean addAll(Collection<? extends E> c) {
        return addAll(size(), c);
    }

    @Override
    public boolean addAll(int index, Collection<? extends E> c) {
        Collection<E> copy = new ArrayList<E>(c);
        copy.removeAll(this);
        return super.addAll(index, copy);
    }

}

Note that the add() method conforms the contract:

Ensures that this collection contains the specified element (optional operation). Returns true if this collection changed as a result of the call. (Returns false if this collection does not permit duplicates and already contains the specified element.)

---

What about creating a subclass of AbstractList that keeps an ArrayList as its backing store, overrides most methods to delegate them to the backing store, and overrides add() to reject duplicates?

class NoDupesList<E> extends AbstractList<E> {
    private final List<E> backing;

    NoDupesList() {
        backing = new ArrayList<E>();
    }

    public E get(int index) {
        return backing.get(index);
    }

    // ...

    public boolean contains(Object o) {
        return backing.contains(o);
    }

    public boolean add(E e) {
        if (contains(e))
            throw new IllegalArgumentException("duplicates disallowed: " + e):

        return backing.add(e);
    }
 }

---

You can use an ArrayList and a HashMap together:

import java.util.*;

class AS<T>{

    private HashMap<T, Integer> m = new HashMap<T, Integer>();
    private ArrayList<T> a = new ArrayList<T>();

    public void add(T object){
        if (!m.containsKey(object)){
            m.put(object, a.size());
            a.add(object);
        }
    }
    public void remove(T object){
        Integer i = m.get(object);
        if (i!=null){
            a.remove(i.intValue());
            m.remove(object);
        }
    }
    public void remove(int index){
        m.remove(a.get(index));
        a.remove(index);
    }
    public T get(int index){
        return a.get(index);
    }

    public String toString(){return a.toString();}
}