Java combination with Set and List interfaces

Question

I have a data structure for which I am currently using an ArrayList . I realized that in this structure I do not want any duplicates to be present. My first thought was to use some form of dialing, however order is also important. After doing a little searching and searching in Collections LinkedHashSet , I found a LinkedHashSet that almost does the job. Unfortunately, one of the main reasons for maintaining order is that I use the get(int index) method of ArrayList for random access, and I see no way around this.

More concise - I need a set that keeps order and allows random access. None of the classes that I have yet to examine provide this functionality. Does anyone know a class that offers this, or should I do it myself? If this is the last case, are there any pitfalls in creating such a structure that people know about?

(Alternatively, a quick and easy way to check and remove duplicates from an ArrayList or similar structure will suffice)

EDIT: for clarity, this is the order in which items are added to the list, which is important, not how they are compared to each other.

Answer 1

I would just stretch an 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 matches the contract :

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

Answer 2

SetUniqueList from the collection collections:

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

(unfortunately, collective domains still do not support generics, so you have to suppress the warning here)

Answer 3

Regarding creating a subclass of AbstractList that stores the ArrayList as its backup storage, overrides most methods for delegating them to the backup storage 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); } } 

Answer 4

You can use ArrayList and 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();} }