List with fast contains

Question

I wonder if there's a List implementation allowing fast contains. I'm working with quite a long List and I can't switch to Set since I need the access by index. I can ignore the performance, which may be acceptable now and may or may not be acceptable in the future. I can create a HashSet and do all modifying operations on both, but doing it manually is quite boring and error prone.

I know that it's impossible to have a class working like both List and Set (because of the different equals semantics), but I wonder if there's List implementing RandomAccess and employing an HashSet for speeding up contains.

Answer 1

I know that it's impossible to have a class working like both List and Set

Have you tried LinkedHashSet? Technically it's a set but it preserves order which might be just enough for you. However access by index is linear and not built-in.

Other approach would be to wrap List with a custom decorator that both delegates to List and maintains a n internalSet for faster contains.

Answer 2

you can wrap a list and hashSet that combines best of both worlds

public class FastContainsList<T> extends AbstractSequentialList<T> implements RandomAccess{
//extending sequential because it bases itself of the ListIterator(int) and size() implementation

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


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

    public boolean contains(Object o){//what it's about
        return set.contains(o);
    }

    public ListIterator<T> listIterator(int i){
        return new ConIterator(list.listIterator(i));
    }

    /*for iterator()*/
    private ConIterator implements ListIterator<T>{

        T obj;
        ListIterator<T> it;

        private ConIterator(ListIterator<T> it){
        this.it = it
        }

        public T next(){
        return obj=it.next();
        }

        public T previous(){
        return obj=it.previous();
        }

        public void remove(){
        it.remove();//remove from both
        set.remove(obj);
        }

        public void set(T t){
            it.set(t);
            set.remove(obj);
            set.add(obj=t);
        }

         public void add(T t){
             it.add(t);
             set.add(t);
         }

        //hasNext and hasPrevious + indexes still to be forwarded to it
    }

}