{"id":3646,"date":"2021-08-06T11:54:09","date_gmt":"2021-08-06T11:54:09","guid":{"rendered":"https:\/\/www.prepbytes.com\/blog\/?p=3646"},"modified":"2022-11-16T11:25:37","modified_gmt":"2022-11-16T11:25:37","slug":"insertion-sort-for-doubly-linked-list","status":"publish","type":"post","link":"https:\/\/prepbytes.com\/blog\/insertion-sort-for-doubly-linked-list\/","title":{"rendered":"Insertion Sort for Doubly Linked List"},"content":{"rendered":"

\"\"<\/p>\n

In the respective article, we will look how stable sorting such as insertion sort works in doubly linked lists. Now let’s just see an approach of insertion sort for doubly linked list. <\/p>\n

Problem Statement of doubly linked list insertion sort<\/h3>\n

In this question, we are given a doubly linked list. We have to sort the given list using the insertion sort technique.<\/p>\n

Input:<\/strong><\/p>\n

\"\"<\/p>\n

Output:<\/strong> <\/p>\n

\"\"<\/p>\n

Explanation:<\/strong> The given list has been sorted.<\/p>\n

This question is not a tricky one. We just have to extract the elements from the list one by one, and insert them in the new list in a sorted way. This sorted insert technique has been explained in detail in the approach.<\/p>\n

Let us have a glance at the approach.<\/p>\n

Approach of insertion sort for doubly linked list<\/h3>\n

The approach is going to be pretty simple. We will create an empty result doubly linked list which will be sorted. Then, we will traverse the given doubly linked list, and for every node that we visit, we will insert the current node in a sorted way in our result list.<\/p>\n

To insert in a sorted way, we will traverse our result list and keep comparing every node with our current node. As soon as we find a node whose value is greater than the current node, we will insert the current node just before that node. If the current node value is greater than every other node of our result list, then we will append the current node at the end.<\/p>\n

After complete traversal, change the head of the given linked list to the head of the result list.<\/p>\n

Algorithm of doubly linked list insertion sort<\/h3>\n
    \n
  • Initialize the newly created sorted list as NULL.<\/li>\n
  • Traverse the given doubly linked list.<\/li>\n
  • For every node, store the next of node in a temp variable and remove all of its links.<\/li>\n
  • Insert the current node in a sorted way in the result list.<\/li>\n
  • To insert in a sorted way, traverse through the result list and keep comparing every node with our current node. As soon as a node is found whose value is greater than the current node, we will insert the current node just before that node. If the current node value is greater than every node of the result list, then append the current node at the end of the result list.<\/li>\n
  • Update current\u2019s value with temp.<\/li>\n
  • Update the head pointer by making it point to our result list.<\/li>\n<\/ul>\n

    Dry Run of insertion sort for doubly linked list<\/h3>\n

    \"\"<\/p>\n

    Code Implementation of doubly linked list insertion sort<\/h3>\n\t\t\t\t\t\t