Search an element in a Linked List (Iterative and Recursive)
Last Updated :
10 Apr, 2023
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;
class Node {
public:
int key;
Node* next;
};
void push(Node** head_ref, int new_key)
{
Node* new_node = new Node();
new_node->key = new_key;
new_node->next = (*head_ref);
(*head_ref) = new_node;
}
int main() {
Node* head = NULL;
int x = 21;
push(&head, 10);
push(&head, 30);
push(&head, 11);
push(&head, 21);
push(&head, 14);
vector<int>v;
Node* temp=head;
while(temp!=NULL){
v.push_back(temp->key);
temp=temp->next;
}
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
{
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;
push(head, 10);
push(head, 30);
push(head, 11);
push(head, 21);
push(head, 14);
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 Node:
def __init__(self, key):
self.key = key
self.next = None
class LinkedList:
def __init__(self):
self.head = None
def push(self, new_key):
new_node = Node(new_key)
new_node.next = self.head
self.head = new_node
llist = LinkedList()
llist.push(10)
llist.push(30)
llist.push(11)
llist.push(21)
llist.push(14)
x = 21
temp = llist.head
v = []
while(temp):
v.append(temp.key)
temp = temp.next
if x in v:
print("YES")
else:
print("NO")
|
C#
using System;
using System.Collections.Generic;
using System.Linq;
class Node {
public int key;
public Node next;
};
class Program {
static void push(ref Node head_ref, int new_key)
{
Node new_node = new Node();
new_node.key = new_key;
new_node.next = head_ref;
head_ref = new_node;
}
static void Main(string[] args)
{
Node head = null;
int x = 21;
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;
}
if (v.Contains(x)) {
Console.WriteLine("YES");
}
else {
Console.WriteLine("NO");
}
}
}
|
Javascript
class Node {
constructor(key) {
this.key = key;
this.next = null;
}
}
class LinkedList {
constructor() {
this.head = null;
}
push(new_key) {
let new_node = new Node(new_key);
new_node.next = this.head;
this.head = new_node;
}
}
let llist = new LinkedList();
llist.push(10);
llist.push(30);
llist.push(11);
llist.push(21);
llist.push(14);
let x = 22;
let temp = llist.head;
let v = [];
while (temp) {
v.push(temp.key);
temp = temp.next;
}
if (v.includes(x)) {
console.log("YES");
} else {
console.log("NO");
}
|
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++
#include <bits/stdc++.h>
using namespace std;
class Node {
public:
int key;
Node* next;
};
void push(Node** head_ref, int new_key)
{
Node* new_node = new Node();
new_node->key = new_key;
new_node->next = (*head_ref);
(*head_ref) = new_node;
}
bool search(Node* head, int x)
{
Node* current = head;
while (current != NULL) {
if (current->key == x)
return true;
current = current->next;
}
return false;
}
int main()
{
Node* head = NULL;
int x = 21;
push(&head, 10);
push(&head, 30);
push(&head, 11);
push(&head, 21);
push(&head, 14);
search(head, x) ? cout << "Yes" : cout << "No";
return 0;
}
|
C
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
struct Node {
int key;
struct Node* next;
};
void push(struct Node** head_ref, int new_key)
{
struct Node* new_node
= (struct Node*)malloc(sizeof(struct Node));
new_node->key = new_key;
new_node->next = (*head_ref);
(*head_ref) = new_node;
}
bool search(struct Node* head, int x)
{
struct Node* current = head;
while (current != NULL) {
if (current->key == x)
return true;
current = current->next;
}
return false;
}
int main()
{
struct Node* head = NULL;
int x = 21;
push(&head, 10);
push(&head, 30);
push(&head, 11);
push(&head, 21);
push(&head, 14);
search(head, x) ? printf("Yes") : printf("No");
return 0;
}
|
Java
class LinkedList {
Node head;
public void push(int new_data)
{
Node new_node = new Node(new_data);
new_node.next = head;
head = new_node;
}
public boolean search(Node head, int x)
{
Node current = head;
while (current != null) {
if (current.data == x)
return true;
current = current.next;
}
return false;
}
public static void main(String args[])
{
LinkedList llist = new LinkedList();
int x = 21;
llist.push(10);
llist.push(30);
llist.push(11);
llist.push(21);
llist.push(14);
if (llist.search(llist.head, x))
System.out.println("Yes");
else
System.out.println("No");
}
}
class Node {
int data;
Node next;
Node(int d)
{
data = d;
next = null;
}
}
|
Python3
class Node:
def __init__(self, data):
self.data = data
self.next = None
class LinkedList:
def __init__(self):
self.head = None
def push(self, new_data):
new_node = Node(new_data)
new_node.next = self.head
self.head = new_node
def search(self, x):
current = self.head
while current != None:
if current.data == x:
return True
current = current.next
return False
if __name__ == '__main__':
llist = LinkedList()
x = 21
llist.push(10)
llist.push(30)
llist.push(11)
llist.push(21)
llist.push(14)
if llist.search(x):
print("Yes")
else:
print("No")
|
C#
using System;
public class Node {
public int data;
public Node next;
public Node(int d)
{
data = d;
next = null;
}
}
public class LinkedList {
Node head;
public void push(int new_data)
{
Node new_node = new Node(new_data);
new_node.next = head;
head = new_node;
}
public bool search(Node head, int x)
{
Node current = head;
while (current != null) {
if (current.data == x)
return true;
current = current.next;
}
return false;
}
public static void Main(String[] args)
{
LinkedList llist = new LinkedList();
llist.push(10);
llist.push(30);
llist.push(11);
llist.push(21);
llist.push(14);
int x = 21;
if (llist.search(llist.head, x))
Console.WriteLine("Yes");
else
Console.WriteLine("No");
}
}
|
Javascript
class Node {
constructor(d) {
this.data = d;
this.next = null;
}
}
var head;
function push(new_data)
{
var new_node = new Node(new_data);
new_node.next = head;
head = new_node;
}
function search( head , x)
{
var current = head;
while (current != null) {
if (current.data == x)
return true;
current = current.next;
}
return false;
}
push(10);
push(30);
push(11);
push(21);
push(14);
var x = 21;
if (search(head, x))
document.write("Yes");
else
document.write("No");
|
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++
#include <bits/stdc++.h>
using namespace std;
struct Node {
int key;
struct Node* next;
};
void push(struct Node** head_ref, int new_key)
{
struct Node* new_node
= (struct Node*)malloc(sizeof(struct Node));
new_node->key = new_key;
new_node->next = (*head_ref);
(*head_ref) = new_node;
}
bool search(struct Node* head, int x)
{
if (head == NULL)
return false;
if (head->key == x)
return true;
return search(head->next, x);
}
int main()
{
struct Node* head = NULL;
int x = 21;
push(&head, 10);
push(&head, 30);
push(&head, 11);
push(&head, 21);
push(&head, 14);
search(head, x) ? cout << "Yes" : cout << "No";
return 0;
}
|
C
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
struct Node {
int key;
struct Node* next;
};
void push(struct Node** head_ref, int new_key)
{
struct Node* new_node
= (struct Node*)malloc(sizeof(struct Node));
new_node->key = new_key;
new_node->next = (*head_ref);
(*head_ref) = new_node;
}
bool search(struct Node* head, int x)
{
if (head == NULL)
return false;
if (head->key == x)
return true;
return search(head->next, x);
}
int main()
{
struct Node* head = NULL;
int x = 21;
push(&head, 10);
push(&head, 30);
push(&head, 11);
push(&head, 21);
push(&head, 14);
search(head, x) ? printf("Yes") : printf("No");
return 0;
}
|
Java
class LinkedList {
Node head;
public void push(int new_data)
{
Node new_node = new Node(new_data);
new_node.next = head;
head = new_node;
}
public boolean search(Node head, int x)
{
if (head == null)
return false;
if (head.data == x)
return true;
return search(head.next, x);
}
public static void main(String args[])
{
LinkedList llist = new LinkedList();
llist.push(10);
llist.push(30);
llist.push(11);
llist.push(21);
llist.push(14);
int x = 21;
if (llist.search(llist.head, x))
System.out.println("Yes");
else
System.out.println("No");
}
}
class Node {
int data;
Node next;
Node(int d)
{
data = d;
next = null;
}
}
|
Python3
class Node:
def __init__(self, data):
self.data = data
self.next = None
class LinkedList:
def __init__(self):
self.head = None
def push(self, new_data):
new_node = Node(new_data)
new_node.next = self.head
self.head = new_node
def search(self, li, key):
if(not li):
return False
if(li.data == key):
return True
return self.search(li.next, key)
if __name__ == '__main__':
li = LinkedList()
li.push(10)
li.push(30)
li.push(11)
li.push(21)
li.push(14)
x = 21
if li.search(li.head, x):
print("Yes")
else:
print("No")
|
C#
using System;
public class Node {
public int data;
public Node next;
public Node(int d)
{
data = d;
next = null;
}
}
public class LinkedList {
Node head;
public void push(int new_data)
{
Node new_node = new Node(new_data);
new_node.next = head;
head = new_node;
}
public bool search(Node head, int x)
{
if (head == null)
return false;
if (head.data == x)
return true;
return search(head.next, x);
}
public static void Main()
{
LinkedList llist = new LinkedList();
llist.push(10);
llist.push(30);
llist.push(11);
llist.push(21);
llist.push(14);
int x = 21;
if (llist.search(llist.head, x))
Console.WriteLine("Yes");
else
Console.WriteLine("No");
}
}
|
Javascript
class Node {
constructor(val) {
this.data = val;
this.next = null;
}
}
var head;
function push(new_data) {
var new_node = new Node(new_data);
new_node.next = head;
head = new_node;
}
function search(head , x) {
if (head == null)
return false;
if (head.data == x)
return true;
return search(head.next, x);
}
push(10);
push(30);
push(11);
push(21);
push(14);
var x = 21;
if (search(head, 21))
document.write("Yes");
else
document.write("No");
|
Time Complexity: O(N)
Auxiliary Space: O(N), Stack space used by recursive calls
Like Article
Suggest improvement
Share your thoughts in the comments
Please Login to comment...