class DoublyLinkedNode {
  Object data;
  DoublyLinkedNode prev;
  DoublyLinkedNode next;

  public DoublyLinkedNode( ) { }
   public DoublyLinkedNode( Object data, DoublyLinkedNode prev, DoublyLinkedNode next ) {
    this.data = data;
    this.prev = prev;
    this.next = next;
  }
   public DoublyLinkedNode( Object data ) {
    this( data, null, null );
  }
}

public class DoublyLinkedList {

  DoublyLinkedNode head;
  DoublyLinkedNode tail;

  public DoublyLinkedList( ) { }
  public void insertAfter( DoublyLinkedNode node, DoublyLinkedNode newNode ) {
    newNode.prev = node;
    newNode.next = node.next;
    if( node.next == null ) {
      tail = newNode;
    }
    else {
      node.next.prev = newNode;
    }
    node.next = newNode;
  }

  public void insertBefore( DoublyLinkedNode node, DoublyLinkedNode newNode ) {
    newNode.prev = node.prev;
    newNode.next = node;
    if( node.prev == null ) {
      head = newNode;
    } else {
      node.prev.next = newNode;
    }
     node.prev = newNode;
  }
   public void insertFront( DoublyLinkedNode newNode ) {
     if( head == null ) {
      head = newNode;
      tail = newNode;
      newNode.prev = null;
      newNode.next = null;
     }
     else {
      insertBefore( head, newNode );
    }
  }
   public void insertEnd( DoublyLinkedNode newNode ) {
     if ( tail == null ) {
      insertFront( newNode );
    }
    else {
      insertAfter( tail, newNode );
    }
  }

  public void remove( DoublyLinkedNode node ) {
    if( node.prev == null ) {
      head = node.next; 
    }
    else {
      node.prev.next = node.next;
    }
    if( node.next == null ) {
      tail = node.prev; 
    } 
    else {
      node.next.prev = node.prev;
    }
  }
   public void removeFront( ) {
    if( head != null ) {
      remove( head );
    }
  }
   public void removeEnd( ) {
    if( tail != null ) {
      remove( tail );
    }
  }
   public DoublyLinkedNode get( Object data ) {
     for( DoublyLinkedNode cursor = head; cursor != null; cursor = cursor.next ) {
      if( cursor.data.equals( data ) ) {
        return cursor;
      }
    }
     return null;
  }
   public static void main( String[] args ) {
    DoublyLinkedList list = new DoublyLinkedList( );
    DoublyLinkedNode node1 = new DoublyLinkedNode( "A" );
    DoublyLinkedNode node2 = new DoublyLinkedNode( "B" );
    DoublyLinkedNode node3 = new DoublyLinkedNode( "C" );
    DoublyLinkedNode node4 = new DoublyLinkedNode( "D" );

    list.insertFront( node1 );
    list.insertEnd( node2 );
    list.insertEnd( node3 );
    list.insertEnd( node4 );
    for( DoublyLinkedNode i = list.head; i != null; i = i.next ) {
      System.out.println( i.data ); 
    } 
  }
}