public class LList<T>
{
    private Node<T> firstNode;
    private Node<T> lastNode;
    private int length;

    public LList()
    {
        this.clear();
    }

    public final void clear()
    {
        this.firstNode = null;
        this.lastNode = null;
        this.length = 0;
    }

    public int size()
    {
        return  this.length;
    }

    public boolean isEmpty()
    {
        return  this.length == 0;
    }

    public String toString()
    {

        if (this.length==0) return "[]";  //exit!

        String r =  "[";

        Node<T> curr = this.firstNode;

        for (int i=0; i<=this.length-2; i++)
        {
            r = r + curr.data.toString() + ", ";
            curr = curr.next;
        }

        r = r + curr.data.toString() + "]";

        return r;
    }

    public void display()
    {
        Node<T> curr = this.firstNode;
        while (curr != null)
        {
            System.out.println("*" + curr.data);
            curr = curr.next;
        }
    }

    private Node<T> getNodeAt(int position)   ///////a private "helper" function
    {

        //preconditions: list is not empty.  1 <= position <= this.length

        Node<T> curr = this.firstNode;
        for (int i=1; i<position; i++)
        {
            curr = curr.next;
        }
        return curr;
    }

    public T get(int idx)
    {
        if (idx < 1  ||  idx > this.length)
        {
            return null;
        }
        else
        {
            T result = this.getNodeAt(idx).data;
            return result;

            //can combine these 2 lines into 1 line, like this:
            //return  this.getNodeAt(idx).data;
        }
    }

    public void set(int idx, T a)
    {
        if (idx < 1 || idx > this.length)
        {
            System.out.println("Illegal index, ignoring");
        }
        else
        {
            Node<T> desiredNode = this.getNodeAt(idx);
            desiredNode.data = a;
            //can combine these 2 lines into 1 line
        }
    }

    public boolean contains(T a)
    {
        Node<T> curr = this.firstNode;
        while (curr != null)
        {
            if (a.equals(curr.data)) {return true;}  //exit!
            curr = curr.next;
        }
        return false;
    }

    public void add(T a)   //add to back
    {
        Node<T> newlast = new Node<T>(a);

        if (this.isEmpty())
        { this.firstNode = newlast; }
        else
        { this.lastNode.next = newlast; }

        this.lastNode = newlast;
        this.length++;
    }

    public void add(int idx, T a)   //insert
    {

        if (idx < 1  ||  idx > this.length+1)
        {
            System.out.println("Illegal index, ignoring");
            return;  //exit!
        }

        Node<T> nn = new Node<T>(a);
        if (this.isEmpty())
        {
            this.firstNode = nn;
            this.lastNode = nn;
        }
        else if (idx == 1)
        {
            nn.next = this.firstNode;
            this.firstNode = nn;
        }
        else if (idx == this.length+1)
        {
            this.lastNode.next = nn;
            this.lastNode = nn;
        }
        else
        {
            Node<T> nodeBefore = this.getNodeAt(idx-1);
            Node<T> nodeAfter = nodeBefore.next;
            nn.next = nodeAfter;
            nodeBefore.next = nn;
        }

        this.length++;

    } //add, insert

    public T remove(int idx)
    {

        if (idx < 1  ||  idx > this.length)
        {
            return null;  //exit!
        }

        T result;
        if (idx == 1)
        {
            result = this.firstNode.data;
            this.firstNode = this.firstNode.next;
            if (this.length==1) this.lastNode=null;
        }
        else
        {
            Node<T> nodeBefore = this.getNodeAt(idx-1);
            Node<T> nodeToRemove = nodeBefore.next;
            Node<T> nodeAfter = nodeToRemove.next;
            result = nodeToRemove.data;
            nodeBefore.next = nodeAfter;
            if (idx==this.length) this.lastNode=nodeBefore;
        }
        this.length--;
        return result;
    }

    public void insertAtSorted(T x)
    {
        Node<T> nn = new Node<T>(x);
        T check = this.getNodeAt(this.length/2).data;
        if (check.equals(x))
        {
            this.add(this.length/2, x);
        }
        else if(check.compareTo(x) < -1)
        {
        }
        else
        {

        }
    }
}