title: maintaining sorted link list
body: <p>I'm trying to create and maintain a sorted link list. Every new element should be inserted in a way that the list remains sorted. I have been able to code it but am not too happy with my code. </p>
  
  <p>Basically there are 4 conditions that need to be satisfied according to me and in my attempt to achieve all of them i think i have made the code more complicated that it should be. </p>
  
  <p>Just want to know if anyone has coded it more efficiently and if you can tell me how to improve the insert function here. This is my working code below and the conditions in comments. For keeping it small I have not posted the functions to remove elements, destroy list etc.</p>
  
  <pre><code>#include &lt;iostream&gt;
  
      using namespace std;
  
      struct node{
          int _val;
          node* _next;
      };
  
      void printList(node **s){
  
          node *t = *s;
          while(t){
              cout &lt;&lt; t-&gt;_val &lt;&lt; endl;
              t = t-&gt;_next;
          }
      }
  
      void insertSortElement(node** s, int val){
  
          node* t = *s;
          if(t){
              if(t-&gt;_next == NULL || (t-&gt;_val &gt; val)){
                  node* p = new node();
                  p-&gt;_val = val;
                  if(t-&gt;_val &gt; val){
                      //3. More than 1 element in the list but 1st element &gt; val
                      p-&gt;_next = t;
                      *s = p;
                  }
                  else{
                      //2. Only 1 element in the list and &lt; val
                      t-&gt;_next = p;
                  }
              }
              else{
                  //4. More than 1 element and 1st &lt; val
                  node* prev = 0;
                  while(t){
                      if(t-&gt;_val &gt; val)
                          break;
                      prev = t;
                      t = t-&gt;_next;
                  }
                  node* p = new node();
                  p-&gt;_val = val;
                  p-&gt;_next = t;
                  prev-&gt;_next = p;
              }
          }
          else{
  
              //1. no element in the list
              node* p = new node();
              p-&gt;_val = val;
              p-&gt;_next = NULL;
              *s = p;
          }
      } 
  
      int main(){
          struct node* s = 0 ;
  
          insertSortElement(&amp;s,5);
          insertSortElement(&amp;s,6);
          insertSortElement(&amp;s,4);
          insertSortElement(&amp;s,2);
          insertSortElement(&amp;s,8);
          insertSortElement(&amp;s,1);
          printList(&amp;s);
      }
  </code></pre>
  
  <p>EDIT:</p>
  
  <p>Found another implementation, much simpler than mine and handles all cases</p>
  
  <pre><code>void insertSorted(node**s , int val){
          node* current = *s;
  
                  if(current == NULL || current-&gt;_val &gt;= val){
                          node* p = new node();
                          p-&gt;_val = val;
                          p-&gt;_next = current;
                          *s = p;
                  }
                  else{
  
                          while(current-&gt;_next != NULL || current-&gt;_next-&gt;_val &lt; val)
                                  current = current-&gt;_next;
  
                          node*  p = new node();
                          p-&gt;_val = val;
                          p-&gt;_next = current-&gt;_next;
                          current-&gt;_next = p;
                  }
  }
  </code></pre>