public class Set<T>
{
    private Node<T> first;
    private int length; 
    private Node<T> last;
    /** 
     * Konstruktor, legt leeres Set an
     */
    public Set(){
        this.first = null;
        this.length = 0;
        this.last= null;
    }
    
    /**
     * Gibt zurück, ob die Liste leer ist (true heißt leer)
     */
    public boolean isEmpty(){
        return this.first == null;
    }
    
    /**
     * Gibt die Länge der Liste zurück
     */
    public int size(){
        return this.length;
    }

    private T get (int n){
        Node<T> current = this.first;
        for ( int i = 0; i < n ; i++ ){
            if (current == null)return null;
            current = current.next;
        }
        if (current == null ) return null;
        return current.wert;
    }
    
    private Node<T> getNode (int n){
        Node<T> current = this.first;
        for ( int i = 0; i < n ; i++ ){
            if (current == null)return null;
            current = current.next;
        }
        if (current == null ) return null;
        return current;
    }
    
    public void add (T val){
        if (!this.contains(val)){
            Node<T> added = new Node<T>(val);
            if (this.first == null){
                this.first = added;
                this.last = added;
            }
            else{ 
            this.last.next = added;
            this.last = added;
            }
            this.length++;
        }
    }

    public boolean contains (T val){
        Node<T> current = this.first;
        
        while(current != null){
            if(current.wert == val) return true;
            current = current.next;
        }
        return false;
    }

    public void remove(T val){
        if(!this.contains(val))return;
        Node<T> current = this.first;
        if(this.first.wert == val){
            this.first = this.first.next;
        }
        while(current.next.wert != val){
            current = current.next;
        }
        current.next = current.next.next;
        this.length--;
    }
    
    public Set<T> intersection(Set<T> s){
        Set<T> tmp  = new Set<T>();
        Node<T> current = this.first;
        while(current != null){
            if (s.contains(current.wert)) tmp.add(current.wert);
            current=current.next;
        }
        return tmp;
    }
    
    public Set<T> unionUnoptimized(Set<T> s){
        Set<T> tmp = new Set<T>();
        for (int i = 0; i < s.size(); i++){
            tmp.add(s.get(i));
        }
        for (int i = 0; i < this.length; i++){
            if (!tmp.contains(this.get(i))) tmp.add(this.get(i));
        }
        return tmp;
    }
    
    public Set<T> union(Set<T> s){
        Set<T> tmp = new Set<T>();
        Node<T> current = s.first;
        while (current != null){
            tmp.add(current.wert);
            current = current.next;
        }
        current = this.first;
        while (current != null){
            tmp.add(current.wert);
            current = current.next;
        }
        return tmp;
    }
    
    public Set<T> difference(Set<T> s){
        Set<T> tmp = new Set<T>();
        Node <T> current = this.first; 
        while (current!=null){
            if(!s.contains(current.wert))tmp.add(current.wert);
            current = current.next;
        }
        return tmp;
    }
    
    public boolean subset(Set<T> s){
        Node <T> current = this.first;
        while (current != null){
            if (!s.contains(current.wert)) return false;
        }
        return true;
    }
    public String toString(){
        Node <T> current = this.first;
        String tmp = "";
        while (current != null){
            tmp = tmp + current.wert + ", ";
            current = current.next;
        }
        return tmp;
    }
}