How to sort a singly linked list using insertion

A linked list is a data structure made up of one or more than one nodes. Each node contains a data value and a pointer to the next node, forming a chain-like structure. These nodes are stored randomly in the system's memory, which improves its space complexity compared to an array.

Understanding the problem

Several sorting methods can be used to sort a linked list. This Answer explores how a linked list can be sorted using insertion. Insertion sort works the same as we sort the play cards in our hands. It compares the two elements and swaps their position depending on their values. It keeps on swapping until we get a sorted list.

// function for inserting node in a sorted way
void sortedInsert(node**, node*);  
// function for insertion sort (linked list) 
node insertionSort(node *head) 
{ 
    // Initialize sorted and current 
    node *sorted = NULL; 
    node *current = head;
    while (current != NULL) 
    { 
        // Store address for next iteration 
        node *link = current->link; 
        // Insert current in new linked list 
        sortedInsert(&sorted, current); 
        // Update current 
        current = link; 
    } 
    // Update head  
    *head = *sorted; 
    return *head;
}   
// Function to insert a new node 
void sortedInsert(node** head, node* new_node) 
{ 
    node* current;        
    // For head
    if (*head == NULL || (*head)->data >= new_node->data) 
    { 
        new_node->link = *head; 
        *head = new_node; 
    } 
    else
    {   // Locating node (tail)
        current = *head; 
        while (current->link!=NULL && 
               current->link->data < new_node->data) 
        { 
            current = current->link; 
        }
        // Updating link 
        new_node->link = current->link; 
        current->link = new_node; 
    } 
}
int main() 
{ 
  node* list1=new node();  
  list1 = NULL;
  list1=add_node(list1,2);
  add_node(list1,8);
  add_node(list1,5);
  add_node(list1,6);
  cout << "Linked List: ";
  print_data(list1);
  cout<<"\nAfter Sorting: ";
  insertionSort(list1);
  print_data(list1);
  
  return 0; 
}

Explanation

Lines 4–8: We define the insertionSort() function to perform insertion sort on the given linked list. We initialize two pointer variables, sorted and current, to keep track of the list.
Lines 10–17: In the while loop, we save the link of the current node, which has the address of the next node. We call the sortedInsert() function to insert the current node into the sorted linked list. Then, we update the current for the next iteration.
Lines 19–22: We store the updated sorted linked list in the head of the given linked list and return head.
Lines 24–31: We define the sortedInsert() function to add each node in a sorted way in the new linked list. First, we declare the current pointer to keep track of the list. Then, in the if condition, we check the head and update it accordingly.
Lines 33–39: In the else part, we check the given data and find the tail of the list using the while loop. In the loop, we update the link of the current for the next iteration.
Lines 40–45: After finding the tail of the link list, we update the value of the current node with thenew_node.

Time complexity: The time complexity for this approach is $O(n^2)$ , where $n$ is the number of nodes in the linked list.

Space complexity: The space complexity for this approach is $O(1)$ .

Free Resources

How to sort a singly linked list using insertion

Understanding the problem

Solution

Implementation

Explanation