In this Linked List tutorial, we will see all about the search operation in a singly linked list. In the search operation, we iterate over the list and compare each node's data with the key. If a match is found, the key is present; otherwise it is not.
To search for a node in a linked list, there are two approaches:
- Iterative Approach
- Recursive Approach
Search a key in a linked list using Iterative approach
Start from the head and move to the next node one by one. If a node's data equals the key, stop and report that the key is present. If we reach the end of the list (null), the key is not present.
// Java program to search a key in a linked list using Iterative approach
class Node {
int data;
Node next;
// Constructor
Node(int data) {
this.data = data;
this.next = null;
}
}
public class SearchUsingIterativeApproachInSLL {
// Method to checks whether key is present in the linked list
static void searchKey(Node head, int key) {
// Initialize tempNode with the head of linked list
Node tempNode = head;
// Iterate over all the nodes
while (tempNode != null) {
// Key is present, if tempNode's data is equal to the key.
if (tempNode.data == key) {
System.out.println(key + " is PRESENT in the list.");
return; // returning because key is found.
}
// Move to the next node
tempNode = tempNode.next;
}
// Key is not present, if there is no node with data as key
System.out.println(key + " is NOT PRESENT in the list.");
}
public static void main(String[] args) {
// Create a linked list
Node head = new Node(50);
head.next = new Node(30);
head.next.next = new Node(10);
head.next.next.next = new Node(70);
head.next.next.next.next = new Node(40);
// Linked list will be created like this
// 50 -> 30 -> 10 -> 70 -> 40
// 10 is the Key to search in the linked list
searchKey(head, 10);
// 100 is the Key to search in the linked list
searchKey(head, 100);
}
}10 is PRESENT in the list. 100 is NOT PRESENT in the list.
Time complexity: O(N), where N is the length of the linked list.
Auxiliary Space: O(1), as constant extra space is used.
Search a key in a linked list using Recursive approach
If the list is empty, the key is not present. If the current node's data equals the key, it is present. Otherwise, search the rest of the list by calling the same method with head.next.
// Java program to search a key in a linked list using Recursive approach
class Node {
int data;
Node next;
// Constructor
Node(int data) {
this.data = data;
this.next = null;
}
}
public class SearchUsingRecursiveApproachInSLL {
// Checks whether the key is present in linked list
static boolean searchKey(Node head, int key) {
// If head is equal to null that means list is empty
if (head == null)
return false;
// If key is present in the current node
if (head.data == key)
return true;
// Recur for remaining list
return searchKey(head.next, key);
}
public static void main(String[] args) {
// Create a linked list
Node head = new Node(50);
head.next = new Node(30);
head.next.next = new Node(10);
head.next.next.next = new Node(70);
head.next.next.next.next = new Node(40);
// Linked list will be created like this
// 50 -> 30 -> 10 -> 70 -> 40
// Scenario: Key is present
if (searchKey(head, 70))
System.out.println("Key 70 is PRESENT in the list.");
else
System.out.println("Key 70 is NOT PRESENT in the list.");
// Scenario: Key is not present
if (searchKey(head, 5))
System.out.println("Key 5 is PRESENT in the list.");
else
System.out.println("Key 5 is NOT PRESENT in the list.");
}
}Key 70 is PRESENT in the list. Key 5 is NOT PRESENT in the list.
Time complexity: O(N), where N is the length of the linked list.
Auxiliary Space: O(N), for the recursion call stack.