{"id":26916,"date":"2017-12-26T21:17:37","date_gmt":"2017-12-26T15:47:37","guid":{"rendered":"https:\/\/www.wikitechy.com\/technology\/?p=26916"},"modified":"2017-12-26T21:17:37","modified_gmt":"2017-12-26T15:47:37","slug":"c-algorithm-search-element-linked-list-iterative-recursive","status":"publish","type":"post","link":"https:\/\/www.wikitechy.com\/technology\/c-algorithm-search-element-linked-list-iterative-recursive\/","title":{"rendered":"C Algorithm &#8211; Search an element in a Linked List both Iterative and Recursive"},"content":{"rendered":"<p>Write a C function that searches a given key \u2018x\u2019 in a given singly linked list. The function should return true if x is present in linked list and false otherwise.<span id=\"more-142794\"><\/span><\/p>\n<pre>   bool search(Node *head, int x)<\/pre>\n<p>For example, if the key to be searched is 15 and linked list is 14->21->11->30->10, then function should return false. If key to be searched is 14, then the function should return true.<\/p>\n<p><strong>Iterative Solution<\/strong><\/p>\n<pre>2) Initialize a node pointer, current = head.\r\n3) Do following while current is not NULL\r\n    a) current->key is equal to the key being searched return true.\r\n    b) current = current->next\r\n4) Return false<\/pre>\n<p><strong>C Programming:<\/strong><\/p>\n[pastacode lang=\u201dc\u201d manual=\u201d%2F%2F%20Iterative%20C%20program%20to%20search%20an%20element%20in%20linked%20list%0A%23include%3Cstdio.h%3E%0A%23include%3Cstdlib.h%3E%0A%20%0A%2F*%20Link%20list%20node%20*%2F%0Astruct%20node%0A%7B%0A%20%20%20%20int%20key%3B%0A%20%20%20%20struct%20node*%20next%3B%0A%7D%3B%0A%20%0A%2F*%20Given%20a%20reference%20(pointer%20to%20pointer)%20to%20the%20head%0A%20%20of%20a%20list%20and%20an%20int%2C%20push%20a%20new%20node%20on%20the%20front%0A%20%20of%20the%20list.%20*%2F%0Avoid%20push(struct%20node**%20head_ref%2C%20int%20new_key)%0A%7B%0A%20%20%20%20%2F*%20allocate%20node%20*%2F%0A%20%20%20%20struct%20node*%20new_node%20%3D%0A%20%20%20%20%20%20%20%20%20%20%20%20(struct%20node*)%20malloc(sizeof(struct%20node))%3B%0A%20%0A%20%20%20%20%2F*%20put%20in%20the%20key%20%20*%2F%0A%20%20%20%20new_node-%3Ekey%20%20%3D%20new_key%3B%0A%20%0A%20%20%20%20%2F*%20link%20the%20old%20list%20off%20the%20new%20node%20*%2F%0A%20%20%20%20new_node-%3Enext%20%3D%20(*head_ref)%3B%0A%20%0A%20%20%20%20%2F*%20move%20the%20head%20to%20point%20to%20the%20new%20node%20*%2F%0A%20%20%20%20(*head_ref)%20%20%20%20%3D%20new_node%3B%0A%7D%0A%20%0A%2F*%20Checks%20whether%20the%20value%20x%20is%20present%20in%20linked%20list%20*%2F%0Abool%20search(struct%20node*%20head%2C%20int%20x)%0A%7B%0A%20%20%20%20struct%20node*%20current%20%3D%20head%3B%20%20%2F%2F%20Initialize%20current%0A%20%20%20%20while%20(current%20!%3D%20NULL)%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20if%20(current-%3Ekey%20%3D%3D%20x)%0A%20%20%20%20%20%20%20%20%20%20%20%20return%20true%3B%0A%20%20%20%20%20%20%20%20current%20%3D%20current-%3Enext%3B%0A%20%20%20%20%7D%0A%20%20%20%20return%20false%3B%0A%7D%0A%20%0A%2F*%20Driver%20program%20to%20test%20count%20function*%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%20%20%20int%20x%20%3D%2021%3B%0A%20%0A%20%20%20%20%2F*%20Use%20push()%20to%20construct%20below%20list%0A%20%20%20%20%2014-%3E21-%3E11-%3E30-%3E10%20%20*%2F%0A%20%20%20%20push(%26head%2C%2010)%3B%0A%20%20%20%20push(%26head%2C%2030)%3B%0A%20%20%20%20push(%26head%2C%2011)%3B%0A%20%20%20%20push(%26head%2C%2021)%3B%0A%20%20%20%20push(%26head%2C%2014)%3B%0A%20%0A%20%20%20%20search(head%2C%2021)%3F%20printf(%22Yes%22)%20%3A%20printf(%22No%22)%3B%0A%20%20%20%20return%200%3B%0A%7D\u201d message=\u201d\u201d highlight=\u201d\u201d provider=\u201dmanual\u201d\/]\n[ad type=\u201dbanner\u201d]\n<p><strong>Output:<\/strong><\/p>\n<pre>Yes<\/pre>\n<p><strong>Recursive Solution<\/strong><\/p>\n<pre><strong>bool search(head, x)<\/strong>\r\n1) If head is NULL, return false.\r\n2) If head's key is same as x, return true;\r\n2) Else return search(head->next, x)<\/pre>\n<p><strong>C Programming:<\/strong><\/p>\n[pastacode lang=\u201dc\u201d manual=\u201d%2F%2F%20Recursive%20C%20program%20to%20search%20an%20element%20in%20linked%20list%0A%23include%3Cstdio.h%3E%0A%23include%3Cstdlib.h%3E%0A%20%0A%2F*%20Link%20list%20node%20*%2F%0Astruct%20node%0A%7B%0A%20%20%20%20int%20key%3B%0A%20%20%20%20struct%20node*%20next%3B%0A%7D%3B%0A%20%0A%2F*%20Given%20a%20reference%20(pointer%20to%20pointer)%20to%20the%20head%0A%20%20of%20a%20list%20and%20an%20int%2C%20push%20a%20new%20node%20on%20the%20front%0A%20%20of%20the%20list.%20*%2F%0Avoid%20push(struct%20node**%20head_ref%2C%20int%20new_key)%0A%7B%0A%20%20%20%20%2F*%20allocate%20node%20*%2F%0A%20%20%20%20struct%20node*%20new_node%20%3D%0A%20%20%20%20%20%20%20%20%20%20%20%20(struct%20node*)%20malloc(sizeof(struct%20node))%3B%0A%20%0A%20%20%20%20%2F*%20put%20in%20the%20key%20%20*%2F%0A%20%20%20%20new_node-%3Ekey%20%20%3D%20new_key%3B%0A%20%0A%20%20%20%20%2F*%20link%20the%20old%20list%20off%20the%20new%20node%20*%2F%0A%20%20%20%20new_node-%3Enext%20%3D%20(*head_ref)%3B%0A%20%0A%20%20%20%20%2F*%20move%20the%20head%20to%20point%20to%20the%20new%20node%20*%2F%0A%20%20%20%20(*head_ref)%20%20%20%20%3D%20new_node%3B%0A%7D%0A%20%0A%2F*%20Checks%20whether%20the%20value%20x%20is%20present%20in%20linked%20list%20*%2F%0Abool%20search(struct%20node*%20head%2C%20int%20x)%0A%7B%0A%20%20%20%20%2F%2F%20Base%20case%0A%20%20%20%20if%20(head%20%3D%3D%20NULL)%0A%20%20%20%20%20%20%20%20return%20false%3B%0A%20%20%20%20%20%0A%20%20%20%20%2F%2F%20If%20key%20is%20present%20in%20current%20node%2C%20return%20true%0A%20%20%20%20if%20(head-%3Ekey%20%3D%3D%20x)%0A%20%20%20%20%20%20%20%20return%20true%3B%0A%20%0A%20%20%20%20%2F%2F%20Recur%20for%20remaining%20list%0A%20%20%20%20return%20search(head-%3Enext%2C%20x)%3B%0A%7D%0A%20%0A%2F*%20Driver%20program%20to%20test%20count%20function*%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%20%20%20int%20x%20%3D%2021%3B%0A%20%0A%20%20%20%20%2F*%20Use%20push()%20to%20construct%20below%20list%0A%20%20%20%20%2014-%3E21-%3E11-%3E30-%3E10%20%20*%2F%0A%20%20%20%20push(%26head%2C%2010)%3B%0A%20%20%20%20push(%26head%2C%2030)%3B%0A%20%20%20%20push(%26head%2C%2011)%3B%0A%20%20%20%20push(%26head%2C%2021)%3B%0A%20%20%20%20push(%26head%2C%2014)%3B%0A%20%0A%20%20%20%20search(head%2C%2021)%3F%20printf(%22Yes%22)%20%3A%20printf(%22No%22)%3B%0A%20%20%20%20return%200%3B%0A%7D\u201d message=\u201d\u201d highlight=\u201d\u201d provider=\u201dmanual\u201d\/]\n[ad type=\u201dbanner\u201d]\n<p><strong>Output:<\/strong><\/p>\n<pre>Yes<\/pre>\n","protected":false},"excerpt":{"rendered":"<p>C Algorithm &#8211; Search an element in a Linked List both Iterative and Recursive &#8211;  Linked List &#8211; Write a C function that searches a given key \u2018x\u2019 in a given<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[69866,1,79476,79478],"tags":[80299,80286,80289,80291,80290,80292,80298,80296,80294,80300,80293,80295,80297,80288,80287,80285],"class_list":["post-26916","post","type-post","status-publish","format-standard","hentry","category-c-programming","category-coding","category-linked-list","category-singly-linked-list","tag-algorithm-to-reverse-a-linked-list-in-data-structure","tag-algorithm-to-search-an-element-in-singly-linked-list","tag-binary-search-using-linked-list","tag-find-the-length-of-the-linked-list-using-recursion","tag-linked-list-recursion-c","tag-linked-list-recursion-java","tag-reverse-a-linked-list-algorithm","tag-reverse-a-linked-list-c","tag-reverse-a-linked-list-java","tag-reverse-a-linked-list-recursively-c","tag-reverse-a-linked-list-using-recursion-in-c","tag-reverse-a-singly-linked-list","tag-reverse-linked-list-recursive-java","tag-search-an-element-in-doubly-linked-list","tag-search-linked-list-complexity","tag-searching-in-linked-list-algorithm"],"_links":{"self":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/26916","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=26916"}],"version-history":[{"count":0,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/26916\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/media?parent=26916"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/categories?post=26916"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/tags?post=26916"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}