set data structure implementation in java

Set refers an abstract data structure used for storing data elements. Analogy with the mathematical term set, it does not guarantee any particular order of the stored elements and contains every value at most once (i.e. contains only unique values).

Similarly we can define multiset (bag) – a set, which may contain each value more than once. we can implement disjoint,union and difference of these set like in set theory of mathematics.

Source Code(JAVA)

/**
 * Set implemented as a list (using ArrayList)
 * @author Pavel Micka
 * @param <ENTITY> Type parameter of the contained value
 */
public class Set<ENTITY> {
    private List<ENTITY> list;
    /**
     * Constructor
     * @param initialCapacity initial capacity of the underlying ArrayList
     */
    public Set(int initialCapacity){
        list = new ArrayList<ENTITY>(initialCapacity);
    }

    /**
     * Inserts entity into the set
     * @param e entity
     * @return true - if was the insertion successful, false - if the set already contained this value
     */
    public boolean put(ENTITY e) {
        if (list.contains(e)) return false;
        list.add(e);
        return true;
    }

 /**
     * Return (and remove) some element from the set
     * @return element, null if the set is empty
     */
    public ENTITY pick() {
        if(list.size() == 0) return null;
        return list.remove(list.size() - 1);
    }

    /**
     * Remove given entity from the set
     * @param e entity
     * @return true - if the set contained the entity, false - otherwise
     */
    public boolean remove(ENTITY e) {
        return list.remove(e);
    }

    /**
     * Query if the set set contains given entity
     * @param e entity
     * @return true - if the set contains the entity, false - otherwise
     */
    public boolean contains(ENTITY e) {
        return list.contains(e);
    }
    /**
     * Size of the set
     * @return number of stored entities
     */
    public int size() {
        return list.size();
    }
}

Complexity 

Although this approach is easy to implement, it is very ineffective, because almost

every operation has to iterate over the underlying list (with  asymptotic 

complexity). For this reason is the list based implementation used only very rarely.

In practice set is usually implemented as a hash table  (guarantees on average  

 complexity of both operations put and contains).