{"id":26785,"date":"2017-12-24T15:27:52","date_gmt":"2017-12-24T09:57:52","guid":{"rendered":"https:\/\/www.wikitechy.com\/technology\/?p=26785"},"modified":"2017-12-24T15:40:17","modified_gmt":"2017-12-24T10:10:17","slug":"c-algorithm-deleting-node-linked-list","status":"publish","type":"post","link":"https:\/\/www.wikitechy.com\/technology\/c-algorithm-deleting-node-linked-list\/","title":{"rendered":"C++ Algorithm &#8211; Deleting a node in Linked List"},"content":{"rendered":"<p>We have discussed Linked List Introduction and Linked List Insertion in previous posts on singly linked list.<span id=\"more-142789\"><\/span><\/p>\n<p>Let us formulate the problem statement to understand the deletion process. <em>Given a \u2018key\u2019, delete the first occurrence of this key in linked list<\/em>.<br \/>\nTo delete a node from linked list, we need to do following steps.<br \/>\n1) Find previous node of the node to be deleted.<br \/>\n2) Changed next of previous node.<br \/>\n3) Free memory for the node to be deleted.<\/p>\n<p><img fetchpriority=\"high\" decoding=\"async\" class=\"alignleft size-full wp-image-26807\" src=\"https:\/\/www.wikitechy.com\/technology\/wp-content\/uploads\/2017\/06\/Linkedlist_deletion-2-1.png\" alt=\"Deleting a node in Linked List | Set 3\" width=\"759\" height=\"243\" srcset=\"https:\/\/www.wikitechy.com\/technology\/wp-content\/uploads\/2017\/06\/Linkedlist_deletion-2-1.png 759w, https:\/\/www.wikitechy.com\/technology\/wp-content\/uploads\/2017\/06\/Linkedlist_deletion-2-1-300x96.png 300w\" sizes=\"(max-width: 759px) 100vw, 759px\" \/><br \/>\nSince every node of linked list is dynamically allocated using malloc() in C, we need to call <a href=\"http:\/\/www.cplusplus.com\/reference\/cstdlib\/free\/\" target=\"_blank\" rel=\"noopener noreferrer\">free()<\/a> for freeing memory allocated for the node to be deleted.<\/p>\n<p><strong>C++ Programming:<\/strong><\/p>\n[pastacode lang=\u201dcpp\u201d manual=\u201d%2F%2F%20A%20complete%20working%20C%20program%20to%20demonstrate%20deletion%20in%20singly%0A%2F%2F%20linked%20list%0A%23include%20%3Cstdio.h%3E%0A%23include%20%3Cstdlib.h%3E%0A%20%0A%2F%2F%20A%20linked%20list%20node%0Astruct%20node%0A%7B%0A%20%20%20%20int%20data%3B%0A%20%20%20%20struct%20node%20*next%3B%0A%7D%3B%0A%20%0A%2F*%20Given%20a%20reference%20(pointer%20to%20pointer)%20to%20the%20head%20of%20a%20list%0A%20%20%20and%20an%20int%2C%20inserts%20a%20new%20node%20on%20the%20front%20of%20the%20list.%20*%2F%0Avoid%20push(struct%20node**%20head_ref%2C%20int%20new_data)%0A%7B%0A%20%20%20%20struct%20node*%20new_node%20%3D%20(struct%20node*)%20malloc(sizeof(struct%20node))%3B%0A%20%20%20%20new_node-%3Edata%20%20%3D%20new_data%3B%0A%20%20%20%20new_node-%3Enext%20%3D%20(*head_ref)%3B%0A%20%20%20%20(*head_ref)%20%20%20%20%3D%20new_node%3B%0A%7D%0A%20%0A%2F*%20Given%20a%20reference%20(pointer%20to%20pointer)%20to%20the%20head%20of%20a%20list%0A%20%20%20and%20a%20key%2C%20deletes%20the%20first%20occurrence%20of%20key%20in%20linked%20list%20*%2F%0Avoid%20deleteNode(struct%20node%20**head_ref%2C%20int%20key)%0A%7B%0A%20%20%20%20%2F%2F%20Store%20head%20node%0A%20%20%20%20struct%20node*%20temp%20%3D%20*head_ref%2C%20*prev%3B%0A%20%0A%20%20%20%20%2F%2F%20If%20head%20node%20itself%20holds%20the%20key%20to%20be%20deleted%0A%20%20%20%20if%20(temp%20!%3D%20NULL%20%26%26%20temp-%3Edata%20%3D%3D%20key)%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20*head_ref%20%3D%20temp-%3Enext%3B%20%20%20%2F%2F%20Changed%20head%0A%20%20%20%20%20%20%20%20free(temp)%3B%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%2F%2F%20free%20old%20head%0A%20%20%20%20%20%20%20%20return%3B%0A%20%20%20%20%7D%0A%20%0A%20%20%20%20%2F%2F%20Search%20for%20the%20key%20to%20be%20deleted%2C%20keep%20track%20of%20the%0A%20%20%20%20%2F%2F%20previous%20node%20as%20we%20need%20to%20change%20\u2019prev-%3Enext\u2019%0A%20%20%20%20while%20(temp%20!%3D%20NULL%20%26%26%20temp-%3Edata%20!%3D%20key)%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20prev%20%3D%20temp%3B%0A%20%20%20%20%20%20%20%20temp%20%3D%20temp-%3Enext%3B%0A%20%20%20%20%7D%0A%20%0A%20%20%20%20%2F%2F%20If%20key%20was%20not%20present%20in%20linked%20list%0A%20%20%20%20if%20(temp%20%3D%3D%20NULL)%20return%3B%0A%20%0A%20%20%20%20%2F%2F%20Unlink%20the%20node%20from%20linked%20list%0A%20%20%20%20prev-%3Enext%20%3D%20temp-%3Enext%3B%0A%20%0A%20%20%20%20free(temp)%3B%20%20%2F%2F%20Free%20memory%0A%7D%0A%20%0A%2F%2F%20This%20function%20prints%20contents%20of%20linked%20list%20starting%20from%20%0A%2F%2F%20the%20given%20node%0Avoid%20printList(struct%20node%20*node)%0A%7B%0A%20%20%20%20while%20(node%20!%3D%20NULL)%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20printf(%22%20%25d%20%22%2C%20node-%3Edata)%3B%0A%20%20%20%20%20%20%20%20node%20%3D%20node-%3Enext%3B%0A%20%20%20%20%7D%0A%7D%0A%20%0A%2F*%20Drier%20program%20to%20test%20above%20functions*%2F%0Aint%20main()%0A%7B%0A%20%20%20%20%2F*%20Start%20with%20the%20empty%20list%20*%2F%0A%20%20%20%20struct%20node*%20head%20%3D%20NULL%3B%0A%20%0A%20%20%20%20push(%26head%2C%207)%3B%0A%20%20%20%20push(%26head%2C%201)%3B%0A%20%20%20%20push(%26head%2C%203)%3B%0A%20%20%20%20push(%26head%2C%202)%3B%0A%20%0A%20%20%20%20puts(%22Created%20Linked%20List%3A%20%22)%3B%0A%20%20%20%20printList(head)%3B%0A%20%20%20%20deleteNode(%26head%2C%201)%3B%0A%20%20%20%20puts(%22%5CnLinked%20List%20after%20Deletion%20of%201%3A%20%22)%3B%0A%20%20%20%20printList(head)%3B%0A%20%20%20%20return%200%3B%0A%7D\u201d message=\u201d\u201d highlight=\u201d\u201d provider=\u201dmanual\u201d\/]\n<p><strong>Output<\/strong>:<\/p>\n<pre>Created Linked List:\r\n 2  3  1  7\r\nLinked List after Deletion of 1:\r\n 2  3  7<\/pre>\n[ad type=\u201dbanner\u201d]\n","protected":false},"excerpt":{"rendered":"<p>Cp++ Algorithm &#8211; Deleting a node in Linked List &#8211; Linked List &#8211; We have discussed Linked List Introduction and Linked List Insertion in previous<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[83515,79476,79478],"tags":[79924,79917,79920,79922,79925,79918,79914,79916,79919,79921,79915,79923],"class_list":["post-26785","post","type-post","status-publish","format-standard","hentry","category-c-programming-3","category-linked-list","category-singly-linked-list","tag-c-program-to-delete-first-node-in-linked-list","tag-delete-a-node-from-linked-list-algorithm","tag-delete-a-node-in-linked-list-with-single-pointer","tag-delete-a-node-in-singly-linked-list","tag-delete-a-node-in-the-middle-of-a-singly-linked-list","tag-delete-last-node-in-linked-list-in-c","tag-delete-node-at-given-position-in-a-linked-list","tag-delete-node-linked-list-c","tag-delete-specific-node-in-linked-list","tag-deletion-in-linked-list-in-data-structure","tag-linked-list-delete-node-java","tag-write-a-program-to-delete-a-node-from-linked-list-in-c"],"_links":{"self":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/26785","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=26785"}],"version-history":[{"count":0,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/26785\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/media?parent=26785"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/categories?post=26785"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/tags?post=26785"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}