title: How to insertion sort a doubly linked list in c
body: <p>I am trying to sort a doubly linked list by an integer value.</p>
  
  <p>This is an example node:</p>
  
  <pre><code>struct Node
  {
  
      struct Node* previous;
      struct Node* next;
      int* a;
  
  }Node;
  </code></pre>
  
  <p>I was originally intending to use an insertion sort, but I am struggling severely to come up with the proper code.</p>
  
  <p>My head and tail are simply <code>struct Node* listHead</code> and <code>struct Node* listTail</code>. They are both global variables.</p>
  
  <p>Edit: I looked at several other posts on this topic, and I couldn't get the code to function properly. I apologize for my ineptitude.</p>
  
  <p>Attempt so far:</p>
  
  <pre><code>    struct Node* key = listHead;
      struct Node* i;
      struct Node* temp;
  
      while(key!=NULL)
      {
          temp=key;
          iterator=key-&gt;previous;
          while(i != NULL &amp;&amp; temp-&gt;a&gt;i-&gt;a)
          {
              if(i-&gt;next-&gt;next!=NULL&amp;&amp; i-&gt;next!=NULL)
              {
                  i=i-&gt;next-&gt;next;
                  i=i-&gt;previous;
              }
          }
          if(i-&gt;next-&gt;next!=NULL &amp;&amp; key-&gt;next!=NULL)
          {
          i-&gt;next-&gt;next = temp;
          key = key-&gt;next;
          }
      }
  </code></pre>
  
  <p>Edit: Second code attempt:</p>
  
  <pre><code>    struct Node* newHead = NULL;
      struct Node* newTail = NULL;
  
      struct Node* i;
      struct Node* move = listHead;
      struct Node* temp;
      while(move-&gt;next!=NULL &amp;&amp; move!=NULL)
      {
          if(newHead==NULL)
          {
              temp=move;
              newHead=temp;
          }else if(newTail==NULL)
          {
              temp=move;
              newTail=temp;
          }else if(newHead-&gt;next-&gt;next==NULL)
          {
              temp=move;
              insert_node(newHead, newTail, temp);
          }
          else
          {
              i=newHead-&gt;next;
              while(inserter-&gt;previous!=NULL)
              {
                  if(i-&gt;previous-&gt;a &lt; i-&gt;a)
                  {
                      temp=move;
                      insert_node(i-&gt;previous,i,temp);
                      break;
                  }
                  i=i-&gt;previous;
              }
          }
          move=move-&gt;next;
      }
      listHead=newHead;
      listTail=newTail;
  </code></pre>
  
  <p>This second block of code only appears to sort the last element.</p>
  
  <p>My insert function:</p>
  
  <pre><code>void insert_node(struct Node* first, struct Node* last, struct Node* insert)
  {
      first-&gt;next=insert;
      insert-&gt;previous=first;
      last-&gt;previous=insert;
      insert-&gt;next=last;
  }
  </code></pre>