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

// Doubly Linked List
public class DLList<T> implements Iterable<T> {

    // Main method to test this class
    public static void main(String[] args) {
        // Add random numbers to a new list:
        DLList<Integer> aList = new DLList<Integer>();
        for (int i = 0; i < 20; i++) aList.add((int) (Math.random() * 100));

        // Print list using for-each loop:
        for (Integer i : aList) System.out.print(i + " ");
        System.out.println();

        // Print list using iterator methods:
        DLList<Integer>.DLListIterator iter = aList.iterator(20);
        while (iter.hasPrevious()) System.out.print(iter.previous() + " ");
        System.out.println();

        while (iter.hasNext()) System.out.print(iter.next() + " ");
        System.out.println();

        while (iter.hasPrevious()) System.out.print(iter.previous() + " ");
        System.out.println();
    }

    private class Node {

        T element;
        Node next;
        Node prev;

        public Node(T element) {
            this.element = element;
        }
    }

    // Linked List Iterator class
    private class DLListIterator implements Iterator<T> {

        private Node walker;

        private DLListIterator() {
            walker = head;
        }

        private DLListIterator(Integer index) {
            walker = head;

            for (int i = 0; i < index; i++) {
                next();
            }
        }

        @Override
        public boolean hasNext() {
            return walker != null;
        }

        public boolean hasPrevious() {
            return walker == null || walker.prev != null;
        }

        @Override
        public T next() {
            if (hasNext()) {
                T element = walker.element;
                walker = walker.next;
                return element;
            } else throw new NoSuchElementException();
        }

        public T previous() {
            if (hasPrevious()) {
                if (walker == null) {
                    walker = tail;
                } else {
                    walker = walker.prev;
                }

                T element = walker.element;

                return element;
            } else throw new NoSuchElementException();
        }
    }

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

    // Add to end of list
    public void add(T element) {
        add(size, element);
    }

    // Add to list at given index
    public void add(int index, T element) {
        if (index < 0 || index > size) throw new IndexOutOfBoundsException(
            "" + index
        );
        Node n = new Node(element);
        if (head == null) {
            // list empty
            head = tail = n;
        } else if (index == 0) {
            // add to head
            n.next = head;
            head.prev = n;
            head = n;
        } else if (index == size) {
            // add to tail
            n.prev = tail;
            tail.next = n;
            tail = n;
        } else {
            // general case
            Node walker = head;
            for (int i = 0; i < index - 1; i++) walker = walker.next;
            n.next = walker.next;
            n.prev = walker;
            walker.next = n;
            n.next.prev = n;
        }
        size++;
    }

    public int size() {
        return size;
    }

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

    @Override
    public Iterator<T> iterator() {
        return new DLListIterator();
    }

    public DLListIterator iterator(Integer i) {
        return new DLListIterator(i);
    }
}