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 headof a list and an int, push a new node on the frontof 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 Nodeclass Node: # Initialize the node with a key def __init__(self, key): self.key = key self.next = None # Class definition for Linked Listclass 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 objectllist = LinkedList()# Add new nodes to the linked listllist.push(10)llist.push(30)llist.push(11)llist.push(21)llist.push(14) # Key to search for in the linked listx = 21# Create a temp variable to traverse the linked listtemp = llist.head# List to store the keys in the linked listv = []# 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 Nodeclass Node {// Initialize the node with a keyconstructor(key) {this.key = key;this.next = null;}}// Class definition for Linked Listclass LinkedList {// Initialize the linked list with a head nodeconstructor() {this.head = null;}// Add a new node with key "new_key" at the beginning of the linked listpush(new_key) {let new_node = new Node(new_key);new_node.next = this.head;this.head = new_node;}}// Create a linked list objectlet llist = new LinkedList();// Add new nodes to the linked listllist.push(10);llist.push(30);llist.push(11);llist.push(21);llist.push(14);// Key to search for in the linked listlet x = 22;// Create a temp variable to traverse the linked listlet temp = llist.head;// Array to store the keys in the linked listlet 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");} |
Output
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 headof a list and an int, push a new node on the frontof 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 classclass 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 classclass 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 classclass 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 classclass 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 codeif __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 listusing System;// Node classpublic class Node { public int data; public Node next; public Node(int d) { data = d; next = null; }}// Linked list classpublic 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 classclass 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 |
Output
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 headof a list and an int, push a new node on the frontof 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 classclass 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 classclass 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 classclass Node: # Function to initialise # the node object def __init__(self, data): self.data = data # Assign data self.next = None # Initialize next as nullclass 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 Codeif __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 listusing System;// Node classpublic class Node { public int data; public Node next; public Node(int d) { data = d; next = null; }}// Linked list classpublic 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 classvar head; // Head of list // Inserts a new node at the front of the list function push(new_data) { // Allocate new node and putting datavar 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
This article is contributed by Ravi. Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
