Inserting node into Doubly Linked List

I am wanting to insert a newnode that will contain a name into the correct position of the Doubly Linked List. Basically an Insertion sort is what I want to achieve here.

This is the code for the insert function however there is problems:

• It breaks the Doubly Linked List if you insert a node with the same value more than once!
• It is not properly sorting the list.

Here is the code for the class:

class Doubly
{
private:
        struct node
           {
              string name; //stores name
              node* next; //points to next node
              node* prev; //points to previous node
           };

           node* head; //points to the first node in the list
           node* last; //points to the last node in the list

        public:

            Doubly(); //cstrctr
            ~Doubly(); //dstrctr

       bool empty() const { return head==NULL; }
       void insert(const string& );
       void remove(const string& );
       void print(ostream& OutStream) const;
       void sort (bool);
};

Here is the code for insert:

void Doubly::insert (const string& input)
{
    // Insertion into an Empty List.

if(empty()) //create a new list with one node = Head/Null
    {

       node* name = new node;
       head = name;
       last = name;
       name -> prev = NULL;
       name -> next = NULL;
       name -> name = input; //

    }

    //Insertion into a populated list
else
    {
        node* newnode;
        newnode = head;

        while (input > newnode -> name && newnode -> next != last -> next)
                        newnode = newnode -> next;

            if (newnode == head)
                {
                     node* name = new node;
                     name 开发者_运维问答-> name = input;
                     name -> prev = newnode;
                     name -> next = NULL;
                     head -> next = name;
                     last = name;
                }

           else
           {
               if (newnode == last && input > last -> name) //Add the name to the end of the linked list
                   {
                         last -> next = new node;
                         (last -> next) -> prev = last;
                         last = last -> next;
                         last -> next = NULL;
                         last -> name = input;  
                   }
               else
                   {
                     node* name = new node;
                     name -> name = input;
                     name -> next = newnode;
                     (newnode -> prev) -> next = name;
                     name -> prev = newnode -> prev;
                     newnode -> prev = name;
                   }
          }
    }
}

---

I think the problem is when inserting at the head of the list, and you only have one element, the while (input > newnode -> name && newnode -> next != last -> next) can exit because of 2 reasons, and you are asuming that if the pointer is still at the head you have to insert it afterwards, but maybe it just went out of the while because there was only one element and you have to insert the new one before the head.

So you probably have to do something like:

   if (newnode->next == head->next) { 
        // Create the node and set the common values for all the cases 
        node* name = new node;
        name->name = input;
        if (input > newnode->name) { // Insert as second element
             name->prev = newnode;
             name->next = NULL;
             newnode->prev = NULL;
             newnodw->next = name;  
             head = newnode;
             last = name;                
        }
        else { // Insert as first element
             name->prev = NULL;
             name->next = newnode;
             newnode->prev = name;
             newnodw->next = NULL; 
             head = name;
             last = newnode;
        }

---

#include<stdio.h>
#include<conio.h>
#include<malloc.h>
struct dnode
{
  int data;
  struct dnode *p,*n;
};
  typedef struct dnode dnode;
  dnode *start,*last;
  dnode *createNode(int ele)
  {
   dnode *nnode;
   nnode=(dnode*)malloc(sizeof(dnode));
   nnode->n=NULL;
   nnode->data=ele;
   return nnode;
  }
   dnode *insertBegining(int ele)
   {
    dnode *nnode,*curr,*prev;
    nnode=createNode(ele);
    if(start==NULL)
    {
     start=nnode;
     nnode->p=NULL;
     return start;
    }
    curr=start;
    start=nnode;
    nnode->p=NULL;
    nnode->n=curr;
    curr->p=nnode;
    return start;
   }
  dnode *insertLast(int ele)
  {
   dnode *nnode,*curr,*prev;
   nnode=createNode(ele);
   if(start==NULL)
   {
    start=nnode;
    nnode->p=NULL;
    return start;
   }
  curr=start;
  while(curr!=NULL)
  {
   prev=curr;
   curr=curr->n;
  }
 prev->n=nnode;
 nnode->p=prev;
 return start;
}
void display()
{
 dnode *curr;
 curr=start;
 while(curr!=NULL)
 {
  printf("%d--->",curr->data);
  curr=curr->n;
 }
}
 void main()
 {
  int ch,ele;
  clrscr();
  do
  {
   printf("\nEnter choice");
   printf("\n1-insert beginning");
   printf("\n2-insert last");
   printf("\n3-display");
   printf("\n4-Exit");
   scanf("%d",&ch);
   switch(ch)
   {
    case 1:
    printf("\nEnter Number");
    scanf("%d",&ele);
    insertBegining(ele);
    break;
    case 2:
    printf("enter number");
    scanf("%d",&ele);
    insertLast(ele);
    break;
    case 3:
    display();
    break;
   }
  }
  while(ch!=4);
  getch();
  }