title: putting node linked list in alphabetical order
body: <p>I need to make it so the user can put in words until they hit enter 'xxx'. this part is already done, but then i need the list to always be in alphabetical order. I cant figure out how to do this part. I have to make it in alphabetical order in the function that adds a new node, not the function that prints the nodes to the screen. this is because it is for a class and is required.</p>
  
  <p>Node header file:</p>
  
  <pre><code>struct Node
  {
      string       word;
      struct Node *next;
  };
  </code></pre>
  
  <p>The function prototype header file:</p>
  
  <pre><code>Node *add_node(Node *list, const string &amp;s);
  Node *del_node(Node *list, const string &amp;s);
  
  void deallocate(Node *list);
  void print(Node *list);
  </code></pre>
  
  <p>The code that gets compiled:</p>
  
  <pre><code>#include    &lt;iostream&gt;
  #include    &lt;iomanip&gt;
  #include    &lt;string&gt;
  using namespace std;
  
  #include    "Node.h"
  #include    "funcs.h"
  
  int main()
  {
      struct Node *list = 0;      // list is a pointer to struct Node
  
      cout &lt;&lt; "please enter a few words (xxx to terminate list):\n";
  
      string s;                   // s is a string object
  
      while (cin &gt;&gt; s)           // read a string into s
      {
          if (s == "xxx")
          {
              break;              // terminate loop when string is equal to         "xxx"
          }
          // add s to list in alphabetical order
          list = add_node(list, s);
  
          cout &lt;&lt; "\nlist:\n";
          print(list);
          cout &lt;&lt; '\n';
      }
  
      cout &lt;&lt; "\nhere is the list:\n";
      print(list);
      cout &lt;&lt; '\n';
  
      cout &lt;&lt; "please enter word words to delete from the list (xxx to    terminate):\n";
          while (cin &gt;&gt; s)
          {
              if (s == "xxx")
              {
                  break;              // terminate loop when string is equal to "xxx"
              }
              // delete first node containing string s
              //list = del_node(list, s);
  
              cout &lt;&lt; "\nlist:\n";
              print(list);
              cout &lt;&lt; '\n';
          }
  
      cout &lt;&lt; "\nthe final list:\n";
      print(list);
      cout &lt;&lt; '\n';
      // deallocate the linked list
      cout &lt;&lt; "\ndeallocating the list:\n";
      deallocate(list);
  
      cout &lt;&lt; "\nall done!\n";
      return 0;
  }
  </code></pre>
  
  <p>The code with the functions:</p>
  
  <pre><code>#include    &lt;iostream&gt;
  #include    &lt;iomanip&gt;
  #include    &lt;string&gt;
  using namespace std;
  
  #include    "Node.h"
  
  
  Node *add_node(Node *list, const string &amp;s)
  {
      struct Node *n = new struct Node;
      n-&gt;word = s;            // copy string s to word
      n-&gt;next = list;
  
      // add node n to the list 
      // the list should always be in ascending alphabetical order
  
      list = n;
  
      return list;            // returning pointer to beginning of the list
  }
  
  
  Node *del_node(Node *list, const string &amp;s)
  {
      // delete node in the list that contains s
      // the list should always be in ascending alphabetical order
  
      // if s does not appear in the list, there is nothing to do
      // if s appears multiple times in the list, delete the first occurrence
      Node *lastp = 0;
      Node *p = list;
      for (; p; p = p-&gt;next)
      {
          if (p-&gt;word == s)
          {
              lastp-&gt;next = p-&gt;next;
              delete p;
              break;
          }
          lastp = p;
      } 
  
  
      return list;            // returning pointer to beginning of the list
  }
  
  
  void deallocate(Node *list)
  {
      for (struct Node *p = list; p;)
      {
          struct Node *tmp = p;   // remember current pointer
  
          p = p-&gt;next;            // advance p to the next node
  
          delete tmp;             // deallocate tmp
  
          // OK to print pointers tmp and p
          cout &lt;&lt; "deallocated\t" &lt;&lt; tmp &lt;&lt; "\tnext is\t" &lt;&lt; p &lt;&lt; '\n';
      }
  }
  
  
  void print(Node *list)
  {
      for (struct Node *p = list; p; p = p-&gt;next)
      {
          cout &lt;&lt; p &lt;&lt; '\t' &lt;&lt; setw(8) &lt;&lt; p-&gt;word
              &lt;&lt; '\t' &lt;&lt; "next:" &lt;&lt; '\t' &lt;&lt; p-&gt;next &lt;&lt; '\n';
      }
  }
  </code></pre>
  
  <p>All the code probably isnt required to answer the question but i figured i'd include it.</p>