public class DoublyLinkedList<E> implements Iterable<E>, Cloneable {

// instance variables of the DoublyLinkedList
    private final Node<E> header;     // header sentinel
    private final Node<E> trailer;    // trailer sentinel
    private int size = 0;       // number of elements in the list
    private int modCount = 0;   // number of modifications to the list (adds or removes)

    /**
     * Creates both elements which act as sentinels
     */
    public DoublyLinkedList() {

        header = new Node<>(null, null, null);      // create header
        trailer = new Node<>(null, header, null);   // trailer is preceded by header
        header.setNext(trailer);                    // header is followed by trailer
    }

    /**
     * Returns the number of elements in the linked list
     *
     * @return the number of elements in the linked list
     */
    public int size() {
        return size;
    }

    /**
     * Checks if the list is empty
     *
     * @return true if the list is empty, and false otherwise
     */
    public boolean isEmpty() {
        return size == 0;
    }

    /**
     * Returns (but does not remove) the first element in the list
     *
     * @return the first element of the list
     */
    public E first() {
        return header.getNext().getElement();
    }

    /**
     * Returns (but does not remove) the last element in the list
     *
     * @return the last element of the list
     */
    public E last() {
        return trailer.getPrev().getElement();
    }

// public update methods
    /**
     * Adds an element e to the front of the list
     *
     * @param e element to be added to the front of the list
     */
    public void addFirst(E e) {
        addBetween(e, header, header.getNext());
    }

    /**
     * Adds an element e to the end of the list
     *
     * @param e element to be added to the end of the list
     */
    public void addLast(E e) {
        addBetween(e, trailer.getPrev(), trailer);
    }

    /**
     * Removes and returns the first element of the list
     *
     * @return the first element of the list
     */
    public E removeFirst() {
        if (header.getNext() == trailer) {
            return null;
        }
        return remove(header.getNext());
    }

    /**
     * Removes and returns the last element of the list
     *
     * @return the last element of the list
     */
    public E removeLast() {
        if (trailer.getPrev() == header) {
            return null;
        }
        return remove(trailer.getPrev());
    }

// private update methods
    /**
     * Adds an element e to the linked list between the two given nodes.
     */
    private void addBetween(E e, Node<E> predecessor, Node<E> successor) {
        Node<E> nova = new Node<>(e, predecessor, successor);
        predecessor.setNext(nova);
        successor.setPrev(nova);
        size++;
        modCount++;
    }

    /**
     * Removes a given node from the list and returns its content.
     */
    private E remove(Node<E> node) {
        Node<E> previous = node.getPrev();
        Node<E> successor = node.getNext();
        previous.setNext(successor);
        successor.setPrev(previous);
        size--;
        modCount++;
        return node.getElement();
    }

// Overriden methods
    @Override
    public boolean equals(Object obj) {
        if (getClass() != obj.getClass()) {
            return false;
        }
        DoublyLinkedList dllist = (DoublyLinkedList) obj;

        if (this.size() != dllist.size()) {
            return false;
        }

        DoublyLinkedListIterator t = (DoublyLinkedListIterator) listIterator();
        DoublyLinkedListIterator n = (DoublyLinkedListIterator) dllist.listIterator();

        while (t.hasNext() && n.hasNext()) {
            if (!t.next().equals(n.next())) {
                return false;
            }
        }

        return true;
    }

    @Override
    public Object clone() throws CloneNotSupportedException {
        DoublyLinkedList clone = new DoublyLinkedList();

        DoublyLinkedListIterator it1 = (DoublyLinkedListIterator) this.listIterator();
        DoublyLinkedListIterator it2 = (DoublyLinkedListIterator) clone.listIterator();

        while (it1.hasNext()) {
            it2.add(it1.next());
        }

        return clone;
    }

//---------------- nested DoublyLinkedListIterator class ----------------
    private class DoublyLinkedListIterator implements ListIterator<E> {

        private DoublyLinkedList.Node<E> nextNode, prevNode, lastReturnedNode; // node that will be returned using next and prev respectively
        private int nextIndex;  // Index of the next element
        private int expectedModCount;  // Expected number of modifications = modCount;

        public DoublyLinkedListIterator() {
            this.prevNode = header;
            this.nextNode = header.getNext();
            lastReturnedNode = null;
            nextIndex = 0;
            expectedModCount = modCount;
        }

        final void checkForComodification() {  // invalidate iterator on list modification outside the iterator
            if (modCount != expectedModCount) {
                throw new ConcurrentModificationException();
            }
        }

        @Override
        public boolean hasNext() {
            checkForComodification();
            return nextNode != trailer;
        }

        @Override
        public E next() throws NoSuchElementException {
            checkForComodification();

            if (hasNext()) {
                this.prevNode = prevNode.getNext();
                this.nextNode = nextNode.getNext();
                nextIndex++;

                lastReturnedNode = prevNode;
                return prevNode.getElement();
            }
            throw new NoSuchElementException("End of list reached.");
        }

        @Override
        public boolean hasPrevious() {
            checkForComodification();
            return prevNode != header;
        }

        @Override
        public E previous() throws NoSuchElementException {
            checkForComodification();

            if (hasPrevious()) {
                this.prevNode = prevNode.getPrev();
                this.nextNode = nextNode.getPrev();
                nextIndex--;

                lastReturnedNode = nextNode;
                return nextNode.getElement();
            }
            throw new NoSuchElementException("End of list reached.");
        }

        @Override
        public int nextIndex() {
            checkForComodification();
            return nextIndex;
        }

        @Override
        public int previousIndex() {
            checkForComodification();
            return nextIndex - 1;
        }

        @Override
        public void remove() throws NoSuchElementException {
            checkForComodification();
            if (lastReturnedNode != null) {
                expectedModCount++;
                DoublyLinkedList.this.remove(lastReturnedNode);
                lastReturnedNode = null;
                return;
            }
            throw new NoSuchElementException();
        }

        @Override
        public void set(E e) throws NoSuchElementException {
            checkForComodification();
            if (lastReturnedNode == null) {
                throw new NoSuchElementException();
            }

            lastReturnedNode.setElement(e);
        }

        @Override
        public void add(E e) {
            checkForComodification();

            DoublyLinkedList.this.addBetween(e, prevNode, nextNode);
            nextNode = prevNode.getNext();
            expectedModCount++;
            next();
        }

    }    //----------- end of inner DoublyLinkedListIterator class ----------

//---------------- Iterable implementation ----------------
    @Override
    public Iterator<E> iterator() {
        return new DoublyLinkedListIterator();
    }

    public ListIterator<E> listIterator() {
        return new DoublyLinkedListIterator();
    }

//---------------- nested Node class ----------------
    private static class Node<E> {

        private E element;      // reference to the element stored at this node
        private Node<E> prev;   // reference to the previous node in the list
        private Node<E> next;   // reference to the subsequent node in the list

        public Node(E element, Node<E> prev, Node<E> next) {
            this.element = element;
            this.prev = prev;
            this.next = next;
        }

        public E getElement() {
            return element;
        }

        public Node<E> getPrev() {
            return prev;
        }

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

        public void setElement(E element) { // Not on the original interface. Added due to list iterator implementation
            this.element = element;
        }

        public void setPrev(Node<E> prev) {
            this.prev = prev;
        }

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