public class List<T>
{
    private Node<T> first;
    private int length; 
    private Node<T> last;
    /** 
     * Konstruktor, legt leere Liste an
     */
    public List(){
        this.first = null;
        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(){
        Node<T> current = this.first;
        int count= 0;
        while(current != null){
            current = current.next;
            count++;
        }

        return length;
    }

    public 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){
        Node<T> added = new Node<T>(val);       
        Node<T> current = this.first;
        if (this.first == null){
            this.first = added;
            this.last = added;
        }
        else{
            this.last.next = added;
            this.last = added;
        }
        this.length++;
    }

    public void add (int n, T val){
        Node<T> added = new Node<T>(val);
        if(this.getNode(n-1) == null)this.add(val);
        added.next = this.getNode(n-1).next;
        this.getNode(n-1).next = added;
        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 T remove(int n){
        if (this.length <= n ) return null;
        if ( n == 0) {
            T ret = this.first.wert;
            this.first = this.first.next;
            this.length--;
            return ret;
        }
        T ret = getNode(n).wert;
        if (getNode(n-1).next.next == null) this.last = getNode(n-1);
        getNode(n-1).next = getNode(n-1).next.next;
        length--;
        return ret;
    }
}