Data Structures Program on Sorted Doubly Linked List with Insertion and Deletion

     #include < iostream >
  #include < cstdlib >
  #include < string >
  using namespace std;
  class Dllist
  {
     private:
       typedef struct Node
       {
         string name;
         Node* next;
         Node* prev;
       };
       Node* head;
       Node* last;
     public:
       Dllist()
       {
         head = NULL;
         last = NULL;
       }
       bool empty() const { return head==NULL; }
       friend ostream& operator <<(ostream& ,const Dllist& );
       void Insert(const string& );
       void Remove(const string& );
  };
  void Dllist::Insert(const string& s)
  {
     // Insertion into an Empty List.
     if(empty())
     {
       Node* temp = new Node;
       head = temp;
       last = temp;
       temp->prev = NULL;
       temp->next = NULL;
       temp->name = s;
     }
     else
     {
       Node* curr;
       curr = head;
       while( s>curr->name && curr->next != last->next) curr = curr->next;
    
       if(curr == head)
       {
         Node* temp = new Node;
         temp->name = s;
         temp->prev = curr;
         temp->next = NULL;
         head->next = temp;
         last = temp;
         // cout<<" Inserted "<< s <<" After "<< curr->name << endl;
       }
       else
       {
         if(curr == last && s>last->name)
         {
           last->next = new Node;
           (last->next)->prev = last;
           last = last->next;
           last->next = NULL;
           last->name = s;
           // cout<<" Added "<< s <<" at the end "<< endl;
         }
         else
         {
           Node* temp = new Node;
           temp->name = s;
           temp->next = curr;
           (curr->prev)->next = temp;
           temp->prev = curr->prev;
           curr->prev = temp;
           // cout<<" Inserted "<< s <<" Before "<< curr->name<< endl;
         }
       }
     }
  }
  ostream& operator<<(ostream& ostr, const Dllist& dl )
  {
     if(dl.empty()) ostr << " The list is empty. "<< endl;
     else
     {
       Dllist::Node* curr;
       for(curr = dl.head; curr != dl.last->next; curr=curr->next)
         ostr << curr->name <<" ";
       ostr << endl;
       ostr << endl;
       return ostr;
     }
  }
  void Dllist::Remove(const string& s)
  {
     bool found = false;
     if(empty())
     {
       cout<<" This is an empty list! "<< endl;
       return;
     }
     else
     {
       Node* curr;
       for(curr = head; curr != last->next; curr = curr->next)
       {
         if(curr->name == s)
         {
           found = true;
           break;
         }
       }
       if(found == false)
       {
         cout<<" The list does not contain specified Node"<         return;
       }
       else
       {
         // Curr points to the node to be removed.
         if (curr == head && found)
         {
           if(curr->next != NULL)
           {
             head = curr->next;
             delete curr;
             return;
           }
           else
           {
             delete curr;
             head = NULL;
             last = NULL;
             return;
           }
         }
         if (curr == last && found)
         {
           last = curr->prev;
           delete curr;
           return;
         }
         (curr->prev)->next = curr->next;
         (curr->next)->prev = curr->prev;
         delete curr;
       }
     }
  }
  int main()
  {
     Dllist d1;
     int ch;
     string temp;
     while(1)
     {
       cout<< endl;
       cout<<" Doubly Linked List Operations "<< endl;
       cout<<" ------------------------------"<< endl;
       cout<<" 1. Insertion "<< endl;
       cout<<" 2. Deletion "<< endl;
       cout<<" 3. Display "<< endl;
       cout<<" 4. Exit "<< endl;
       cout<<" Enter your choice : ";
       cin>>ch;
       switch(ch)
       {
         case 1: cout<<" Enter Name to be inserted : ";
           cin>>temp;
           d1.Insert(temp);
           break;
         case 2: cout<<" Enter Name to be deleted : ";
           cin>>temp;
           d1.Remove(temp);
           break;
         case 3: cout<<" The List contains : ";
           cout<< d1;
           break;
         case 4: system("pause");
           return 0;
           break;
       }
     }
  }