/**
 * Implementation of the LinkedListInterface
 * For all public methods, see documentation in LinkedListInterface
 * 
 * @author gtowell
 * Created: April 2021
 * @param <J>
 */
public class SingleLinkedList<J> implements LinkedListInterface<J> {
        
    protected class Node<H> 
    {
	    public H data;
	    public Node<H> next;
	    public Node(H data) 
	    {
            this.data = data;
            this.next = null;
	    }	
    }   

    protected Node<J> head = null;
    
    public int size() {
        int siz = 0;
        Node<J> n = head;
        while (n != null) {
            siz++;
            n = n.next;
        }
        return siz;
    }

    public boolean isEmpty() {
        return head == null;
    }

    @Override
    public J first() {
        return head.data;
    }

    private Node<J> lastNode() {
        Node<J> n = head;
        if (n == null)
            return null;
        while (n.next != null) {
            n = n.next;
        }
        return n;
    }

    @Override
    public J last() {
        Node<J> n = lastNode();
        if (n == null)
            return null;
        return n.data;
    }
    
    @Override
    public void addLast(J c) {
        Node<J> n = lastNode();
        Node<J> newnode = new Node<>(c);
        if (n == null) {
            head = newnode;
            return;
        }
        n.next = newnode;
    }

    @Override
    public void addFirst(J c) {
        Node<J> newnode = new Node<>(c);
        if (head == null) {
            head = newnode;
            return;
        }
        newnode.next = head;
        head = newnode;
    }

    @Override
    public J removeFirst() {
        if (head == null)
            return null;
        Node<J> tmp = head;
        head = head.next;
        return tmp.data;
    }

    @Override
    public J removeLast() {
        if (head == null)
            return null;
        Node<J> prev = head;
        Node<J> here = head.next;
        if (here == null) {
            // only one item in list
            head = null;
            return prev.data;
        }
        while (here.next != null) {
            prev = here;
            here = here.next;
        }
        prev.next = null;
        return here.data;
    }

    @Override
    public boolean remove(J r) {
        if (head == null)
            return false;
        Node<J> prev = null;
        Node<J> here = head;
        while (here.next != null) {
            if (here == r)
                break;
            prev = here;
            here = here.next;
        }
        if (here.data == r) {
            if (prev == null)
                head = head.next;
            else
                prev.next = here.next;
            return true;
        }
        return false;
    }

    public String toString() {
        StringBuffer sb = new StringBuffer();
        for (Node<J> node = head; node != null; node = node.next) {
            sb.append(node.data.toString());
            sb.append("\n");
        }
        return sb.toString();
    }
}