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

Output

Yes

Time Complexity: O(N)
Auxiliary Space: O(N), Stack space used by recursive calls

Search an element in a Linked List (Recursive Approach)

C++

C

Java

Python3

C#

Javascript

Search an element in a Linked List (Iterative and Recursive)

Categories

Contact US

Search an element in a Linked List (Recursive Approach)

C++

C

Java

Python3

C#

Javascript

Search an element in a Linked List (Iterative and Recursive)

Similar Reads

Categories

Contact US