public class DoubleLLexample {

// Build and prInteger a double linked list
// This code is only demonstrative code: much
// of the code should be written as methods
public static void main(String args[])
{
DoubleNode<Integer> prev,next,node,ptr,head,rear;

// Start the DLL with one node with value 1.
// DDL - double linked list
node = new DoubleNode<Integer>(1);
node.setNext(null);
node.setPrevious(null);
// head points to the beginning of the double linked list
head=node;
// rear points to the end of the double linked list
rear=node;
System.out.println("\n\nFirst node initialized");
System.out.format("Double linked list has one element %d in it\n",node.getElement());

// Insert the addNumbers 14, 8, 2, -7 and 20 in order in the DDL which
// already has the value 1 in it.
Integer[] addNumbers = new Integer[5];
addNumbers[0]=14;
addNumbers[1]=8;
addNumbers[2]=2;
addNumbers[3]=-7;
addNumbers[4]=20;

// After insertion, delete the deleteNumbers -7, 20, 8 37 from the DDL
Integer[] deleteNumbers = new Integer[4];
deleteNumbers[0]=-7; // delete node on the left
deleteNumbers[1]=20; // delete node on the right
deleteNumbers[2]=8;  // delete node in the middle
deleteNumbers[3]=37; // number not in list

for(Integer i=0;i<addNumbers.length;i++)
{
// Find the insertion place
ptr=head;
boolean found=false;
while(ptr!=null && !found)
   {
   System.out.println("\nComparison: DLL element: " + ptr.getElement() +  " and number: " + addNumbers[i]);
   if(addNumbers[i] > ptr.getElement()) ptr=ptr.getNext();
   else found=true;
   }

// We have found the inseration place
node = new DoubleNode<Integer>(addNumbers[i]);
if(ptr==head) // insert at the beginning of the DLL before head
   {
   System.out.println("\n---------------\nInsert before head");
   head.setPrevious(node);
   node.setNext(head);
   node.setPrevious(null);
   head=node;
   }
else 
    {
    if(ptr==null) // end rear of list
      {
      System.out.println("\n---------------\nInsert after rear");
      node.setPrevious(rear);
      node.setNext(null);
      rear.setNext(node);
      rear=node;
      }
    else if(ptr!=null) // insert in the middle of DLL just before ptr and after prev
        {
        System.out.println("\n---------------\nInsert in the middle");
        // insert after node
        prev=ptr.getPrevious();
        prev.setNext(node);
        node.setPrevious(prev);
        node.setNext(ptr);
        ptr.setPrevious(node);
        }
    }

System.out.format("\nDDL from left:\n");
next=head;
while(next!=null)
   {
   System.out.format("%3d ",next.getElement());
   next=next.getNext();
   } 
System.out.format("\n");

System.out.format("\nDDL from right:\n");
prev=rear;
while(prev!=null)
   { 
   System.out.format("%3d ",prev.getElement());
   prev=prev.getPrevious();
   }
System.out.format("\n");
} // for add

System.out.format("\n===================================================\n");

// a linear search, better to be a binary search
for(Integer j=0;j<deleteNumbers.length;j++)
{
// Find the deletion place
ptr=head;
boolean found=false;
while(ptr!=null && !found)
   {
   System.out.println("\nComparison: DDL element: " + ptr.getElement() +  " and number: " + deleteNumbers[j]);
   if(deleteNumbers[j] != ptr.getElement()) ptr=ptr.getNext();
   else found=true;
   }

if(found)
{
// We have found the deletion place
if(ptr==head) // insert at the beginning of the DLL before head
   {
   System.out.println("\n---------------\nDelete head");
   head=head.getNext();
   head.setPrevious(null);
   }
else 
    {
    if(ptr==rear) // end rear of list
      {
      System.out.println("\n---------------\nDelete rear");
      rear=rear.getPrevious();
      rear.setNext(null);
      }
    else if(ptr!=null) // insert in the middle of DLL just before ptr and after prev
        {
        System.out.println("\n---------------\nDelete in the middle");
        prev=ptr.getPrevious();
        next=ptr.getNext();
        prev.setNext(next);
        next.setPrevious(prev);
        }
    }
}
else
{
System.out.format("\nNumber %3d not found in the double linked list\n",deleteNumbers[j]);
}

System.out.format("\nDDL from left:\n");
next=head;
while(next!=null)
   {
   System.out.format("%3d ",next.getElement());
   next=next.getNext();
   } 
System.out.format("\n");

System.out.format("\nDDL from right:\n");
prev=rear;
while(prev!=null)
   { 
   System.out.format("%3d ",prev.getElement());
   prev=prev.getPrevious();
   }
System.out.format("\n");
} // for delete


} // main 
        
} // DoubleLLexample