title: Inserting node into Doubly Linked List
body: <p>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.</p>
  
  <p>This is the code for the insert function however there is problems:</p>
  
  <ul>
  <li>It breaks the Doubly Linked List if you insert a node with the same value more than once!</li>
  <li>It is not properly sorting the list.</li>
  </ul>
  
  <p>Here is the code for the class:</p>
  
  <pre><code>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&amp; );
         void remove(const string&amp; );
         void print(ostream&amp; OutStream) const;
         void sort (bool);
  };
  </code></pre>
  
  <p>Here is the code for insert:</p>
  
  <pre><code>void Doubly::insert (const string&amp; 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 -&gt; prev = NULL;
         name -&gt; next = NULL;
         name -&gt; name = input; //
  
      }
  
      //Insertion into a populated list
  else
      {
          node* newnode;
          newnode = head;
  
          while (input &gt; newnode -&gt; name &amp;&amp; newnode -&gt; next != last -&gt; next)
                          newnode = newnode -&gt; next;
  
              if (newnode == head)
                  {
                       node* name = new node;
                       name -&gt; name = input;
                       name -&gt; prev = newnode;
                       name -&gt; next = NULL;
                       head -&gt; next = name;
                       last = name;
                  }
  
             else
             {
                 if (newnode == last &amp;&amp; input &gt; last -&gt; name) //Add the name to the end of the linked list
                     {
                           last -&gt; next = new node;
                           (last -&gt; next) -&gt; prev = last;
                           last = last -&gt; next;
                           last -&gt; next = NULL;
                           last -&gt; name = input;  
                     }
                 else
                     {
                       node* name = new node;
                       name -&gt; name = input;
                       name -&gt; next = newnode;
                       (newnode -&gt; prev) -&gt; next = name;
                       name -&gt; prev = newnode -&gt; prev;
                       newnode -&gt; prev = name;
                     }
            }
      }
  }
  </code></pre>