Write a C function that searches a given key ‘x’ in a given singly linked list. The function should return true if x is present in linked list and false otherwise.
bool search(Node *head, int x)
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.
Iterative Solution
2) Initialize a node pointer, current = head.
3) Do following while current is not NULL
a) current->key is equal to the key being searched return true.
b) current = current->next
4) Return false
C Programming:
[pastacode lang=”c” manual=”%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” message=”” highlight=”” provider=”manual”/] [ad type=”banner”]Output:
Yes
Recursive Solution
bool search(head, x) 1) If head is NULL, return false. 2) If head's key is same as x, return true; 2) Else return search(head->next, x)
C Programming:
[pastacode lang=”c” manual=”%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” message=”” highlight=”” provider=”manual”/] [ad type=”banner”]Output:
Yes