import java.util.NoSuchElementException;

public class SimpleLinkedList<E> implements SimpleList<E> {

    private class Node {

        E element;
        Node next;
    }

    private Node head;
    private Node tail;
    private int size;

    @Override
    public void addFirst(E elem) {
        Node n = new Node();
        n.element = elem;
        if (head == null) {
            head = tail = n;
        } else {
            n.next = head;
            head = n;
        }

        size++;
    }

    @Override
    public E removeFirst() {
        if (head == null) {
            return null;
        }

        E element = head.element;
        head = head.next;

        if (head == null) {
            tail = null;
        }

        size--;
        return element;
    }

    @Override
    public E removeLast() {
        if (head == null) {
            throw new NoSuchElementException("Empty List");
        } else {
            E element = tail.element;
            if (size == 1) {
                head = tail = null;
            } else {
                Node walker = head;
                while (walker.next != tail) {
                    walker = walker.next;
                }

                walker.next = null;
                tail = walker;
            }

            size--;
            return element;
        }
    }

    @Override
    public void addLast(E elem) {
        Node n = new Node();
        n.element = elem;
        if (tail == null) {
            head = tail = n;
        } else {
            tail.next = n;
            tail = n;
        }

        size++;
    }
}