{"id":27334,"date":"2018-01-20T20:59:16","date_gmt":"2018-01-20T15:29:16","guid":{"rendered":"https:\/\/www.wikitechy.com\/technology\/?p=27334"},"modified":"2018-01-20T20:59:41","modified_gmt":"2018-01-20T15:29:41","slug":"delete-a-node-in-a-doubly-linked-list-doubly-linked-list","status":"publish","type":"post","link":"https:\/\/www.wikitechy.com\/technology\/delete-a-node-in-a-doubly-linked-list-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<\/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-27277\" src=\"https:\/\/www.wikitechy.com\/technology\/wp-content\/uploads\/2017\/06\/DLL3.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.png 553w, https:\/\/www.wikitechy.com\/technology\/wp-content\/uploads\/2017\/06\/DLL3-300x61.png 300w, https:\/\/www.wikitechy.com\/technology\/wp-content\/uploads\/2017\/06\/DLL3-550x112.png 550w\" sizes=\"(max-width: 553px) 100vw, 553px\" \/><\/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<p>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.<\/p>\n[ad type=\u201dbanner\u201d]\n<p>Java Programming:<\/p>\n[pastacode lang=\u201djava\u201d manual=\u201d%2F%2F%20Java%20program%20to%20delete%20a%20node%20from%20doubly%20linked%20list%0A%20%0Aclass%20LinkedList%20%7B%0A%20%0A%20%20%20%20static%20Node%20head%20%3D%20null%3B%0A%20%0A%20%20%20%20class%20Node%20%7B%0A%20%0A%20%20%20%20%20%20%20%20int%20data%3B%0A%20%20%20%20%20%20%20%20Node%20next%2C%20prev%3B%0A%20%0A%20%20%20%20%20%20%20%20Node(int%20d)%20%7B%0A%20%20%20%20%20%20%20%20%20%20%20%20data%20%3D%20d%3B%0A%20%20%20%20%20%20%20%20%20%20%20%20next%20%3D%20prev%20%3D%20null%3B%0A%20%20%20%20%20%20%20%20%7D%0A%20%20%20%20%7D%0A%20%0A%20%20%20%20%2F*Function%20to%20delete%20a%20node%20in%20a%20Doubly%20Linked%20List.%0A%20%20%20%20head_ref%20\u2013%3E%20pointer%20to%20head%20node%20pointer.%0A%20%20%20%20del%20%20\u2013%3E%20%20pointer%20to%20node%20to%20be%20deleted.%20*%2F%0A%20%20%20%20void%20deleteNode(Node%20head_ref%2C%20Node%20del)%20%7B%0A%20%0A%20%20%20%20%20%20%20%20%2F*%20base%20case%20*%2F%0A%20%20%20%20%20%20%20%20if%20(head%20%3D%3D%20null%20%7C%7C%20del%20%3D%3D%20null)%20%7B%0A%20%20%20%20%20%20%20%20%20%20%20%20return%3B%0A%20%20%20%20%20%20%20%20%7D%0A%20%0A%20%20%20%20%20%20%20%20%2F*%20If%20node%20to%20be%20deleted%20is%20head%20node%20*%2F%0A%20%20%20%20%20%20%20%20if%20(head%20%3D%3D%20del)%20%7B%0A%20%20%20%20%20%20%20%20%20%20%20%20head%20%3D%20del.next%3B%0A%20%20%20%20%20%20%20%20%7D%0A%20%0A%20%20%20%20%20%20%20%20%2F*%20Change%20next%20only%20if%20node%20to%20be%20deleted%20is%20NOT%20the%20last%20node%20*%2F%0A%20%20%20%20%20%20%20%20if%20(del.next%20!%3D%20null)%20%7B%0A%20%20%20%20%20%20%20%20%20%20%20%20del.next.prev%20%3D%20del.prev%3B%0A%20%20%20%20%20%20%20%20%7D%0A%20%0A%20%20%20%20%20%20%20%20%2F*%20Change%20prev%20only%20if%20node%20to%20be%20deleted%20is%20NOT%20the%20first%20node%20*%2F%0A%20%20%20%20%20%20%20%20if%20(del.prev%20!%3D%20null)%20%7B%0A%20%20%20%20%20%20%20%20%20%20%20%20del.prev.next%20%3D%20del.next%3B%0A%20%20%20%20%20%20%20%20%7D%0A%20%0A%20%20%20%20%20%20%20%20%2F*%20Finally%2C%20free%20the%20memory%20occupied%20by%20del*%2F%0A%20%20%20%20%20%20%20%20return%3B%0A%20%20%20%20%7D%0A%20%0A%20%20%20%20%2F*%20UTILITY%20FUNCTIONS%20*%2F%0A%20%20%20%20%2F*%20Function%20to%20insert%20a%20node%20at%20the%20beginning%20of%20the%20Doubly%20Linked%20List%20*%2F%0A%20%20%20%20void%20push(Node%20head_ref%2C%20int%20new_data)%20%7B%0A%20%0A%20%20%20%20%20%20%20%20%2F*%20allocate%20node%20*%2F%0A%20%20%20%20%20%20%20%20Node%20new_node%20%3D%20new%20Node(new_data)%3B%0A%20%0A%20%20%20%20%20%20%20%20%2F*%20since%20we%20are%20adding%20at%20the%20begining%2C%0A%20%20%20%20%20%20%20%20%20prev%20is%20always%20NULL%20*%2F%0A%20%20%20%20%20%20%20%20new_node.prev%20%3D%20null%3B%0A%20%0A%20%20%20%20%20%20%20%20%2F*%20link%20the%20old%20list%20off%20the%20new%20node%20*%2F%0A%20%20%20%20%20%20%20%20new_node.next%20%3D%20(head)%3B%0A%20%0A%20%20%20%20%20%20%20%20%2F*%20change%20prev%20of%20head%20node%20to%20new%20node%20*%2F%0A%20%20%20%20%20%20%20%20if%20((head)%20!%3D%20null)%20%7B%0A%20%20%20%20%20%20%20%20%20%20%20%20(head).prev%20%3D%20new_node%3B%0A%20%20%20%20%20%20%20%20%7D%0A%20%0A%20%20%20%20%20%20%20%20%2F*%20move%20the%20head%20to%20point%20to%20the%20new%20node%20*%2F%0A%20%20%20%20%20%20%20%20(head)%20%3D%20new_node%3B%0A%20%20%20%20%7D%0A%20%0A%20%20%20%20%20%2F*Function%20to%20print%20nodes%20in%20a%20given%20doubly%20linked%20list%0A%20%20%20%20%20This%20function%20is%20same%20as%20printList()%20of%20singly%20linked%20lsit%20*%2F%0A%20%20%20%20void%20printList(Node%20node)%20%7B%0A%20%20%20%20%20%20%20%20while%20(node%20!%3D%20null)%20%7B%0A%20%20%20%20%20%20%20%20%20%20%20%20System.out.print(node.data%20%2B%20%22%20%22)%3B%0A%20%20%20%20%20%20%20%20%20%20%20%20node%20%3D%20node.next%3B%0A%20%20%20%20%20%20%20%20%7D%0A%20%20%20%20%7D%0A%20%0A%20%20%20%20public%20static%20void%20main(String%5B%5D%20args)%20%7B%0A%20%20%20%20%20%20%20%20LinkedList%20list%20%3D%20new%20LinkedList()%3B%0A%20%0A%20%20%20%20%20%20%20%20%2F*%20Let%20us%20create%20the%20doubly%20linked%20list%2010%3C-%3E8%3C-%3E4%3C-%3E2%20*%2F%0A%20%20%20%20%20%20%20%20list.push(head%2C%202)%3B%0A%20%20%20%20%20%20%20%20list.push(head%2C%204)%3B%0A%20%20%20%20%20%20%20%20list.push(head%2C%208)%3B%0A%20%20%20%20%20%20%20%20list.push(head%2C%2010)%3B%0A%20%0A%20%20%20%20%20%20%20%20System.out.println(%22Original%20Linked%20list%20%22)%3B%0A%20%20%20%20%20%20%20%20list.printList(head)%3B%0A%20%0A%20%20%20%20%20%20%20%20%2F*%20delete%20nodes%20from%20the%20doubly%20linked%20list%20*%2F%0A%20%20%20%20%20%20%20%20list.deleteNode(head%2C%20head)%3B%20%20%2F*delete%20first%20node*%2F%0A%20%0A%20%20%20%20%20%20%20%20list.deleteNode(head%2C%20head.next)%3B%20%20%2F*delete%20middle%20node*%2F%0A%20%0A%20%20%20%20%20%20%20%20list.deleteNode(head%2C%20head.next)%3B%20%20%2F*delete%20last%20node*%2F%0A%20%20%20%20%20%20%20%20System.out.println(%22%22)%3B%0A%20%0A%20%20%20%20%20%20%20%20%2F*%20Modified%20linked%20list%20will%20be%20NULL%3C-8-%3ENULL%20*%2F%0A%20%20%20%20%20%20%20%20System.out.println(%22Modified%20Linked%20List%22)%3B%0A%20%20%20%20%20%20%20%20list.printList(head)%3B%0A%20%20%20%20%7D%0A%7D\u201d message=\u201d\u201d highlight=\u201d\u201d provider=\u201dmanual\u201d\/]\n<p>Time Complexity: O(1)<br \/>\nTime Complexity: O(1)<\/p>\n<div id=\"company_tags\">\u00a0[ad type=\u201dbanner\u201d]<\/div>\n","protected":false},"excerpt":{"rendered":"<p>Delete a node in a 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":[79479,79476],"tags":[73376,81324,81321,81320,81323,81318,81322,81319],"class_list":["post-27334","post","type-post","status-publish","format-standard","hentry","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\/27334","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=27334"}],"version-history":[{"count":0,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/27334\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/media?parent=27334"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/categories?post=27334"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/tags?post=27334"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}