{"id":27339,"date":"2018-01-20T21:14:48","date_gmt":"2018-01-20T15:44:48","guid":{"rendered":"https:\/\/www.wikitechy.com\/technology\/?p=27339"},"modified":"2018-01-20T21:14:48","modified_gmt":"2018-01-20T15:44:48","slug":"doubly-linked-list","status":"publish","type":"post","link":"https:\/\/www.wikitechy.com\/technology\/doubly-linked-list\/","title":{"rendered":"Delete a node in a Doubly Linked List"},"content":{"rendered":"<p>Write a function to delete a given node in a doubly linked list.<span id=\"more-7293\"><\/span><\/p>\n<pre>     (a) Original Doubly Linked List<\/pre>\n<p><img fetchpriority=\"high\" decoding=\"async\" class=\"aligncenter size-full wp-image-27303\" src=\"https:\/\/www.wikitechy.com\/technology\/wp-content\/uploads\/2017\/06\/DLL3-1.png\" alt=\"Delete a node in a Doubly Linked List\" width=\"553\" height=\"112\" srcset=\"https:\/\/www.wikitechy.com\/technology\/wp-content\/uploads\/2017\/06\/DLL3-1.png 553w, https:\/\/www.wikitechy.com\/technology\/wp-content\/uploads\/2017\/06\/DLL3-1-300x61.png 300w, https:\/\/www.wikitechy.com\/technology\/wp-content\/uploads\/2017\/06\/DLL3-1-550x112.png 550w\" sizes=\"(max-width: 553px) 100vw, 553px\" \/><\/p>\n<pre>     (a) After deletion of head node<\/pre>\n<p><img decoding=\"async\" class=\"aligncenter size-full wp-image-27275\" src=\"https:\/\/www.wikitechy.com\/technology\/wp-content\/uploads\/2017\/06\/DLL1-1.png\" alt=\"Delete a node in a Doubly Linked List\" width=\"423\" height=\"112\" srcset=\"https:\/\/www.wikitechy.com\/technology\/wp-content\/uploads\/2017\/06\/DLL1-1.png 423w, https:\/\/www.wikitechy.com\/technology\/wp-content\/uploads\/2017\/06\/DLL1-1-300x79.png 300w\" sizes=\"(max-width: 423px) 100vw, 423px\" \/><\/p>\n<pre>     (a) After deletion of middle node<\/pre>\n<p><img decoding=\"async\" class=\"aligncenter size-full wp-image-27278\" src=\"https:\/\/www.wikitechy.com\/technology\/wp-content\/uploads\/2017\/06\/DLL2.png\" alt=\"Delete a node in a Doubly Linked List\" width=\"323\" height=\"112\" srcset=\"https:\/\/www.wikitechy.com\/technology\/wp-content\/uploads\/2017\/06\/DLL2.png 323w, https:\/\/www.wikitechy.com\/technology\/wp-content\/uploads\/2017\/06\/DLL2-300x104.png 300w, https:\/\/www.wikitechy.com\/technology\/wp-content\/uploads\/2017\/06\/DLL2-320x112.png 320w\" sizes=\"(max-width: 323px) 100vw, 323px\" \/><\/p>\n<pre>     (a) After deletion of last node<\/pre>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"aligncenter size-full wp-image-27279\" src=\"https:\/\/www.wikitechy.com\/technology\/wp-content\/uploads\/2017\/06\/DLL0.png\" alt=\"Delete a node in a Doubly Linked List\" width=\"195\" height=\"112\" \/><\/p>\n<div id=\"practice\">\n<h4 id=\"algorithmlet-the-node-to-be-deleted-is-del-1-if-node-to-be-deleted-is-head-node-then-change-the-head-pointer-to-next-current-head-2-set-next-of-previous-to-del-if-previous-to-del-exixts-3-se\">Algorithm:<br \/>\nLet the node to be deleted is <em>del<\/em>.<br \/>\n1) If node to be deleted is head node, then change the head pointer to next current head.<br \/>\n2) Set <em>next <\/em>of previous to <em>del<\/em>, if previous to <em>del<\/em> exixts.<br \/>\n3) Set <em>prev <\/em>of next to <em>del<\/em>, if next to <em>del<\/em> exixts.<\/h4>\n[ad type=\u201dbanner\u201d]\n<p>Python Programming:<\/p>\n[pastacode lang=\u201dpython\u201d manual=\u201d%23%20Program%20to%20delete%20a%20node%20in%20doubly%20linked%20list%0A%20%0A%23%20for%20Garbage%20collection%0Aimport%20gc%0A%20%0A%23%20A%20node%20of%20the%20doublly%20linked%20list%0Aclass%20Node%3A%0A%20%20%20%20%20%0A%20%20%20%20%23%20Constructor%20to%20create%20a%20new%20node%0A%20%20%20%20def%20__init__(self%2C%20data)%3A%0A%20%20%20%20%20%20%20%20self.data%20%3D%20data%20%0A%20%20%20%20%20%20%20%20self.next%20%3D%20None%0A%20%20%20%20%20%20%20%20self.prev%20%3D%20None%0A%20%0Aclass%20DoublyLinkedList%3A%0A%20%20%20%20%20%23%20Constructor%20for%20empty%20Doubly%20Linked%20List%0A%20%20%20%20def%20__init__(self)%3A%0A%20%20%20%20%20%20%20%20self.head%20%3D%20None%0A%20%20%0A%20%20%20%23%20Function%20to%20delete%20a%20node%20in%20a%20Doubly%20Linked%20List.%0A%20%20%20%23%20head_ref%20\u2013%3E%20pointer%20to%20head%20node%20pointer.%0A%20%20%20%23%20dele%20\u2013%3E%20pointer%20to%20node%20to%20be%20deleted%0A%20%0A%20%20%20%20def%20deleteNode(self%2C%20dele)%3A%0A%20%20%20%20%20%20%20%20%20%0A%20%20%20%20%20%20%20%20%23%20Base%20Case%0A%20%20%20%20%20%20%20%20if%20self.head%20is%20None%20or%20dele%20is%20None%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20return%0A%20%20%20%20%20%20%20%20%20%0A%20%20%20%20%20%20%20%20%23%20If%20node%20to%20be%20deleted%20is%20head%20node%0A%20%20%20%20%20%20%20%20if%20self.head%20%3D%3D%20dele%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20self.head%20%3D%20dele.next%0A%20%0A%20%20%20%20%20%20%20%20%23%20Change%20next%20only%20if%20node%20to%20be%20deleted%20is%20NOT%0A%20%20%20%20%20%20%20%20%23%20the%20last%20node%0A%20%20%20%20%20%20%20%20if%20dele.next%20is%20not%20None%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20dele.next.prev%20%3D%20dele.prev%0A%20%20%20%20%20%0A%20%20%20%20%20%20%20%20%23%20Change%20prev%20only%20if%20node%20to%20be%20deleted%20is%20NOT%20%0A%20%20%20%20%20%20%20%20%23%20the%20first%20node%0A%20%20%20%20%20%20%20%20if%20dele.prev%20is%20not%20None%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20dele.prev.next%20%3D%20dele.next%0A%20%20%20%20%20%20%20%20%23%20Finally%2C%20free%20the%20memory%20occupied%20by%20dele%0A%20%20%20%20%20%20%20%20%23%20Call%20python%20garbage%20collector%0A%20%20%20%20%20%20%20%20gc.collect()%0A%20%0A%20%0A%20%20%20%20%23%20Given%20a%20reference%20to%20the%20head%20of%20a%20list%20and%20an%0A%20%20%20%20%23%20integer%2Cinserts%20a%20new%20node%20on%20the%20front%20of%20list%0A%20%20%20%20def%20push(self%2C%20new_data)%3A%0A%20%20%0A%20%20%20%20%20%20%20%20%23%201.%20Allocates%20node%0A%20%20%20%20%20%20%20%20%23%202.%20Put%20the%20data%20in%20it%0A%20%20%20%20%20%20%20%20new_node%20%3D%20Node(new_data)%0A%20%20%0A%20%20%20%20%20%20%20%20%23%203.%20Make%20next%20of%20new%20node%20as%20head%20and%0A%20%20%20%20%20%20%20%20%23%20previous%20as%20None%20(already%20None)%0A%20%20%20%20%20%20%20%20new_node.next%20%3D%20self.head%0A%20%20%0A%20%20%20%20%20%20%20%20%23%204.%20change%20prev%20of%20head%20node%20to%20new_node%0A%20%20%20%20%20%20%20%20if%20self.head%20is%20not%20None%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20self.head.prev%20%3D%20new_node%0A%20%20%0A%20%20%20%20%20%20%20%20%23%205.%20move%20the%20head%20to%20point%20to%20the%20new%20node%0A%20%20%20%20%20%20%20%20self.head%20%3D%20new_node%0A%20%0A%20%0A%20%20%20%20def%20printList(self%2C%20node)%3A%0A%20%20%20%20%20%20%20%20while(node%20is%20not%20None)%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20print%20node.data%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20node%20%3D%20node.next%0A%20%0A%20%0A%23%20Driver%20program%20to%20test%20the%20above%20functions%0A%20%0A%23%20Start%20with%20empty%20list%0Adll%20%3D%20DoublyLinkedList()%0A%20%0A%23%20Let%20us%20create%20the%20doubly%20linked%20list%2010%3C-%3E8%3C-%3E4%3C-%3E2%0Adll.push(2)%3B%0Adll.push(4)%3B%0Adll.push(8)%3B%0Adll.push(10)%3B%0A%20%0Aprint%20%22%5Cn%20Original%20Linked%20List%22%2C%0Adll.printList(dll.head)%0A%20%0A%23%20delete%20nodes%20from%20doubly%20linked%20list%0Adll.deleteNode(dll.head)%0Adll.deleteNode(dll.head.next)%0Adll.deleteNode(dll.head.next)%0A%23%20Modified%20linked%20list%20will%20be%20NULL%3C-8-%3ENULL%0Aprint%20%22%5Cn%20Modified%20Linked%20List%22%2C%0Adll.printList(dll.head)%0A%20\u2033 message=\u201d\u201d highlight=\u201d\u201d provider=\u201dmanual\u201d\/]\n<p>Time Complexity: O(1)<br \/>\nTime Complexity: O(1)<\/p>\n<\/div>\n<p>\u00a0<\/p>\n[ad type=\u201dbanner\u201d]\n","protected":false},"excerpt":{"rendered":"<p>Delete a node in a Doubly Linked List &#8211; Doubly Linked List &#8211; If node to be deleted is head node, then change the head pointer to next current head.<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[69969,79479,79476],"tags":[73376,81324,81321,81320,81323,81318,81322,81319],"class_list":["post-27339","post","type-post","status-publish","format-standard","hentry","category-algorithm","category-doubly-linked-list","category-linked-list","tag-algorithm-for-insertion-and-deletion-in-doubly-linked-list","tag-delete-all-nodes-in-doubly-linked-list","tag-delete-last-node-in-doubly-linked-list-in-c","tag-delete-node-from-doubly-linked-list-java","tag-doubly-linked-list-c-examples","tag-insertion-and-deletion-in-doubly-linked-list-in-c","tag-insertion-and-deletion-in-doubly-linked-list-in-data-structure","tag-write-a-function-to-delete-a-node-from-doubly-linked-list"],"_links":{"self":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/27339","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/comments?post=27339"}],"version-history":[{"count":0,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/27339\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/media?parent=27339"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/categories?post=27339"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/tags?post=27339"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}