class CDLList<T> {
  class Node {
    // Each Node object has these three fields
    private T element;
    private Node previous;
    private Node next;

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

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

    // This function returns the element variable of the Node
    public T 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 p 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;
    }
  }

  // Each object in CDLList has one field head, which points to the starting Node of CDLList.
  private Node head;

  /**
   * Constructor: initialises the head field as null
   */
  public CDLList() {
    head = null;
  }

  /**
   * @return The element in the first Node of this CDLL. If the list is empty, this method returns null.
   */
  public T getFirst() {
    // TODO
    return (head != null) ? head.getElement() : null;
  }

  /**
   * Adds element e in a new Node to the head of the list.
   *
   * @param e
   *     The element to add.
   */
  public void addFirst(T e) {
    // TODO
    if(head == null) {
      head = new Node(e, null, null);
    } else if(head.getNext() == null) {

      Node newNode = new Node(e, head, head);
      head.setPrevious(newNode);
      head.setNext(newNode);
      head = newNode;

    } else {

      Node newNode = new Node(e, head.getPrevious(), head);
      Node tail = head.getPrevious();
      tail.setNext(newNode);
      head.setPrevious(newNode);
      head = newNode;
    }
  }

  /**
   * Remove the first Node in the list and return its element.
   *
   * @return The element of the first Node. If the list is empty, this method returns null.
   */
  public T removeFirst() {
    // TODO
    T answer;

    if(head == null) return null;
    if(head.getNext() == null) {
      answer = head.getElement();
      head = null;
      return answer;
    }

    answer = head.getElement();
    Node tail = head.getPrevious();
    tail.setNext(head.getNext());
    head = tail.getNext();
    head.setPrevious(tail);
    return answer;
  }

  /**
   * @return The element in the last Node of the CDLL. If the list is empty, this method returns null.
   */
  public T getLast() {
    // TODO
    return (head == null) ? null : (head.getNext() == null ) ? head.getElement() : head.getPrevious().getElement();
  }

  /**
   * Adds element e in a new Node to the end of the list.
   *
   * @param e
   *     The element to add.
   */
  public void addLast(T e) {
    // TODO
    if( head == null ) this.addFirst(e);
    else if(head.getNext() == null ) {
      Node newNode = new Node(e, head, head);
      head.setNext(newNode);
      head.setPrevious(newNode);
    }
    else {
      Node tail = head.getPrevious();
      Node newNode = new Node(e, tail, head);
      tail.setNext(newNode);
      head.setPrevious(newNode);
      tail = newNode;
    }
  }

  /**
   * Remove the last Node in the list and return its element.
   *
   * @return The element of the last Node. If the list is empty, this method returns null.
   */
  public T removeLast() {
    // TODO
    if(head == null || head.getNext() == null) return this.removeFirst();
    else {
      Node tail = head.getPrevious();
      T answer = tail.getElement();
      head.setPrevious(tail.getPrevious());
      tail = tail.getPrevious();
      tail.setNext(head);
      return answer;
    }
  }

  /**
   * Moves the head reference to the next element.
   */
  public void rotateForward() {
    // TODO
    if(head == null || head.getNext() == null) return;
    else head = head.getNext();

  }

  /**
   * Moves the head reference to the previous element.
   */
  public void rotateBackward() {
    // TODO
    if(head == null || head.getNext() == null) return;
    else head = head.getPrevious();

  }


  public void show(String string, int n) {
    Node current = head;
    System.out.println(string);
    for(int i = 0; i < n; i++) {
      System.out.print(current.getElement() + ", ");
      current = current.getNext();
    }
  }

}
//