{"id":27573,"date":"2018-04-04T19:30:22","date_gmt":"2018-04-04T14:00:22","guid":{"rendered":"https:\/\/www.wikitechy.com\/technology\/?p=27573"},"modified":"2018-04-04T19:30:22","modified_gmt":"2018-04-04T14:00:22","slug":"cpp-algorithm-remove-duplicates-unsorted-linked-list","status":"publish","type":"post","link":"https:\/\/www.wikitechy.com\/technology\/cpp-algorithm-remove-duplicates-unsorted-linked-list\/","title":{"rendered":"Cpp Algorithm &#8211; Remove duplicates from an unsorted linked list"},"content":{"rendered":"<p>Write a removeDuplicates() function which takes a list and deletes any duplicate nodes from the list. The list is not sorted.<span id=\"more-5036\"><\/span><\/p>\n<p>For example if the linked list is 12->11->12->21->41->43->21 then removeDuplicates() should convert the list to 12->11->21->41->43.<\/p>\n<p><strong>METHOD 1 (Using two loops)<\/strong><br \/>\nThis is the simple way where two loops are used. Outer loop is used to pick the elements one by one and inner loop compares the picked element with rest of the elements.<\/p>\n<p><strong>C++ Programming:<\/strong><\/p>\n[pastacode lang=\u201dcpp\u201d manual=\u201d%2F*%20Program%20to%20remove%20duplicates%20in%20an%20unsorted%0A%20%20%20linked%20list%20*%2F%0A%23include%3Cbits%2Fstdc%2B%2B.h%3E%0Ausing%20namespace%20std%3B%0A%20%0A%2F*%20A%20linked%20list%20node%20*%2F%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%2F%20Utility%20function%20to%20create%20a%20new%20Node%0Astruct%20Node%20*newNode(int%20data)%0A%7B%0A%20%20%20Node%20*temp%20%3D%20new%20Node%3B%0A%20%20%20temp-%3Edata%20%3D%20data%3B%0A%20%20%20temp-%3Enext%20%3D%20NULL%3B%0A%20%20%20return%20temp%3B%0A%7D%0A%20%0A%2F*%20Function%20to%20remove%20duplicates%20from%20a%0A%20%20%20unsorted%20linked%20list%20*%2F%0Avoid%20removeDuplicates(struct%20Node%20*start)%0A%7B%0A%20%20%20%20struct%20Node%20*ptr1%2C%20*ptr2%2C%20*dup%3B%0A%20%20%20%20ptr1%20%3D%20start%3B%0A%20%0A%20%20%20%20%2F*%20Pick%20elements%20one%20by%20one%20*%2F%0A%20%20%20%20while%20(ptr1%20!%3D%20NULL%20%26%26%20ptr1-%3Enext%20!%3D%20NULL)%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20ptr2%20%3D%20ptr1%3B%0A%20%0A%20%20%20%20%20%20%20%20%2F*%20Compare%20the%20picked%20element%20with%20rest%0A%20%20%20%20%20%20%20%20%20%20%20of%20the%20elements%20*%2F%0A%20%20%20%20%20%20%20%20while%20(ptr2-%3Enext%20!%3D%20NULL)%0A%20%20%20%20%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%20%20%20%20%2F*%20If%20duplicate%20then%20delete%20it%20*%2F%0A%20%20%20%20%20%20%20%20%20%20%20%20if%20(ptr1-%3Edata%20%3D%3D%20ptr2-%3Enext-%3Edata)%0A%20%20%20%20%20%20%20%20%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%2F*%20sequence%20of%20steps%20is%20important%20here%20*%2F%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20dup%20%3D%20ptr2-%3Enext%3B%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20ptr2-%3Enext%20%3D%20ptr2-%3Enext-%3Enext%3B%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20delete(dup)%3B%0A%20%20%20%20%20%20%20%20%20%20%20%20%7D%0A%20%20%20%20%20%20%20%20%20%20%20%20else%20%2F*%20This%20is%20tricky%20*%2F%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20ptr2%20%3D%20ptr2-%3Enext%3B%0A%20%20%20%20%20%20%20%20%7D%0A%20%20%20%20%20%20%20%20ptr1%20%3D%20ptr1-%3Enext%3B%0A%20%20%20%20%7D%0A%7D%0A%20%0A%2F*%20Function%20to%20print%20nodes%20in%20a%20given%20linked%20list%20*%2F%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%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*%20Druver%20program%20to%20test%20above%20function%20*%2F%0Aint%20main()%0A%7B%0A%20%20%20%20%2F*%20The%20constructed%20linked%20list%20is%3A%0A%20%20%20%20%2010-%3E12-%3E11-%3E11-%3E12-%3E11-%3E10*%2F%0A%20%20%20%20struct%20Node%20*start%20%3D%20newNode(10)%3B%0A%20%20%20%20start-%3Enext%20%3D%20newNode(12)%3B%0A%20%20%20%20start-%3Enext-%3Enext%20%3D%20newNode(11)%3B%0A%20%20%20%20start-%3Enext-%3Enext-%3Enext%20%3D%20newNode(11)%3B%0A%20%20%20%20start-%3Enext-%3Enext-%3Enext-%3Enext%20%3D%20newNode(12)%3B%0A%20%20%20%20start-%3Enext-%3Enext-%3Enext-%3Enext-%3Enext%20%3D%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20newNode(11)%3B%0A%20%20%20%20start-%3Enext-%3Enext-%3Enext-%3Enext-%3Enext-%3Enext%20%3D%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20newNode(10)%3B%0A%20%0A%20%20%20%20printf(%22Linked%20list%20before%20removing%20duplicates%20%22)%3B%0A%20%20%20%20printList(start)%3B%0A%20%0A%20%20%20%20removeDuplicates(start)%3B%0A%20%0A%20%20%20%20printf(%22%5CnLinked%20list%20after%20removing%20duplicates%20%22)%3B%0A%20%20%20%20printList(start)%3B%0A%20%0A%20%20%20%20return%200%3B%0A%7D%0A\u201d message=\u201d\u201d highlight=\u201d\u201d provider=\u201dmanual\u201d\/]\n<p><strong>Output :<\/strong><\/p>\n<pre>Linked list before removing duplicates:\r\n 10 12 11 11 12 11 10 \r\nLinked list after removing duplicates:\r\n 10 12 11<\/pre>\n<p>Time Complexity: O(n^2)<\/p>\n<p><strong>METHOD 2 (Use Sorting)<\/strong><br \/>\nIn general, Merge Sort is the best suited sorting algorithm for sorting linked lists efficiently.<br \/>\n1) Sort the elements using Merge Sort. We will soon be writing a post about sorting a linked list. O(nLogn)<br \/>\n2) Remove duplicates in linear time using the algorithm for removing duplicates in sorted Linked List. O(n)<\/p>\n<p>Please note that this method doesn\u2019t preserve the original order of elements.<\/p>\n<p>Time Complexity: O(nLogn)<\/p>\n<p><strong>METHOD 3 (Use Hashing)<\/strong><br \/>\nWe traverse the link list from head to end. For every newly encountered element, we check whether it is in the hash table: if yes, we remove it; otherwise we put it in the hash table.<\/p>\n<p><strong>C++ Programming:<\/strong><\/p>\n[pastacode lang=\u201dcpp\u201d manual=\u201d%2F*%20Program%20to%20remove%20duplicates%20in%20an%20unsorted%0A%20%20%20linked%20list%20*%2F%0A%23include%3Cbits%2Fstdc%2B%2B.h%3E%0Ausing%20namespace%20std%3B%0A%20%0A%2F*%20A%20linked%20list%20node%20*%2F%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%2F%20Utility%20function%20to%20create%20a%20new%20Node%0Astruct%20Node%20*newNode(int%20data)%0A%7B%0A%20%20%20Node%20*temp%20%3D%20new%20Node%3B%0A%20%20%20temp-%3Edata%20%3D%20data%3B%0A%20%20%20temp-%3Enext%20%3D%20NULL%3B%0A%20%20%20return%20temp%3B%0A%7D%0A%20%0A%2F*%20Function%20to%20remove%20duplicates%20from%20a%0A%20%20%20unsorted%20linked%20list%20*%2F%0Avoid%20removeDuplicates(struct%20Node%20*start)%0A%7B%0A%20%20%20%20%2F%2F%20Hash%20to%20store%20seen%20values%0A%20%20%20%20unordered_set%3Cint%3E%20seen%3B%0A%20%0A%20%20%20%20%2F*%20Pick%20elements%20one%20by%20one%20*%2F%0A%20%20%20%20struct%20Node%20*curr%20%3D%20start%3B%0A%20%20%20%20struct%20Node%20*prev%20%3D%20NULL%3B%0A%20%20%20%20while%20(curr%20!%3D%20NULL)%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%2F%2F%20If%20current%20value%20is%20seen%20before%0A%20%20%20%20%20%20%20%20if%20(seen.find(curr-%3Edata)%20!%3D%20seen.end())%0A%20%20%20%20%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%20%20%20prev-%3Enext%20%3D%20curr-%3Enext%3B%0A%20%20%20%20%20%20%20%20%20%20%20delete%20(curr)%3B%0A%20%20%20%20%20%20%20%20%7D%0A%20%20%20%20%20%20%20%20else%0A%20%20%20%20%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%20%20%20seen.insert(curr-%3Edata)%3B%0A%20%20%20%20%20%20%20%20%20%20%20prev%20%3D%20curr%3B%0A%20%20%20%20%20%20%20%20%7D%0A%20%20%20%20%20%20%20%20curr%20%3D%20prev-%3Enext%3B%0A%20%20%20%20%7D%0A%7D%0A%20%0A%2F*%20Function%20to%20print%20nodes%20in%20a%20given%20linked%20list%20*%2F%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%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*%20Driver%20program%20to%20test%20above%20function%20*%2F%0Aint%20main()%0A%7B%0A%20%20%20%20%2F*%20The%20constructed%20linked%20list%20is%3A%0A%20%20%20%20%2010-%3E12-%3E11-%3E11-%3E12-%3E11-%3E10*%2F%0A%20%20%20%20struct%20Node%20*start%20%3D%20newNode(10)%3B%0A%20%20%20%20start-%3Enext%20%3D%20newNode(12)%3B%0A%20%20%20%20start-%3Enext-%3Enext%20%3D%20newNode(11)%3B%0A%20%20%20%20start-%3Enext-%3Enext-%3Enext%20%3D%20newNode(11)%3B%0A%20%20%20%20start-%3Enext-%3Enext-%3Enext-%3Enext%20%3D%20newNode(12)%3B%0A%20%20%20%20start-%3Enext-%3Enext-%3Enext-%3Enext-%3Enext%20%3D%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20newNode(11)%3B%0A%20%20%20%20start-%3Enext-%3Enext-%3Enext-%3Enext-%3Enext-%3Enext%20%3D%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20newNode(10)%3B%0A%20%0A%20%20%20%20printf(%22Linked%20list%20before%20removing%20duplicates%20%3A%20%5Cn%22)%3B%0A%20%20%20%20printList(start)%3B%0A%20%0A%20%20%20%20removeDuplicates(start)%3B%0A%20%0A%20%20%20%20printf(%22%5CnLinked%20list%20after%20removing%20duplicates%20%3A%20%5Cn%22)%3B%0A%20%20%20%20printList(start)%3B%0A%20%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>Linked list before removing duplicates:\r\n 10 12 11 11 12 11 10 \r\nLinked list after removing duplicates:\r\n 10 12 11<\/pre>\n<p>Time Complexity: O(n) on average (assuming that hash table access time is O(1) on average).<\/p>\n","protected":false},"excerpt":{"rendered":"<p>Cpp Algorithm &#8211; Remove duplicates from an unsorted linked list &#8211; Linked List &#8211; Write a removeDuplicates() function which takes a list and deletes <\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[79476,79478],"tags":[81763,81733,81764,81731,81727,81732,81766,81729,81728,81730,81765],"class_list":["post-27573","post","type-post","status-publish","format-standard","hentry","category-linked-list","category-singly-linked-list","tag-algorithm-to-remove-duplicate-elements-from-linked-list","tag-find-duplicates-in-linked-list-java","tag-implement-an-algorithm-to-find-the-nth-to-last-element-of-a-singly-linked-list","tag-remove-duplicates-from-an-unsorted-linked-list-using-hashing","tag-remove-duplicates-from-linked-list-java","tag-remove-duplicates-from-linked-list-python","tag-remove-duplicates-from-linked-list-without-buffer","tag-remove-duplicates-from-sorted-linked-list-c","tag-remove-duplicates-from-sorted-linked-list-java","tag-remove-duplicates-from-sorted-list-ii","tag-remove-duplicates-from-sorted-list-java"],"_links":{"self":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/27573","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=27573"}],"version-history":[{"count":0,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/27573\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/media?parent=27573"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/categories?post=27573"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/tags?post=27573"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}