Top List List

Write a program in C to search an existing element in a Singly linked list

C Exercises: Search an element in a Singly Linked List

Last update on December 20 2021 09:11:04 [UTC/GMT +8 hours]

Quick links

  • Using loop
  • Using recursion

Search is one of the most common operation on performed any data structure. In this post I will explain how to search an element in linked list [iterative and recursive] using C program. I will explain both ways to search, how to search an element in linked list using loop and recursion.

Write a C program to create a function to search an element in linked list. If element exists in the linked list then, it should return its index otherwise -1.

Program to search an element in a singly linked list

Explanation

In this program, we need to search a node in the given singly linked list.

To solve this problem, we will traverse through the list using a node current. Current points to head and start comparing searched node data with current node data. If they are equal, set the flag to true and print the message along with the position of the searched node.

For, eg. In the above list, a search node says 4 which can be found at the position 4.

Algorithm

  1. Create a class Node which has two attributes: data and next. Next is a pointer to the next node in the list.
  2. Create another class SearchLinkedList which has two attributes: head and tail.
  3. addNode[] will add a new node to the list:
    1. Create a new node.
    2. It first checks, whether the head is equal to null which means the list is empty.
    3. If the list is empty, both head and tail will point to a newly added node.
    4. If the list is not empty, the new node will be added to end of the list such that tail's next will point to a newly added node. This new node will become the new tail of the list.
  4. searchNode[] will search for a node in the list:
    1. Variable i will keep track of the position of the searched node.
    2. The variable flag will store boolean value false.
    3. Node current will point to head node.
    4. Iterate through the loop by incrementing current to current.next and i to i + 1.
    5. Compare each node's data with the searched node. If a match is found, set flag to true.
    6. If the flag is true, display the position of the searched node.
    7. Else, display the message "Element is not present in the list".
  5. display[] will display the nodes present in the list:
    1. Define a node current which will initially point to head of the list.
    2. Traverse through the list till current points to null.
    3. Display each node by making current to point to node next to it in each iteration.

Solution

Python

Output:

Element is present in the list at the position : 2 Element is not present in the list

C

Output:

Element is present in the list at the position : 2 Element is not present in the list

JAVA

Output:

Element is present in the list at the position : 2 Element is not present in the list

C#

Output:

Element is present in the list at the position : 2 Element is not present in the list

PHP

Output:

Element is present in the list at the position : 2 Element is not present in the list

Search an element in a Linked List [Iterative and Recursive]

Write a function that searches a given key ‘x’ in a given singly linked list. The function should return true if x is present in linked list and false otherwise.

bool search[Node *head, int x]

For example, if the key to be searched is 15 and linked list is 14->21->11->30->10, then function should return false. If key to be searched is 14, then the function should return true.
Iterative Solution

1] Initialize a node pointer, current = head. 2] Do following while current is not NULL a] current->key is equal to the key being searched return true. b] current = current->next 3] Return false

Following is iterative implementation of above algorithm to search a given key.

C++




// Iterative C++ program to search
// an element in linked list
#include
using namespace std;
/* Link list node */
class Node
{
public:
int key;
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[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 off 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 program to test count function*/
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];
search[head, 21]? coutnext;
}
return false;
}
/* Driver program to test count function*/
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];
search[head, 21]? printf["Yes"] : printf["No"];
return 0;
}
Java




// Iterative Java program to search an element
// in linked list
//Node class
class Node
{
int data;
Node next;
Node[int d]
{
data = d;
next = null;
}
}
//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]
{
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 function to test the above functions
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];
if [llist.search[llist.head, 21]]
System.out.println["Yes"];
else
System.out.println["No"];
}
}
// This code is contributed by Pratik Agarwal
Python3




# Iterative 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
# Linked List class
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]
# 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
# Code execution starts here
if __name__ == '__main__':
# Start with the empty list
llist = 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];
if llist.search[21]:
print["Yes"]
else:
print["No"]
# This code is contributed by Ravi Shankar
C#




// Iterative 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]
{
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];
if [llist.search[llist.head, 21]]
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 class
class 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];
if [search[head, 21]]
document.write["Yes"];
else
document.write["No"];
// This code contributed by aashish2995

Output:



Yes

Recursive Solution

bool search[head, x] 1] If head is NULL, return false. 2] If head's key is same as x, return true; 3] Else return search[head->next, x]

Following is the recursive implementation of the above algorithm to search a given key.

C++




// Recursive C++ program to search
// an element in linked list
#include
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 off 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];
search[head, 21]? cout 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 program to test count function*/
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];
search[head, 21]? printf["Yes"] : printf["No"];
return 0;
}
Java




// Recursive Java program to search an element
// in linked list
// Node class
class Node
{
int data;
Node next;
Node[int d]
{
data = d;
next = null;
}
}
// 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 function to test the above functions
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];
if [llist.search[llist.head, 21]]
System.out.println["Yes"];
else
System.out.println["No"];
}
}
// 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[1]
li.push[2]
li.push[3]
li.push[4]
key = 4
if li.search[li.head,key]:
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];
if [llist.search[llist.head, 21]]
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];
if [search[head, 21]]
document.write["Yes"];
else
document.write["No"];
// This code contributed by gauravrajput1

Output:

Yes

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




Article Tags :
Linked List
Practice Tags :
Linked List
Read Full Article

Search an element in linked list - C Program

  • Home > C Programs > C Linked List programs
  • « Previous
  • Next »
    Programs
  • C Linked List Programs
  • Create & Sort a single linked list
  • Create Odd & Even linked lists
  • Insert node in doubly linked list
  • Delete user specified node from circular linked list
  • Search an element in linked list
  • Print linked list in reverse order
C program to search an element in linked list.

Solution:

#include
#include
struct node
{
int data;
struct node *next;
}
first, *nw;

int search[int item]
{
int count=1;
nw=&first;
while[nw->next!=NULL]
{
if[nw->data==item]
break;
else
count++;
nw=nw->next;
}
return count;
}
int main[]
{
int no,i,item,pos;
first.next=NULL;
nw=&first;
printf["How many nodes you want in linked list?: "];
scanf["%d",&no];
printf["\n"];
for[i=0;i< no;i++]
{
nw->next=[struct node *]malloc[sizeof[struct node]];
printf["Enter element in node %d: ",i+1];
scanf["%d",&nw->data];
nw=nw->next;
}
nw->next=NULL;
printf["\nElements in linked list :\n\n"];
nw=&first;
while[nw->next!=NULL]
{
printf["%d\t",nw->data];
nw=nw->next;
}
printf["\n"];
printf["\nEnter element to be searched : "];
scanf["%d",&item];
pos=search[item];
if[pos

Bài Viết Liên Quan

Which of the following linked lists where each node has pointers to point to the Predecessor and successors node?
How many pointers are naturally changed for the insertion in a linked list?
Which of the following points is not true about linked list data structure?
Which type of linked lists comprise SA node contains a pointer to predecessor as well as successor?
Which of the following indicates the current position of the top of the stack
In a linked implementation of a stack, a pushed element should be added to the end of the list.
Write a program in C to delete a node from the any position of Singly Linked list
Which of these statements will delete a node form the end of a Doubly Linked List if temp refers to the last node?
What is the time complexity of adding a node at the end of doubly linked list
In a linked list the pointer of the node contains a special value called the null pointer
What is the average run time complexity of inserting an element into a doubly linked list assuming you have a pointer to the insertion location?
Difference between singly linked list and Doubly linked list in data structure
Write ac program to remove odd integers from a linked list containing integers
Is a technique using which a computer periodically collects all the deleted space onto the free storage list Mcq?
What is the time complexity of inserting a node in a sorted doubly linked list having a pointer to the head of list?
What is the asymptotic complexity of adding a node at end of single linked list
Write algorithms to insert and delete an element from a circular linked list discuss with examples
What is the complexity to insert a node at a specific position in a linked list?
What is the time complexity of inserting a node in singly linked list at the end?
Program to insert a node at the beginning at the end and in the middle of the given linked list

Toplist mới

#1
Top 7 luas segitiga berikut adalah 130 cm k 300 cm - 120 cm 2023
6 tháng trước
#2
Top 16 negara asean yang memiliki jumlah penduduk paling sedikit adalah 2023
6 tháng trước
#3
Top 6 poh larutan cuka 0 1 m ka = 10 ⁻ ⁵ adalah 2023
6 tháng trước
#4
Top 8 sistem pengangkatan pegawai berdasarkan kecakapan atau kompetensi pegawai adalah 2023
6 tháng trước
#5
Top 8 proses pertama kali yang terjadi pada saat pembentukan urine adalah 2023
6 tháng trước
#6
Top 8 contoh diagonal bidang 2023
6 tháng trước
#7
Top 5 contoh ideologi transnasional 2023
6 tháng trước
#8
Top 7 kapur gamping dalam alat penjernih air berfungsi untuk …. 2023
6 tháng trước
#9
Top 6 rumus molekul senyawa dengan rumus empiris c2h2o dan mr 84 adalah 2023
6 tháng trước

Bài mới nhất

Chủ Đề

Kiat Bagus Cara Belajar Location Jelaskan Kesehatan dan kecantikan Bagaimana Teknologi Apa arti Arti kata Sebutkan Top List Toplist Apa yang Permainan Mengapa disebut Belajar dengan baik Membandingkan Perbedaan Berikut ini Makanan lezat Dimaksud Tentang Facebook Konstruksi Berikut yang Daftar Teratas javascript