Write a 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:
1) Initialize a node pointer, current = head.
2) Do following while current is not NULL
a) current->key is equal to the key being searched return true.
b) current = current->next
3) Return false
Following is iterative implementation of above algorithm to search a given key.
Python
# Iterative Python program to search # an element in linked list# Node classclass Node: # Function to initialise the # node object def __init__(self, data): # Assign data self.data = data # Initialize next as null self.next = None# Linked List classclass LinkedList: def __init__(self): # Initialize head as None self.head = None # This function insert a new node at the # beginning of the linked list def push(self, new_data): # Create a new Node new_node = Node(new_data) # 3. Make next of new Node as head new_node.next = self.head # 4. Move the head to point to new Node self.head = new_node # This Function checks whether the value # x present in the linked list def search(self, x): # Initialize current to head current = self.head # Loop till current not equal to None while current != None: if current.data == x: # Data found return True current = current.next # Data Not found return False# Driver codeif __name__ == '__main__': # Start with the empty list llist = LinkedList() # Use push() to construct list # 14->21->11->30->10 llist.push(10); llist.push(30); llist.push(11); llist.push(21); llist.push(14); if llist.search(21): print("Yes") else: print("No")# This code is contributed by Ravi Shankar |
Output:
Yes
Time Complexity: O(n), where n represents the length of the given linked list.
Auxiliary Space: O(1), no extra space is required, so it is a constant.
Recursive Solution:
bool search(head, x) 1) If head is NULL, return false. 2) If head's key is same as x, return true; 3) Else return search(head->next, x)
Following is the recursive implementation of the above algorithm to search a given key.
Python
# Recursive Python program to # search an element in linked list# Node classclass Node: # Function to initialize # the node object def __init__(self, data): # Assign data self.data = data # Initialize next as null self.next = Noneclass LinkedList: def __init__(self): # Initialize head as None self.head = None # This function insert a new node at # the beginning of the linked list def push(self, new_data): # Create a new Node new_node = Node(new_data) # Make next of new Node as head new_node.next = self.head # Move the head to # point to new Node self.head = new_node # Checks whether the value key # is present in linked list def search(self, li, key): # Base case if(not li): return False # If key is present in # current node, return true if(li.data == key): return True # Recur for remaining list return self.search(li.next, key) # Driver Code if __name__=='__main__': li = LinkedList() li.push(1) li.push(2) li.push(3) li.push(4) key = 4 if li.search(li.head,key): print("Yes") else: print("No")# This code is contributed by Manoj Sharma |
Output:
Yes
Time Complexity: O(n), where n represents the length of the given linked list.
Auxiliary Space: O(n), for recursive call stack where n represents the length of the given linked list.
Please refer complete article on Search an element in a Linked List (Iterative and Recursive) for more details!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
