class Solution {
      public static class Node
      {
        // Each node object has these three variables
        private Object element;
        private Node   next;
        private Node   previous;

        // Constructor: Creates a Node object with element = e, next = n and previous = p
        Node(Object e, Node n, Node p)
        {
          element = e;
          next    = n;
          previous = p;
        }

        // This function gets Object e as input and sets e as the element of the Node
        public void setElement(Object e)
        {
          element = e;
        }

        // This function returns the element variable of the Node
        public Object getElement()
        {
          return element;
        }

        // This function gets Node n as input and sets the next variable of the current Node object as n.
        public void setNext(Node n)
        {
          next = n;
        }

        // This function returns the next Node
        public Node getNext()
        {
          return next;
        }

        // This function gets Node n as input and sets the previous variable of the current Node object as p.
        public void setPrevious(Node p)
        {
          previous = p;
        }

        // This function returns the previous Node
        public Node getPrevious()
        {
          return previous;
        }

      }

      public static class DLList
      {

        // Each object in DLList has one variable head, which points to the starting Node of DLList.
        private Node head;
        private Node tail;

        // Implemens an empty constructor which initialises the head variable as null
        DLList()
        {
          head = null;
          tail = null;
        }

        // Returns the head node of the DLL
        public Node getHead()
        {
          return head;
        }



        // Returns the tail node of the DLL
        public Node getTail()
        {
            return tail;
        }

        // Following methods are the ones you are expected to implement

        // Adds node n to the head of the list.
        public void addFirst(Node n)
        {
          if(n != null) {
            Node otherNode = head;
            head = n;
            if (otherNode == null) tail = n;
            else {
              otherNode.setPrevious(n);
              n.setNext(otherNode);
          }
          }
        }

        //Removes and returns the first node in the list. If the list is empty, returns null.
        public Node removeFirst()
        {
          Node otherNode;
          if (tail == null && head == null) otherNode = null;
          else {
            otherNode = head;
            head.getNext().setPrevious(null);
            head = head.getNext();
          }
          return otherNode;
        }

        // Adds node n to the end of the list
        public void addLast(Node n)
        {
          if (n != null) {
          Node otherNode = tail;
            tail = n;
            if (otherNode == null) head = n;
            else {
              otherNode.setNext(n);
              n.setPrevious(otherNode);
            }
          }
        }

        //Removes and returns the last node in the list.If the list is empty, returns null.
        public Node removeLast() {
          Node otherNode;
          if (tail == null && head == null) otherNode = null;
          else {
            otherNode = tail;
            tail.getPrevious().setNext(null);
            tail = tail.getPrevious();
          }
          return otherNode;
        }

        // Returns the number of nodes in the list
        public int size()
        {
          int size = 0;
          if (head == null && tail == null) return size;
          else {
            for (Node temp = head; temp != null; temp = temp.getNext()) {
              size++;
            }
          }
          return size;
        }

        // Adds node n after the node in position pos. The list is zero indexed, so the first element in the list correspond
        // to position 0. If there is no node in position pos, this method adds it to the last position.
        public void addAtPosition(Node n, int pos)
        {
          if (n != null) {
          if (pos < size() - 1) {
              if (pos == -1) {
                addFirst(n);
              } else {
                n.setNext(null);
                Node current = head;
                Node previous = null;
                for (int i = 0; i <= pos; i++) {
                  previous = current;
                  current = current.getNext();
                }

                n.setNext(previous.getNext());
                previous.setNext(n);
            }
            } else {
               addLast(n);
            }
          }
        }

        // Remove and return node n at position pos. The list is zero indexed, so the first element in the list correspond
        // to position 0. If there is no node in position pos, this method returns null.
        public Node removeFromPosition(int pos)
        {
          if (head == null && tail == null) {
              return null;
          }
          if (pos < size()) {
            if (pos == 0) {
              return removeFirst();
            } else if (pos == size()-1) {
              return removeLast();
            } else {
                Node temp = head;
              for (int i = 0; i < pos-1; i++) {
                  temp = temp.getNext();
              }
              Node next = temp.getNext().getNext();
              Node result = temp.getNext();
              temp.setNext(next);
              return result;
           }
          }
          return null;
        }

        // Returns  a new DLL that contains the elements of the current one in reversed order
        public DLList reverse()
        {
          DLList list = new DLList();

          if (head != null && tail != null) {
            Node temp = tail;
            while (temp != null) {
              Node newNode = new Node(temp.getElement(), null, null);
              list.addLast(newNode);
              temp = temp.getPrevious();
            }
          }
          return list;
        }
      }
}//