/* package whatever; // don't place package name! */

import java.util.*;
import java.lang.*;
import java.io.*;

class Ideone {
   public static void main(String[] args) {
      DoubleLinkedList dbl = new DoubleLinkedList();

      Node jacques = new Node("Jacques");
      dbl.setHead(jacques);

      Node joseph = new Node("Joseph");

      Node peter = new Node("Peter");

      Node francis = new Node("Francis");

      Node gilbert = new Node("Gilbert");
      dbl.setTail(gilbert);

      jacques.setNextNode(joseph);

      joseph.setPreviousNode(jacques);
      joseph.setNextNode(peter);

      peter.setPreviousNode(joseph);
      peter.setNextNode(francis);

      francis.setPreviousNode(peter);
      francis.setNextNode(gilbert);

      gilbert.setPreviousNode(francis);

      System.out.println(dbl.toString());
      System.out.println("++++++++++++++++++++++++++++++++");
      System.out.println(dbl.reverseToString());
      System.out.println("++++++++++++++++++++++++++++++++");
      System.out.println("++++++++++++++++++++++++++++++++");
      System.out.println("++++++++++++++++++++++++++++++++");
      DoubleLinkedList.reverseTwoNode(joseph, francis);
      System.out.println(dbl.toString());
      System.out.println("++++++++++++++++++++++++++++++++");
      System.out.println(dbl.reverseToString());
   }
   
}

class DoubleLinkedList {

   private Node head; //the head node pointer of the DLL
   private Node tail; //the tail node pointer of the DLL
   private int size; //The size of the DLL, number of String


   public static void reverseTwoNode(Node n1, Node n2) {
      if (n1 == n2.getPreviousNode() || n2 == n1.getPreviousNode()) {
         /* Adjacent nodes */

         /* Order is relevant */
         Node first;
         Node second;
         if (n1 == n2.getPreviousNode()) {
            first = n1;
            second = n2;
         } else {
            first = n2;
            second = n1;
         }

         first.setNextNode(second.getNextNode());
         second.setPreviousNode(first.getPreviousNode());

         if (first.getNextNode() != null)
            first.getNextNode().setPreviousNode(first);

         if (second.getPreviousNode() != null)
            second.getPreviousNode().setNextNode(second);

         second.setNextNode(first);
         first.setPreviousNode(second);
      } else {
         /* Non adjacent */
         Node prevN1 = n1.getPreviousNode();
         Node nextN1 = n1.getNextNode();
         Node prevN2 = n2.getPreviousNode();
         Node nextN2 = n2.getNextNode();

         n1.setPreviousNode(prevN2);
         n1.setNextNode(nextN2);
         n2.setPreviousNode(prevN1);
         n2.setNextNode(nextN1);

         if (prevN1 != null)
            prevN1.setNextNode(n2);
         if (nextN1 != null)
            nextN1.setPreviousNode(n2);
         if (prevN2 != null)
            prevN2.setNextNode(n1);
         if (nextN2 != null)
            nextN2.setPreviousNode(n1);
      }
   }

   public static void reverseTwoNodeOriginalCode(Node N1, Node N2) {
      N1.setNextNode(N2.getNextNode());
      N2.setPreviousNode(N1.getPreviousNode());

      if (N1.getNextNode() != null)
         N1.getNextNode().setPreviousNode(N1);

      if (N2.getPreviousNode() != null)
         N2.getPreviousNode().setNextNode(N2);

      N2.setNextNode(N1);
      N1.setPreviousNode(N2);
   }

   public DoubleLinkedList() {
      this.size = 0;
      this.setTail(null);
      this.setHead(null);
   }

   public String toString() {
      String str = "List of candidate \n";
      str += "head-->";

      Node iterator = this.getHead();

      while (iterator != null) {
         str += iterator.getString();
         str += "-->";
         iterator = iterator.getNextNode();
      }
      return str + "tail";
   }

   /**
    * Return string that display DLL from tail to head
    * 
    * @return str
    */
   public String reverseToString() {
      String str = "Reverse\n";
      str += "tail-->";

      Node iterator = this.getTail();

      while (iterator != null) {
         str += iterator.getString();
         str += "-->";
         iterator = iterator.getPreviousNode();
      }

      return (str + "head");
   }

   public Node getNode(int index) {

      Node result = null;
      if (index >= 0 && index < this.size) {
         result = this.getHead();
         for (int i = 0; i < index; i++) {
            result = result.getNextNode();
         }
      }
      return result;
   }

   public Node getHead() {
      return head;
   }

   public void setHead(Node head) {
      this.head = head;
   }

   public Node getTail() {
      return tail;
   }

   public void setTail(Node tail) {
      this.tail = tail;
   }
}

class Node {

   private Node prevNode; //Pointer to the previous Node
   private Node nextNode; //Pointer to the next Node
   private String candidate; //String that own the Node

   /**
    * Constructor
    * Simple constructor that fill instantiate candidate provided,
    * and initialize prevNode and nextNode to null
    * 
    * @param C
    */
   public Node(String C) {
      this.prevNode = null;
      this.nextNode = null;
      this.candidate = C;
   }

   /**
    * Advanced Constructor
    * Identical to the previous Construtor but allow to set a previousNode and nextNode
    * 
    * @param C
    * @param prevNode
    * @param nextNode
    */
   public Node(String C, Node prevNode, Node nextNode) {
      this.prevNode = prevNode;
      this.nextNode = nextNode;
      this.candidate = C;
   }

   /**
    * Get String from the current node
    * 
    * @return candidate
    */
   public String getString() {
      return this.candidate;
   }

   /**
    * Set the provided candidate to the current Node
    * 
    * @param C
    */
   public void setString(String C) {
      this.candidate = C;
   }

   /**
    * Get the previous Node from the current Node
    * 
    * @return prevNode
    */
   public Node getPreviousNode() {
      return this.prevNode;
   }

   /**
    * Set the previous Node to the current Node
    * 
    * @param N
    */
   public void setPreviousNode(Node N) {
      this.prevNode = N;
   }

   /**
    * Get the next Node from the current Node
    * 
    * @return nextNode
    */
   public Node getNextNode() {
      return this.nextNode;
   }

   /**
    * Set the a provided Node to the nextNode of the current Node
    * 
    * @param N
    */
   public void setNextNode(Node N) {
      this.nextNode = N;
   }
}