import java.util.NoSuchElementException;

/**
 * An implementation of the Linked List data structure.
 *
 * The LinkedList is like the ArrayList, except the list's
 * elements are stored in linked nodes instead of an array.
 *
 * @param <E> component type
 */
public class DoublyLinkedList<E> {

    public static void main(String[] args) {
        DoublyLinkedList<Integer> list = new DoublyLinkedList<>();
        for (int i = 2; i <= 20; i += 2) list.add(i);

        System.out.println(list);

        list.removeFirst();

        list.removeLast();

        list.printReverse();
    }

    // The list's elements are stored in nodes.
    private class Node {

        E element; // Element stored in this node
        Node next; // Link to the next node in the list
        Node previous; // Link to the previous node in the list
    }

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

    public void add(E elem) {
        Node n = new Node();
        n.element = elem;
        if (head == null) head = tail = n;
        else {
            n.previous = tail;
            tail.next = n;
            tail = n;
        }
        size++;
    }

    public void add(int index, E elem) {
        if (index < 0 || index > size) throw new IndexOutOfBoundsException(
            index + ""
        );

        Node n = new Node();
        n.element = elem;

        if (index == 0) {
            n.next = head;
            head = n;
            if (tail == null) tail = n;
        } else {
            Node walker = head;
            for (int i = 0; i < index - 1; i++) {
                walker = walker.next;
            }

            n.next = walker.next;
            walker.next = n;

            if (n.next == null) tail = n;
        }

        size++;
    }

    public E 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;
    }

    public void set(int index, E element) {
        if (index < 0 || index >= size) throw new IndexOutOfBoundsException(
            index + ""
        );
        Node walker = head;
        for (int i = 0; i < index; i++) walker = walker.next;

        walker.element = element;
    }

    public E get(E element) {
        Node walker = head;
        for (int i = 0; i < size; i++) {
            if (walker.element.equals(element)) {
                return walker.element;
            }

            walker = walker.next;
        }

        return null;
    }

    public boolean contains(E element) {
        Node walker = head;
        for (int i = 0; i < size; i++) {
            if (walker.element.equals(element)) {
                return true;
            }

            walker = walker.next;
        }

        return false;
    }

    public int size() {
        return size;
    }

    public void removeFirst() {
        if (size == 0) throw new NoSuchElementException();

        if (size == 1) {
            head = tail = null;
        } else {
            head = head.next;
            head.previous = null;
        }

        size--;
    }

    public void removeLast() {
        if (size == 0) throw new NoSuchElementException();

        if (size == 1) {
            head = tail = null;
        } else {
            tail = tail.previous;
            tail.next = null;
        }

        size--;
    }

    public void printReverse() {
        Node walker = tail;
        while (walker != null) {
            System.out.println(walker.element);

            walker = walker.previous;
        }
    }

    @Override
    public String toString() {
        if (head == null) return "[]";
        else {
            String s = "[";
            Node walker = head;
            while (walker != tail) {
                s += walker.element + ", ";
                walker = walker.next;
            }
            s += tail.element + "]";
            return s;
        }
    }
}