Search an element in a Linked List (Iterative and Recursive)
Given a linked list and a key ‘X‘ in, the task is to check if X is present in the linked list or not.
Examples:
Input: 14->21->11->30->10, X = 14
Output: Yes
Explanation: 14 is present in the linked list.Input: 6->21->17->30->10->8, X = 13
Output: No
Using O(N) Extra Space.
The Approach:
In this approach we use vector where we store all the nodes value in the vector and then check whether there is key present in vector then it will return 1.
C++
#include <bits/stdc++.h> using namespace std; /* Link list node */ class Node { public : int key; Node* next; }; /* Given a reference (pointer to pointer) to the head of a list and an int, push a new node on the front of the list. */ void push(Node** head_ref, int new_key) { /* allocate node */ Node* new_node = new Node(); /* put in the key */ new_node->key = new_key; /* link the old list of the new node */ new_node->next = (*head_ref); /* move the head to point to the new node */ (*head_ref) = new_node; } int main() { /* Start with the empty list */ Node* head = NULL; int x = 21; /* Use push() to construct below list 14->21->11->30->10 */ push(&head, 10); push(&head, 30); push(&head, 11); push(&head, 21); push(&head, 14); vector< int >v; //we donot use given data Node* temp=head; while (temp!=NULL){ v.push_back(temp->key); temp=temp->next; } // we use iterator to find. vector< int >::iterator it; find(v.begin(),v.end(),x); if (it==v.end()){ cout<< "NO" <<endl; } else { cout<< "YES" <<endl; } return 0; } |
Java
import java.util.*; class Node { int key; Node next; Node( int key) { this .key = key; this .next = null ; } } class Main { // Given a reference (pointer to pointer) to the head // of a list and an int, push a new node on the front of the list. static void push(Node[] head_ref, int new_key) { Node new_node = new Node(new_key); new_node.next = head_ref[ 0 ]; head_ref[ 0 ] = new_node; } public static void main(String[] args) { Node[] head = new Node[ 1 ]; int x = 21 ; // Use push() to construct below list 14->21->11->30->10 push(head, 10 ); push(head, 30 ); push(head, 11 ); push(head, 21 ); push(head, 14 ); // Create a vector of integers from the linked list and search for the value x in the vector using an iterator. Vector<Integer> v = new Vector<Integer>(); Node temp = head[ 0 ]; while (temp != null ) { v.add(temp.key); temp = temp.next; } int it = v.indexOf(x); if (it == - 1 ) { System.out.println( "NO" ); } else { System.out.println( "YES" ); } } } |
Python3
# Class definition for Node class Node: # Initialize the node with a key def __init__( self , key): self .key = key self . next = None # Class definition for Linked List class LinkedList: # Initialize the linked list with a head node def __init__( self ): self .head = None # Add a new node with key "new_key" at the beginning of the linked list def push( self , new_key): new_node = Node(new_key) new_node. next = self .head self .head = new_node # Create a linked list object llist = LinkedList() # Add new nodes to the linked list llist.push( 10 ) llist.push( 30 ) llist.push( 11 ) llist.push( 21 ) llist.push( 14 ) # Key to search for in the linked list x = 21 # Create a temp variable to traverse the linked list temp = llist.head # List to store the keys in the linked list v = [] # Traverse the linked list and store the keys in the list "v" while (temp): v.append(temp.key) temp = temp. next # Check if "x" is in the list "v" if x in v: print ( "YES" ) else : print ( "NO" ) |
C#
using System; using System.Collections.Generic; using System.Linq; /* Link list node */ class Node { public int key; public Node next; }; class Program { /* Given a reference (pointer to pointer) to the head of a list and an int, push a new node on the front of the list. */ static void push( ref Node head_ref, int new_key) { /* allocate node */ Node new_node = new Node(); /* put in the key */ new_node.key = new_key; /* link the old list of the new node */ new_node.next = head_ref; /* move the head to point to the new node */ head_ref = new_node; } static void Main( string [] args) { /* Start with the empty list */ Node head = null ; int x = 21; /* Use push() to construct below list 14->21->11->30->10 */ push( ref head, 10); push( ref head, 30); push( ref head, 11); push( ref head, 21); push( ref head, 14); List< int > v = new List< int >(); Node temp = head; while (temp != null ) { v.Add(temp.key); temp = temp.next; } /* Find whether x is present in the list or not */ if (v.Contains(x)) { Console.WriteLine( "YES" ); } else { Console.WriteLine( "NO" ); } } } // This code is contributed by sarojmcy2e |
Javascript
// Class definition for Node class Node { // Initialize the node with a key constructor(key) { this .key = key; this .next = null ; } } // Class definition for Linked List class LinkedList { // Initialize the linked list with a head node constructor() { this .head = null ; } // Add a new node with key "new_key" at the beginning of the linked list push(new_key) { let new_node = new Node(new_key); new_node.next = this .head; this .head = new_node; } } // Create a linked list object let llist = new LinkedList(); // Add new nodes to the linked list llist.push(10); llist.push(30); llist.push(11); llist.push(21); llist.push(14); // Key to search for in the linked list let x = 22; // Create a temp variable to traverse the linked list let temp = llist.head; // Array to store the keys in the linked list let v = []; // Traverse the linked list and store the keys in the array "v" while (temp) { v.push(temp.key); temp = temp.next; } // Check if "x" is in the array "v" if (v.includes(x)) { console.log( "YES" ); } else { console.log( "NO" ); } |
YES
Time Complexity: O(N), to traverse linked list.
Auxiliary Space: O(N),to store the values.
Search an element in a Linked List (Iterative Approach):
Follow the below steps to solve the problem:
- Initialize a node pointer, current = head.
- Do following while current is not NULL
- If the current value (i.e., current->key) is equal to the key being searched return true.
- Otherwise, move to the next node (current = current->next).
- If the key is not found, return false
Below is the implementation of the above approach.
C++
// Iterative C++ program to search // an element in linked list #include <bits/stdc++.h> using namespace std; /* Link list node */ class Node { public : int key; Node* next; }; /* Given a reference (pointer to pointer) to the head of a list and an int, push a new node on the front of the list. */ void push(Node** head_ref, int new_key) { /* allocate node */ Node* new_node = new Node(); /* put in the key */ new_node->key = new_key; /* link the old list of the new node */ new_node->next = (*head_ref); /* move the head to point to the new node */ (*head_ref) = new_node; } /* Checks whether the value x is present in linked list */ bool search(Node* head, int x) { Node* current = head; // Initialize current while (current != NULL) { if (current->key == x) return true ; current = current->next; } return false ; } /* Driver code*/ int main() { /* Start with the empty list */ Node* head = NULL; int x = 21; /* Use push() to construct below list 14->21->11->30->10 */ push(&head, 10); push(&head, 30); push(&head, 11); push(&head, 21); push(&head, 14); // Function call search(head, x) ? cout << "Yes" : cout << "No" ; return 0; } // This is code is contributed by rathbhupendra |
C
// Iterative C program to search an element // in the linked list #include <stdbool.h> #include <stdio.h> #include <stdlib.h> /* Link list node */ struct Node { int key; struct Node* next; }; /* Given a reference (pointer to pointer) to the head of a list and an int, push a new node on the front of the list. */ void push( struct Node** head_ref, int new_key) { /* allocate node */ struct Node* new_node = ( struct Node*) malloc ( sizeof ( struct Node)); /* put in the key */ new_node->key = new_key; /* link the old list of the new node */ new_node->next = (*head_ref); /* move the head to point to the new node */ (*head_ref) = new_node; } /* Checks whether the value x is present in linked list */ bool search( struct Node* head, int x) { struct Node* current = head; // Initialize current while (current != NULL) { if (current->key == x) return true ; current = current->next; } return false ; } /* Driver code*/ int main() { /* Start with the empty list */ struct Node* head = NULL; int x = 21; /* Use push() to construct below list 14->21->11->30->10 */ push(&head, 10); push(&head, 30); push(&head, 11); push(&head, 21); push(&head, 14); // Function call search(head, x) ? printf ( "Yes" ) : printf ( "No" ); return 0; } |
Java
// Iterative Java program to search an element // in linked list // Linked list class class LinkedList { Node head; // Head of list // Inserts a new node at the front of the list public void push( int new_data) { // Allocate new node and putting data Node new_node = new Node(new_data); // Make next of new node as head new_node.next = head; // Move the head to point to new Node head = new_node; } // Checks whether the value x is present in linked list public boolean search(Node head, int x) { Node current = head; // Initialize current while (current != null ) { if (current.data == x) return true ; // data found current = current.next; } return false ; // data not found } // Driver code public static void main(String args[]) { // Start with the empty list LinkedList llist = new LinkedList(); int x = 21 ; /*Use push() to construct below list 14->21->11->30->10 */ llist.push( 10 ); llist.push( 30 ); llist.push( 11 ); llist.push( 21 ); llist.push( 14 ); // Function call if (llist.search(llist.head, x)) System.out.println( "Yes" ); else System.out.println( "No" ); } } // Node class class Node { int data; Node next; Node( int d) { data = d; next = null ; } } // This code is contributed by Pratik Agarwal |
Python3
# Iterative Python3 program to search an element # in linked list # Node class class Node: # Function to initialise the node object def __init__( self , data): self .data = data # Assign data self . next = None # Initialize next as null # Linked List class class LinkedList: def __init__( self ): self .head = None # Initialize head as 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: return True # data found current = current. next return False # Data Not found # Driver code if __name__ = = '__main__' : # Start with the empty list llist = LinkedList() x = 21 ''' Use push() to construct below list 14->21->11->30->10 ''' llist.push( 10 ) llist.push( 30 ) llist.push( 11 ) llist.push( 21 ) llist.push( 14 ) # Function call if llist.search(x): print ( "Yes" ) else : print ( "No" ) # This code is contributed by Ravi Shankar |
C#
// Iterative C# program to search an element // in linked list using System; // Node class public class Node { public int data; public Node next; public Node( int d) { data = d; next = null ; } } // Linked list class public class LinkedList { Node head; // Head of list // Inserts a new node at the front of the list public void push( int new_data) { // Allocate new node and putting data Node new_node = new Node(new_data); // Make next of new node as head new_node.next = head; // Move the head to point to new Node head = new_node; } // Checks whether the value x is present in linked list public bool search(Node head, int x) { Node current = head; // Initialize current while (current != null ) { if (current.data == x) return true ; // data found current = current.next; } return false ; // data not found } // Driver code public static void Main(String[] args) { // Start with the empty list LinkedList llist = new LinkedList(); /*Use push() to construct below list 14->21->11->30->10 */ llist.push(10); llist.push(30); llist.push(11); llist.push(21); llist.push(14); int x = 21; // Function call if (llist.search(llist.head, x)) Console.WriteLine( "Yes" ); else Console.WriteLine( "No" ); } } // This code contributed by Rajput-Ji |
Javascript
// Iterative javascript program // to search an element // in linked list //Node class class Node { constructor(d) { this .data = d; this .next = null ; } } // Linked list class var head; // Head of list // Inserts a new node at the front of the list function push(new_data) { // Allocate new node and putting data var new_node = new Node(new_data); // Make next of new node as head new_node.next = head; // Move the head to point to new Node head = new_node; } // Checks whether the value // x is present in linked list function search( head , x) { var current = head; // Initialize current while (current != null ) { if (current.data == x) return true ; // data found current = current.next; } return false ; // data not found } // Driver function to test // the above functions // Start with the empty list /* Use push() to construct below list 14->21->11->30->10 */ push(10); push(30); push(11); push(21); push(14); var x = 21; if (search(head, x)) document.write( "Yes" ); else document.write( "No" ); // This code contributed by aashish1995 |
Yes
Time Complexity: O(N), Where N is the number of nodes in the LinkedList
Auxiliary Space: O(1)
Search an element in a Linked List (Recursive Approach):
Follow the below steps to solve the problem:
- If the head is NULL, return false.
- If the head’s key is the same as X, return true;
- Else recursively search in the next node.
Below is the recursive implementation of the above algorithm.
C++
// Recursive C++ program to search // an element in linked list #include <bits/stdc++.h> using namespace std; /* Link list node */ struct Node { int key; struct Node* next; }; /* Given a reference (pointer to pointer) to the head of a list and an int, push a new node on the front of the list. */ void push( struct Node** head_ref, int new_key) { /* allocate node */ struct Node* new_node = ( struct Node*) malloc ( sizeof ( struct Node)); /* put in the key */ new_node->key = new_key; /* link the old list of the new node */ new_node->next = (*head_ref); /* move the head to point to the new node */ (*head_ref) = new_node; } /* Checks whether the value x is present in linked list */ bool search( struct Node* head, int x) { // Base case if (head == NULL) return false ; // If key is present in current node, return true if (head->key == x) return true ; // Recur for remaining list return search(head->next, x); } /* Driver code*/ int main() { /* Start with the empty list */ struct Node* head = NULL; int x = 21; /* Use push() to construct below list 14->21->11->30->10 */ push(&head, 10); push(&head, 30); push(&head, 11); push(&head, 21); push(&head, 14); // Function call search(head, x) ? cout << "Yes" : cout << "No" ; return 0; } // This code is contributed by SHUBHAMSINGH10 |
C
// Recursive C program to search an element in linked list #include <stdbool.h> #include <stdio.h> #include <stdlib.h> /* Link list node */ struct Node { int key; struct Node* next; }; /* Given a reference (pointer to pointer) to the head of a list and an int, push a new node on the front of the list. */ void push( struct Node** head_ref, int new_key) { /* allocate node */ struct Node* new_node = ( struct Node*) malloc ( sizeof ( struct Node)); /* put in the key */ new_node->key = new_key; /* link the old list of the new node */ new_node->next = (*head_ref); /* move the head to point to the new node */ (*head_ref) = new_node; } /* Checks whether the value x is present in linked list */ bool search( struct Node* head, int x) { // Base case if (head == NULL) return false ; // If key is present in current node, return true if (head->key == x) return true ; // Recur for remaining list return search(head->next, x); } /* Driver code*/ int main() { /* Start with the empty list */ struct Node* head = NULL; int x = 21; /* Use push() to construct below list 14->21->11->30->10 */ push(&head, 10); push(&head, 30); push(&head, 11); push(&head, 21); push(&head, 14); // Function call search(head, x) ? printf ( "Yes" ) : printf ( "No" ); return 0; } |
Java
// Recursive Java program to search an element // in the linked list // Linked list class class LinkedList { Node head; // Head of list // Inserts a new node at the front of the list public void push( int new_data) { // Allocate new node and putting data Node new_node = new Node(new_data); // Make next of new node as head new_node.next = head; // Move the head to point to new Node head = new_node; } // Checks whether the value x is present // in linked list public boolean search(Node head, int x) { // Base case if (head == null ) return false ; // If key is present in current node, // return true if (head.data == x) return true ; // Recur for remaining list return search(head.next, x); } // Driver code public static void main(String args[]) { // Start with the empty list LinkedList llist = new LinkedList(); /* Use push() to construct below list 14->21->11->30->10 */ llist.push( 10 ); llist.push( 30 ); llist.push( 11 ); llist.push( 21 ); llist.push( 14 ); int x = 21 ; // Function call if (llist.search(llist.head, x)) System.out.println( "Yes" ); else System.out.println( "No" ); } } // Node class class Node { int data; Node next; Node( int d) { data = d; next = null ; } } // This code is contributed by Pratik Agarwal |
Python3
# Recursive Python program to # search an element in linked list # Node class class Node: # Function to initialise # the node object def __init__( self , data): self .data = data # Assign data self . next = None # Initialize next as null class LinkedList: def __init__( self ): self .head = None # Initialize head as 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( 10 ) li.push( 30 ) li.push( 11 ) li.push( 21 ) li.push( 14 ) x = 21 # Function call if li.search(li.head, x): print ( "Yes" ) else : print ( "No" ) # This code is contributed # by Manoj Sharma |
C#
// Recursive C# program to search // an element in linked list using System; // Node class public class Node { public int data; public Node next; public Node( int d) { data = d; next = null ; } } // Linked list class public class LinkedList { Node head; // Head of list // Inserts a new node at the front of the list public void push( int new_data) { // Allocate new node and putting data Node new_node = new Node(new_data); // Make next of new node as head new_node.next = head; // Move the head to point to new Node head = new_node; } // Checks whether the value x is present // in linked list public bool search(Node head, int x) { // Base case if (head == null ) return false ; // If key is present in current node, // return true if (head.data == x) return true ; // Recur for remaining list return search(head.next, x); } // Driver code public static void Main() { // Start with the empty list LinkedList llist = new LinkedList(); /* Use push() to construct below list 14->21->11->30->10 */ llist.push(10); llist.push(30); llist.push(11); llist.push(21); llist.push(14); int x = 21; // Function call if (llist.search(llist.head, x)) Console.WriteLine( "Yes" ); else Console.WriteLine( "No" ); } } // This code is contributed by PrinciRaj1992 |
Javascript
// Recursive javascript program to search an element // in linked list // Node class class Node { constructor(val) { this .data = val; this .next = null ; } } // Linked list class var head; // Head of list // Inserts a new node at the front of the list function push(new_data) { // Allocate new node and putting data var new_node = new Node(new_data); // Make next of new node as head new_node.next = head; // Move the head to point to new Node head = new_node; } // Checks whether the value x is present // in linked list function search(head , x) { // Base case if (head == null ) return false ; // If key is present in current node, // return true if (head.data == x) return true ; // Recur for remaining list return search(head.next, x); } // Driver function to test the above functions // Start with the empty list /* * Use push() to construct below list 14->21->11->30->10 */ push(10); push(30); push(11); push(21); push(14); var x = 21; if (search(head, 21)) document.write( "Yes" ); else document.write( "No" ); // This code contributed by gauravrajput1 |
Yes
Time Complexity: O(N)
Auxiliary Space: O(N), Stack space used by recursive calls
Contact Us