Searching in Circular Singly Linked List

by Online Tutorials Library July 22, 2022

Searching in circular singly linked list

Searching in circular singly linked list needs traversing across the list. The item which is to be searched in the list is matched with each node data of the list once and if the match found then the location of that item is returned otherwise -1 is returned.

The algorithm and its implementation in C is given as follows.

Algorithm

Step 1: SET PTR = HEAD
Step 2: Set I = 0
STEP 3: IF PTR = NULL

WRITE “EMPTY LIST”
GOTO STEP 8
END OF IF

STEP 4: IF HEAD → DATA = ITEM

WRITE i+1 RETURN [END OF IF]

STEP 5: REPEAT STEP 5 TO 7 UNTIL PTR->next != head
STEP 6: if ptr → data = item

write i+1
RETURN
End of IF

STEP 7: I = I + 1
STEP 8: PTR = PTR → NEXT

[END OF LOOP]

STEP 9: EXIT

C Function

  #include<stdio.h>  #include<stdlib.h>  void create(int);  void search();  struct node  {  int data;  struct node *next;  };  struct node *head;  void main ()  {  int choice,item,loc;  do   {  printf(“n1.Createn2.Searchn3.Exitn4.Enter your choice?”);  scanf(“%d”,&choice);  switch(choice)  {  case 1:  printf(“nEnter the itemn”);  scanf(“%d”,&item);  create(item);  break;   case 2:  search();  case 3:  exit(0);  break;  default:  printf(“nPlease enter valid choicen”);  }    }while(choice != 3);  }  void create(int item)  {  struct node *ptr = (struct node *)malloc(sizeof(struct node));  struct node *temp;  if(ptr == NULL)  {  printf(“nOVERFLOWn”);  }  else  {  ptr->data = item;  if(head == NULL)  {  head = ptr;  ptr -> next = head;  }  else  {  temp = head;  while(temp -> next != head)  {  temp = temp -> next;  }  temp -> next = ptr;   ptr -> next = head;  }  printf(“nNode Insertedn”);  }    }  void search()  {  struct node *ptr;  int item,i=0,flag=1;  ptr = head;   if(ptr == NULL)  {  printf(“nEmpty Listn”);  }  else  {   printf(“nEnter item which you want to search?n”);   scanf(“%d”,&item);  if(head ->data == item)  {  printf(“item found at location %d”,i+1);  flag=0;  return;  }  else   {  while (ptr->next != head)  {  if(ptr->data == item)  {  printf(“item found at location %d “,i+1);  flag=0;  return;  }   else  {  flag=1;  }  i++;  ptr = ptr -> next;  }  }  if(flag != 0)  {  printf(“Item not foundn”);  return;  }  }    }    

Output

1.Create  2.Search  3.Exit  4.Enter your choice?1    Enter the item  12    Node Inserted    1.Create  2.Search  3.Exit  4.Enter your choice?1    Enter the item  23    Node Inserted    1.Create  2.Search  3.Exit  4.Enter your choice?2    Enter item which you want to search?  12  item found at location 1

Next TopicDoubly Linked List

Searching in Circular Singly Linked List

Searching in circular singly linked list

Algorithm

C Function

DAA Algorithm

Chutney vs Pickle

You may also like