public class SinglyLinkedList<E> {

    // Nested Node class
    private static class Node<E> {

        private E element;
        private Node<E> next;

        public Node(E e, Node<E> n) {
            element = e;
            next = n;
        }

        public E getElement() {
            return element;
        }

        public Node<E> getNext() {
            return next;
        }

        public void setNext(Node<E> n) {
            next = n;
        }
    }

    private Node<E> head = null;
    private Node<E> tail = null;
    private int size = 0;

    public SinglyLinkedList() {
    }
    
    public int size() {
        return size;
    }

    public boolean isEmpty() {
        return size == 0;
    }

    public E first() {

        if (isEmpty())
            return null;

        return head.getElement();
    }

    public E last() {

        if (isEmpty())
            return null;

        return tail.getElement();
    }

    public void addFirst(E e) {

        Node<E> newest = new Node<>(e, head);

        head = newest;

        if (size == 0)
            tail = head;

        size++;
    }

    public void addLast(E e) {

        Node<E> newest = new Node<>(e, null);

        if (isEmpty())
            head = newest;
        else
            tail.setNext(newest);

        tail = newest;
        size++;
    }

    public E removeFirst() {

        if (isEmpty())
            return null;

        E answer = head.getElement();

        head = head.getNext();
        size--;

        if (size == 0)
            tail = null;

        return answer;
    }

    public void forwardTraversal(){
        Node<E> current = head;
        while(current != null){
            System.out.print(current.getElement());
            if(current.getNext() != null){
                System.out.print(" -> ");
            }
            current = current.getNext();
        }
    }

    public boolean contain(E value){
        Node<E> current = head;

        while(current != null){
            if (current.getElement().equals(value)) {
                return true;
            }
            current = current.getNext();
        }
        return false;
    }
    public static void main(String[] args) {
        System.out.println("||==========================================||");
        System.out.printf("|| %-40s ||%n","Student Name: Faisal Majed Alghamdi");
        System.out.printf("|| %-40s ||%n","Student Number: 447001625");
        System.out.println("||==========================================||\n");

        System.out.println("\n\nList1:");
        SinglyLinkedList<Integer> list1 = new SinglyLinkedList<>();

        list1.addFirst(100);
        list1.addFirst(200);
        list1.addFirst(300);
        list1.addFirst(400);

        list1.forwardTraversal();

        System.out.println("\n\nList2:");
        SinglyLinkedList<Integer> list2 = new SinglyLinkedList<>();

        list2.addLast(100);
        list2.addLast(200);
        list2.addLast(300);
        list2.addLast(400);
        
        list2.forwardTraversal();

        System.out.println("\n\nDoes list2 contain 300? " + list2.contain(300));
        System.out.println("Does list2 contain 500? " + list2.contain(500));


        System.out.println("\n\nList3:");
        SinglyLinkedList<String> list3 = new SinglyLinkedList<>();

        list3.addLast("ABC");
        list3.addLast("DEF");
        list3.addLast("GHI");
        list3.addLast("JKL");
        
        list3.forwardTraversal();

        System.out.println("\n\nDoes list3 contain ABC? " + list3.contain("ABC"));
    }
}