import static lib.IO.*;

public class List {
    private Element head;
    
    /**
     * creates a new empty list
     */
    public List() {
        this.head = null;
    }
    
    /**
     * checks whether the list is empty
     * @return true iff the list is empty
     */
    public boolean isEmpty() {
        return head == null;
    }
    
    /**
     * computes the size of the list
     * @return the size of the list
     */
    public int size() {
        if (head == null) {
            return 0;
        } else {
            return head.size();
        }
    }
    
    /**
     * returns a string-representation of this list
     * @return a string representation of this list
     */
    public String toString() {
        return this.toString(false);
    }
    
    /**
     * returns a string-representation of this list
     * @param reverse if set to true then the elements are listed in reversed order
     * @return a string representation of this list
     */
    public String toString(boolean reverse) {
        String result = "(";
        if (head != null) 
            result += head.toString(reverse);        
        return result + ")";
    }
    
    
    /**
     * checks whether some data is contained in the list
     * @param data the data that has to be checked 
     * @return true iff the data is contained in the list
     */
    public boolean contains(int data) {
        return head != null && head.contains(data);
    }
    
    /**
     * inserts some data into the list
     * @param data the data to be inserted
     */
    public void insert(int data) {
        head = new Element(data, head);
    }
        
    /**
     * removes some data from the list. if the data is not contained in the list then nothing happens. if it occurs
     * multiple times in the list then only one occurrence is deleted.
     * @param data the data to be removed
     */
    public void remove(int data) {
        if (head != null) {
            head = head.remove(data);
        }
    }
    
    /**
     * inserts some data into the list. moreover, if the list was sorted before then 
     * it will be sorted afterwards, too.
     * @param data the data to be inserted
     */
    public void insertSorted(int data) {
        head = insertSorted(data, head);
    }
    
    private static Element insertSorted(int data, Element e) {
        if (e == null) {
            return new Element(data, null);
        } else if (data < e.getData()) {
            return new Element(data, e);
        } else {
            e.setNext(insertSorted(data, e.getNext()));
            return e;
        }
    }

    /**
     * removes all elements from the list
     */
    public void removeAll() {
        head = null;
    }
    
    /**
     * removes the first element of a list and returns it. 
     * this method should only be called on non-empty lists 
     * @return the first element of the list
     */
    public int removeHead() {
        int res;
        if (head == null) {
            println("error, list is empty");
            res = (int)Math.random();
        } else {
            res = head.getData();
            head = head.getNext();
        }
        return res;
    }
            
}