.png)
Search in a Singly Linked List
Problem Statement
Given the head pointer of a singly linked list and a key value, determine whether the key exists in the linked list.
Return:
- True / 1 if the element is found
- False / 0 if the element is not found
The search must be performed by traversing the linked list from head to end.
Understanding the Search Operation in a Linked List
Searching in a linked list is different from searching in an array.
In arrays:
- Direct indexing is possible.
- Binary search can be applied if sorted.
In linked lists:
- There is no direct access by index.
- Nodes must be visited sequentially.
- Traversal is mandatory.
Because of this, searching in a singly linked list always requires linear traversal.
How Searching Works in a Linked List
To search for a key:
- Start from the head node.
- Compare the current node’s data with the key.
- If equal, return True.
- Otherwise, move to the next node.
- Continue until:
- Key is found, or
- You reach NULL.
Key Insight:
Search in a singly linked list is always O(n) in worst case.
Iterative Search in a Linked List
Logic Behind Iterative Search
The iterative approach uses a loop.
We:
- Create a temporary pointer.
- Traverse the list node by node.
- Compare data with the key.
If match found → stop immediately.
If end reached → key does not exist.
Algorithm for Iterative Search
If head == NULL:
Return False
Set temp = head
While temp != NULL:
If temp->data == key:
Return True
Move temp = temp->next
Return False
Time and Space Complexity
Time Complexity: O(n)
Worst case: element not present or present at last node.
Space Complexity: O(1)
No extra memory used.
C Program for Searching in a Linked List
// While running this code, replace all #include "..." with #include <...>
#include "stdio.h"
#include "stdlib.h"
struct Node {
int data;
struct Node* next;
};
int search(struct Node* head, int key) {
struct Node* temp = head;
while (temp != NULL) {
if (temp->data == key)
return 1;
temp = temp->next;
}
return 0;
}
int main() {
struct Node* head = (struct Node*)malloc(sizeof(struct Node));
head->data = 10;
head->next = (struct Node*)malloc(sizeof(struct Node));
head->next->data = 20;
head->next->next = (struct Node*)malloc(sizeof(struct Node));
head->next->next->data = 30;
head->next->next->next = NULL;
int key = 20;
if (search(head, key))
printf("Element %d found in the linked list\n", key);
else
printf("Element %d not found in the linked list\n", key);
return 0;
}Output:
Element 20 found in the linked list
C++ Program for Searching in a Linked List
// While running this code, replace all #include "..." with #include <...>
#include "iostream"
using namespace std;
class Node {
public:
int data;
Node* next;
Node(int val) {
data = val;
next = NULL;
}
};
bool search(Node* head, int key) {
Node* temp = head;
while (temp != NULL) {
if (temp->data == key)
return true;
temp = temp->next;
}
return false;
}
int main() {
Node* head = new Node(10);
head->next = new Node(20);
head->next->next = new Node(30);
int key = 25;
if (search(head, key))
cout << "Element " << key << " found in the linked list" << endl;
else
cout << "Element " << key << " not found in the linked list" << endl;
return 0;
}
Output:
Element 25 not found in the linked list
Java Program for Searching in a Linked List
class Node {
int data;
Node next;
Node(int data) {
this.data = data;
this.next = null;
}
}
public class Main {
public static boolean search(Node head, int key) {
Node temp = head;
while (temp != null) {
if (temp.data == key)
return true;
temp = temp.next;
}
return false;
}
public static void main(String[] args) {
Node head = new Node(10);
head.next = new Node(20);
head.next.next = new Node(30);
int key = 30;
if (search(head, key))
System.out.println("Element " + key + " found in the linked list");
else
System.out.println("Element " + key + " not found in the linked list");
}
}
Output:
Element 30 found in the linked list
Python Program for Searching in a Linked List
class Node:
def __init__(self, data):
self.data = data
self.next = None
def search(head, key):
temp = head
while temp is not None:
if temp.data == key:
return True
temp = temp.next
return False
head = Node(10)
head.next = Node(20)
head.next.next = Node(30)
key = 40
if search(head, key):
print(f"Element {key} found in the linked list")
else:
print(f"Element {key} not found in the linked list")
Output:
Element 40 not found in the linked list
Recursive Search in a Linked List
Concept Behind Recursive Search
In recursion:
If head is NULL:
Return False
If head->data == key:
Return True
Otherwise:
Return search(head->next, key)
Each recursive call reduces the problem size by one node.
Time and Space Complexity
Time Complexity: O(n)
Space Complexity: O(n) due to recursion stack.
Recursive Search Implementation
You are absolutely right.
For a complete book-quality chapter, the Recursive Search implementation must be provided in all languages, just like the iterative one.
Below is the missing section, written in proper SEO structure and with output included in code blocks.
Recursive Search in a Singly Linked List
How Recursive Search Works
Recursive search follows a divide-and-conquer idea.
At each step:
- If the current node is NULL → return False.
- If current node’s data equals the key → return True.
- Otherwise → recursively search in the remaining list.
Each recursive call moves one node forward until either:
- The key is found, or
- The list ends.
Algorithm for Recursive Search
If head == NULL:
Return False
If head->data == key:
Return True
Return search(head->next, key)
Time and Space Complexity
Time Complexity: O(n)
Worst case: element not found.
Space Complexity: O(n)
Because each recursive call occupies stack space.
Recursive Search Implementation in C
// While running this code, replace all #include "..." with #include <...>
#include "stdio.h"
#include "stdlib.h"
struct Node {
int data;
struct Node* next;
};
int searchRecursive(struct Node* head, int key) {
if (head == NULL)
return 0;
if (head->data == key)
return 1;
return searchRecursive(head->next, key);
}
int main() {
struct Node* head = (struct Node*)malloc(sizeof(struct Node));
head->data = 10;
head->next = (struct Node*)malloc(sizeof(struct Node));
head->next->data = 20;
head->next->next = (struct Node*)malloc(sizeof(struct Node));
head->next->next->data = 30;
head->next->next->next = NULL;
int key = 30;
if (searchRecursive(head, key))
printf("Element %d found in the linked list\n", key);
else
printf("Element %d not found in the linked list\n", key);
return 0;
}Output:
Element 30 found in the linked list
Recursive Search Implementation in C++
// While running this code, replace all #include "..." with #include <...>
#include "iostream"
using namespace std;
class Node {
public:
int data;
Node* next;
Node(int val) {
data = val;
next = NULL;
}
};
bool searchRecursive(Node* head, int key) {
if (head == NULL)
return false;
if (head->data == key)
return true;
return searchRecursive(head->next, key);
}
int main() {
Node* head = new Node(5);
head->next = new Node(15);
head->next->next = new Node(25);
int key = 100;
if (searchRecursive(head, key))
cout << "Element " << key << " found in the linked list" << endl;
else
cout << "Element " << key << " not found in the linked list" << endl;
return 0;
}
Output:
Element 100 not found in the linked list
Recursive Search Implementation in Java
class Node {
int data;
Node next;
Node(int data) {
this.data = data;
this.next = null;
}
}
public class Main {
public static boolean searchRecursive(Node head, int key) {
if (head == null)
return false;
if (head.data == key)
return true;
return searchRecursive(head.next, key);
}
public static void main(String[] args) {
Node head = new Node(7);
head.next = new Node(14);
head.next.next = new Node(21);
int key = 14;
if (searchRecursive(head, key))
System.out.println("Element " + key + " found in the linked list");
else
System.out.println("Element " + key + " not found in the linked list");
}
}
Output:
Element 14 found in the linked list
Recursive Search Implementation in Python
class Node:
def __init__(self, data):
self.data = data
self.next = None
def search_recursive(head, key):
if head is None:
return False
if head.data == key:
return True
return search_recursive(head.next, key)
head = Node(3)
head.next = Node(6)
head.next.next = Node(9)
key = 8
if search_recursive(head, key):
print(f"Element {key} found in the linked list")
else:
print(f"Element {key} not found in the linked list")
Output:
Element 8 not found in the linked list
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.jpg)
.png)
.jpg)
.jpg)
.jpg)
