title: Understanding insertion sort for doubly linked list
body: <p>So I understand how insertion sort works but trying to apply the concept to doubly linked lists fizzles out my brain. Can someone please explain how the algorithm works in this context? I cannot wrap my head around how the node pointers change after each node-by-node comparison, given a pre-existing linked list. I am currently working in Java and referring to this code-example: <a href="https://www.geeksforgeeks.org/insertion-sort-doubly-linked-list/" rel="nofollow noreferrer">https://www.geeksforgeeks.org/insertion-sort-doubly-linked-list/</a></p>
  <p>Below are two functions, sortedInsert and insertionSort, where the former is helper function.</p>
  <p>What is the else clause doing in sortedInsert? Also why does the author &quot;removing all links so as to create current&quot; in the insertionSort function?</p>
  <pre><code>// function to insert a new node in sorted way in
  // a sorted doubly linked list
  static Node sortedInsert(Node head_ref, Node newNode)
  {
      Node current;
   
      // if list is empty
      if (head_ref == null)
          head_ref = newNode;
   
      // if the node is to be inserted at the beginning
      // of the doubly linked list
      else if ((head_ref).data &gt;= newNode.data)
      {
          newNode.next = head_ref;
          newNode.next.prev = newNode;
          head_ref = newNode;
      }
   
      else
      {
          current = head_ref;
   
          // locate the node after which the new node
          // is to be inserted
          while (current.next != null &amp;&amp;
              current.next.data &lt; newNode.data)
              current = current.next;
   
          //Make the appropriate links /
   
          newNode.next = current.next;
   
          // if the new node is not inserted
          // at the end of the list
          if (current.next != null)
              newNode.next.prev = newNode;
   
          current.next = newNode;
          newNode.prev = current;
      }
      return head_ref;
  }
   
  // function to sort a doubly linked list using insertion sort
  static Node insertionSort(Node head_ref)
  {
      // Initialize 'sorted' - a sorted doubly linked list
      Node sorted = null;
   
      // Traverse the given doubly linked list and
      // insert every node to 'sorted'
      Node current = head_ref;
      while (current != null)
      {
   
          // Store next for next iteration
          Node next = current.next;
   
          // removing all the links so as to create 'current'
          // as a new node for insertion
          current.prev = current.next = null;
   
          // insert current in 'sorted' doubly linked list
          sorted=sortedInsert(sorted, current);
   
          // Update current
          current = next;
      }
   
      // Update head_ref to point to sorted doubly linked list
      head_ref = sorted;
       
      return head_ref;
  }
  </code></pre>