import java.util.Iterator;
import java.util.NoSuchElementException;

/**
 * A linked list of integers.
 */
public class LinkedList implements Iterable<Integer> {

    // Main method - used for testing purposes
    public static void main(String[] args) {
        LinkedList list = new LinkedList();

        LinkedList list2 = new LinkedList();

        for (int i = 0; i < 10; i++) {
            int randInt = (int) (Math.random() * 100);
            list.add(randInt);

            list2.add(randInt);

            list.add(2);
            list2.add(2);
        }

        list.add(5);

        list.printList();

        System.out.println(list.countOccurrences(2));
        System.out.println(list.getIndex(5));

        System.out.println(list.equals(list2));
    }

    // Node objects store the list's elements
    private class Node {

        int element; // element stored in this node
        Node next; // link to next node in the list (or null)
    }

    private Node head; // Reference to first node in the list
    private Node tail; // Reference to last node in the list
    private int size; // Number of elements stored in the list

    /**
     * Default constructor - creates an empty list
     */
    public LinkedList() {
        head = tail = null;
        size = 0;
    }

    // Prints the whole list (driver method)
    public void printList() {
        printList(head);
        System.out.println();
    }

    // Print list starting at walker (worker method)
    private void printList(Node walker) {
        if (walker != null) {
            System.out.print(walker.element + " "); // print current element
            printList(walker.next); // print rest of list
        }
    }

    /**
     * Returns the size of this list.
     * @return size of list
     */
    public int size() {
        return size;
    }

    /**
     * Adds the given element to the end of the list.
     * @param element element to add
     */
    public void add(int element) {
        Node n = new Node();
        n.element = element;
        if (size == 0) {
            head = tail = n;
        } else {
            tail.next = n;
            tail = n;
        }
        size++;
    }

    /**
     * Removes the first occurrence of the given element from the list.
     * @param element element to remove
     * @throws NoSuchElementException if given element not in the list
     */
    public void remove(int element) {
        Node walker = head;
        Node follower = null;
        while (walker != null && walker.element != element) {
            follower = walker;
            walker = walker.next;
        }
        if (walker == null) {
            throw new NoSuchElementException();
        } else if (walker == head) {
            head = head.next;
            if (head == null) tail = null;
        } else if (walker == tail) {
            follower.next = null;
            tail = follower;
        } else {
            follower.next = walker.next;
        }
        size--;
    }

    /**
     * Returns the element in the list at the given index.
     * @param index index of element
     * @return element at given index
     * @throws IndexOutOfBoundsException if index invalid
     */
    public int get(int index) {
        if (index < 0 || index >= size) throw new IndexOutOfBoundsException(
            index + ""
        );
        Node walker = head;
        for (int i = 0; i < index; i++) walker = walker.next;
        return walker.element;
    }

    @Override
    /**
     * Returns an iterator object for this list.
     * @return iterator object
     */
    public Iterator<Integer> iterator() {
        return new LinkedListIterator();
    }

    // This inner class defines the iterator object
    // for this list.
    private class LinkedListIterator implements Iterator<Integer> {

        private Node walker; // Link to "next" node

        // Constructor - creates an iterator object that
        // starts at the head of the list.
        public LinkedListIterator() {
            walker = head;
        }

        @Override
        // Returns true if the iterator has not reached the
        // end of the list.
        public boolean hasNext() {
            return walker != null;
        }

        @Override
        // Returns the "next" element in the list and advances
        // the walker.
        public Integer next() {
            if (hasNext()) {
                Integer elem = walker.element;
                walker = walker.next;
                return elem;
            } else {
                throw new NoSuchElementException();
            }
        }
    }

    public int countOccurrences(int element) {
        return countOccurrences(element, head, 0);
    }

    private int countOccurrences(int element, Node walker, int count) {
        if (walker == null) return count;

        if (walker.element == element) count++;

        return countOccurrences(element, walker.next, count);
    }

    public int getIndex(int element) {
        return getIndex(element, head, 0);
    }

    private int getIndex(int element, Node walker, int index) {
        if (walker == null) return -1;
        else if (walker.element == element) return index;

        index++;

        return getIndex(element, walker.next, index);
    }

    public boolean equals(Object other) {
        if (other instanceof LinkedList) {
            LinkedList otherList = (LinkedList) other;
            if (size == otherList.size) return equals(head, otherList.head);
            else return false;
        } else return false;
    }

    private boolean equals(Node walkerA, Node walkerB) {
        if (walkerA == null || walkerB == null) return true;

        if (walkerA.element != walkerB.element) return false;

        return equals(walkerA.next, walkerB.next);
    }

    public LinkedList cloneList() {
        return cloneList(head, new LinkedList());
    }

    private LinkedList cloneList(Node walker, LinkedList newList) {
        if (walker == null) return newList;
        newList.add(walker.element);
        return cloneList(walker.next, newList);
    }
}