{"id":188005,"date":"2025-02-06T09:26:53","date_gmt":"2025-02-06T09:26:53","guid":{"rendered":"https:\/\/learnexams.com\/blog\/?p=188005"},"modified":"2025-02-06T09:26:55","modified_gmt":"2025-02-06T09:26:55","slug":"insertion-sort-for-doubly-linked-lists","status":"publish","type":"post","link":"https:\/\/www.learnexams.com\/blog\/2025\/02\/06\/insertion-sort-for-doubly-linked-lists\/","title":{"rendered":"Insertion sort for doubly-linked lists"},"content":{"rendered":"\n<ol start=\"4\" class=\"wp-block-list\">\n<li>Insertion sort for doubly-linked lists [4]. From the prerequisite course, you have learned that Insertion sort is a simple sorting algorithm that builds the final sorted list one item at a time. Insertion sort for a doubly-linked list operates similarly to the insertion sort algorithm used for arrays. Starting with the second list element, each element in the linked list is visited. Each visited element is moved back as needed and inserted into the correct position in the list&#8217;s sorted portion. The python code of Insertion sort for doubly-linked lists is shown below.<\/li>\n<\/ol>\n\n\n\n<figure class=\"wp-block-image size-large\"><img decoding=\"async\" src=\"https:\/\/learnexams.com\/blog\/wp-content\/uploads\/2025\/02\/image-69-830x1024.png\" alt=\"\" class=\"wp-image-188006\"\/><\/figure>\n\n\n\n<p><mark style=\"background-color:rgba(0, 0, 0, 0)\" class=\"has-inline-color has-ast-global-color-6-color\"><strong>The Correct Answer and Explanation is :<\/strong><\/mark><\/p>\n\n\n\n<p>nsertion sort is a straightforward algorithm that constructs a sorted sequence incrementally, processing one element at a time.hen applied to a doubly linked list, the algorithm operates similarly to its array-based counterpart but leverages the bidirectional pointers for efficient insertion operations.<br><strong>Python Implementation:<\/strong><\/p>\n\n\n\n<p>&#8220;python<br>class Node:<br>def <strong>init<\/strong>(self, data):<br>self.data = data<br>self.prev = None<br>self.next = None<\/p>\n\n\n\n<p>def insertion_sort(head):<br>if not head:<br>return head<\/p>\n\n\n\n<pre class=\"wp-block-code\"><code>current = head.next\nwhile current:\n    key = current\n    move = current.prev\n    while move and key.data &lt; move.data:\n        move = move.prev\n\n    next_current = current.next\n\n    # Detach key node\n    if current.prev:\n        current.prev.next = current.next\n    if current.next:\n        current.next.prev = current.prev\n\n    # Insert key node at correct position\n    if not move:\n        # Insert at the beginning\n        key.next = head\n        key.prev = None\n        head.prev = key\n        head = key\n    else:\n        key.next = move.next\n        key.prev = move\n        if move.next:\n            move.next.prev = key\n        move.next = key\n\n    current = next_current\n\nreturn head<\/code><\/pre>\n\n\n\n<p>&#8220;`<br><strong>Explanation:<\/strong><\/p>\n\n\n\n<ol class=\"wp-block-list\">\n<li><strong>Node Class Definition:<\/strong> <code>Node<\/code> class is defined to represent each element in the doubly linked list, containing <code>data<\/code>, <code>prev<\/code> (pointer to the previous node), and <code>next<\/code> (pointer to the next node).<\/li>\n\n\n\n<li><strong>Function <code>insertion_sort<\/code>:<\/strong> his function takes the <code>head<\/code> of the doubly linked list as its parameter. If the list is empty (<code>head<\/code> is <code>None<\/code>), it returns <code>None<\/code>.<\/li>\n\n\n\n<li><strong>Traversal:<\/strong> he algorithm starts with the second node (<code>head.next<\/code>) and iterates through each node (<code>current<\/code>). For each <code>current<\/code> node, it identifies the correct position in the sorted portion of the list by comparing <code>current.data<\/code> with the data in the preceding nodes (<code>move<\/code>).<\/li>\n\n\n\n<li><strong>Finding the Insertion Point:<\/strong> he inner <code>while<\/code> loop moves backward through the sorted portion of the list to find the appropriate spot where the <code>current<\/code> node should be inserted.<\/li>\n\n\n\n<li><strong>Detaching the Current Node:<\/strong> efore insertion, the <code>current<\/code> node is detached from its original position by updating the <code>next<\/code> pointer of its <code>prev<\/code> node and the <code>prev<\/code> pointer of its <code>next<\/code> node.<\/li>\n\n\n\n<li><strong>Inserting the Node:<\/strong><\/li>\n<\/ol>\n\n\n\n<ul class=\"wp-block-list\">\n<li><strong>At the Beginning:<\/strong> f no node in the sorted portion has a value less than <code>current.data<\/code> (<code>move<\/code> becomes <code>None<\/code>), the <code>current<\/code> node is inserted at the beginning. &#8211; <strong>Elsewhere:<\/strong> therwise, the <code>current<\/code> node is inserted after the <code>move<\/code> node.<\/li>\n<\/ul>\n\n\n\n<ol class=\"wp-block-list\">\n<li><strong>Updating Pointers:<\/strong> fter insertion, the <code>prev<\/code> and <code>next<\/code> pointers of the involved nodes are updated to maintain the integrity of the doubly linked list structure.<\/li>\n\n\n\n<li><strong>Advancing to the Next Node:<\/strong> he <code>current<\/code> pointer is moved to the next node in the original list (<code>next_current<\/code>), and the process repeats until all nodes are processed.<br><strong>Time Complexity:<\/strong><\/li>\n<\/ol>\n\n\n\n<p>he time complexity of this insertion sort implementation on a doubly linked list is (O(n^2)) in the worst case, where (n) is the number of nodes. This is because, for each node, the algorithm may traverse a significant portion of the sorted list to find the correct insertion point.<br><strong>Advantages:<\/strong><\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li><strong>Stability:<\/strong> nsertion sort maintains the relative order of equal elements, making it a stable sorting algorithm.<\/li>\n\n\n\n<li><strong>Simplicity:<\/strong> he algorithm is straightforward to implement and understand.<\/li>\n\n\n\n<li><strong>Efficiency for Small or Nearly Sorted Lists:<\/strong> nsertion sort performs efficiently for small datasets or lists that are already partially sorted.<br><strong>Conclusion:<\/strong><\/li>\n<\/ul>\n\n\n\n<p>mplementing insertion sort on a doubly linked list involves iterating through the list, detaching each node, and inserting it into its correct position within the sorted portion. The bidirectional nature of doubly linked lists facilitates efficient insertion operations, as nodes can be easily re-linked in both forward and backward directions.<\/p>\n","protected":false},"excerpt":{"rendered":"<p>The Correct Answer and Explanation is : nsertion sort is a straightforward algorithm that constructs a sorted sequence incrementally, processing one element at a time.hen applied to a doubly linked list, the algorithm operates similarly to its array-based counterpart but leverages the bidirectional pointers for efficient insertion operations.Python Implementation: &#8220;pythonclass Node:def init(self, data):self.data = dataself.prev [&hellip;]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"site-sidebar-layout":"default","site-content-layout":"","ast-site-content-layout":"default","site-content-style":"default","site-sidebar-style":"default","ast-global-header-display":"","ast-banner-title-visibility":"","ast-main-header-display":"","ast-hfb-above-header-display":"","ast-hfb-below-header-display":"","ast-hfb-mobile-header-display":"","site-post-title":"","ast-breadcrumbs-content":"","ast-featured-img":"","footer-sml-layout":"","ast-disable-related-posts":"","theme-transparent-header-meta":"","adv-header-id-meta":"","stick-header-meta":"","header-above-stick-meta":"","header-main-stick-meta":"","header-below-stick-meta":"","astra-migrate-meta-layouts":"default","ast-page-background-enabled":"default","ast-page-background-meta":{"desktop":{"background-color":"","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-opacity":"","overlay-gradient":""},"tablet":{"background-color":"","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-opacity":"","overlay-gradient":""},"mobile":{"background-color":"","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-opacity":"","overlay-gradient":""}},"ast-content-background-meta":{"desktop":{"background-color":"var(--ast-global-color-5)","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-opacity":"","overlay-gradient":""},"tablet":{"background-color":"var(--ast-global-color-5)","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-opacity":"","overlay-gradient":""},"mobile":{"background-color":"var(--ast-global-color-5)","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-opacity":"","overlay-gradient":""}},"footnotes":""},"categories":[25],"tags":[],"class_list":["post-188005","post","type-post","status-publish","format-standard","hentry","category-exams-certification"],"_links":{"self":[{"href":"https:\/\/www.learnexams.com\/blog\/wp-json\/wp\/v2\/posts\/188005","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.learnexams.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.learnexams.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.learnexams.com\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.learnexams.com\/blog\/wp-json\/wp\/v2\/comments?post=188005"}],"version-history":[{"count":0,"href":"https:\/\/www.learnexams.com\/blog\/wp-json\/wp\/v2\/posts\/188005\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.learnexams.com\/blog\/wp-json\/wp\/v2\/media?parent=188005"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.learnexams.com\/blog\/wp-json\/wp\/v2\/categories?post=188005"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.learnexams.com\/blog\/wp-json\/wp\/v2\/tags?post=188005"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}