Search in Linked List: How to perform it?

Search in Linked List: जिस तरह से किसी Array में से यदि किसी Data Item को Search करने के दो तरीके हैं उसी तरह से किसी Linked List में से भी किसी Data Item को Search करने के दो तरीके होते हैं।

मानलो कि LIST एक Linked List है और ITEM वह Item है जिसे Search करना है और LOCATION वह Memory Location है जहां पर Search किया जाने वाला ITEM पहली बार प्राप्त होता है। (एक Linked List में एक ही प्रकार के मान कई बार कई LOCATIONS पर हो सकते हैं।)

यहां पहले Algorithm में ये माना गया है कि जिस LIST में से ITEM की LOCATION को Search किया जा रहा है वह LIST Sorted नहीं है। दूसरे Algorithm में ये माना जा रहा है कि LIST SORTED है जिसमें से Data Items की LOCATION को Search करना है।

हम ये भी मान कर चल रहे हैं कि जो Data Item Search किया जा रहा है वह LIST में केवल एक ही बार Store हो सकता है यानी Stored Data Item Unique है।

LIST is Unsorted

मानलो कि हम जिस LIST में Data ITEM को Search कर रहे हैं वह LIST Sorted नहीं है। इस स्थिति में हमें LIST के हर Data Item PTR[INFO] को एक PTR Pointer से Traversing द्वारा Search किए जा रहे ITEM से Check करना होगा। यानी

IF PTR[INFO] == ITEM then
SET LOCATION = PTR
ELSE
PTR = PTR[LINK]

इस Algorithm में हमें दो Test करने होंगे जिसमें पहला Test ये तय करेगा कि Loop कब तक चलेगा। यानी Loop तब तक चलना चाहिए जब तक कि PTR में NULL ना आ जाए और दूसरा Test ये Check करेगा कि जो ITEM Search किया जा रहा है वह LIST में उपलब्ध है या नहीं। यदि ITEM LIST में उपलब्ध हो तो ITEM की LOCATION Return होनी चाहिए अन्यथा एक Message Display होना चाहिए जो बताए कि Search किया जाने वाला ITEM LIST में उपलब्ध नहीं है। इसी पूरी प्रक्रिया का Algorithm हम निम्नानुसार लिख सकते हैं-

UNSORTED SEARCHING Algorithm
UNSORTED_SEARCHING(LIST, LINK, INFO, ITEM, LOC, PTR)

• SET PTR = START
• REPEAT Step 3 and 4 WHILE PTR <> NULL
• IF PTR[INFO] == ITEM then
  SET LOC = PTR and EXIT
  ELSE
  PTR = PTR[LINK]            [ Now PTR Points next NODE ]
  [ End of IF Structure ]
  [ End of Loop Step 2 ]
• SET LOC = NULL                [ If Search is Unsuccessful ]
• EXIT

इस Algorithm के आधार पर हम निम्नानुसार एक Function बना सकते हैं जो किसी Linked List में से किसी ITEM को Search करता है और यदि ITEM प्राप्त हो जाता है तो उसकी LOCATION Return करता है। यदि ITEM प्राप्त नहीं होता है तो LOCATION में NULL Store हो जाता है, जिसका मतलब होता है कि List में Find किया जाने वाला ITEM उपलब्ध नहीं है।

UNSORTED SEARCH Function

void SEARCH(struct LIST **PTR, int ITEM)
{
 struct LIST *temp;
   int LOCATION=0 ;
   temp = *PTR;
   clrscr();

 while(temp != NULL)
   {
   LOCATION++;
   if(temp->INFO == ITEM)
   {
    printf("nSearched Data Element Found at the %d LOCATION n", LOCATION);
  return ;
   }

   else
    temp = temp->LINK;
   }
   printf("nData Item Not Found In The LIST n");
}

LIST is Sorted

जिस LIST में से Data Item की Location को Search किया जा रहा है वह LIST यदि SORTED हो तो हम निम्न Algorithm का प्रयोग करके Find की जाने वाली ITEM की LOCATION का पता लगा सकते हैं। इस Algorithm में भी हमें LIST के हर Node को ITEM से Test करना पडता है।

यानी इस Algorithm की Complexity व पिछले Algorithm की Complexity समान होती है। यानी यदि हम किसी Linked List पर Binary Search Algorithm का प्रयोग करके किसी Data की LOCATION प्राप्त करना चाहें तो हम ऐसा नहीं कर सकते हैं। एक Linked List की Binary Searching नहीं की जा सकती है।

SORTED SEARCH Algorithm
SORTED_SEARCH(LIST, LINK, INFO, ITEM, LOC)

• SET PTR = START
• REPEAT Step 3 WHILE PTR <> NULL
• IF ITEM < PTR[INFO] then
  SET PTR = PTR[LINK]        [ Now PTR points to next NODE ]
  ELSEIF ITEM = PTR[INFO] then
  SET LOCATION = PTR and EXIT      [ Search is Successful ]
  ELSE
  SET LOCATION = NULL and EXIT     [ ITEM not Exists in LIST ]
• EXIT

इस Algorithm का प्रयोग करके हम निम्नानुसार एक Function Create कर सकते हैं-

void SEARCH2(struct LIST **PTR, int ITEM)
{
struct LIST *temp;
   int LOCATION=0 ;
   temp = *PTR;
   clrscr();

while(temp != NULL)
   {
      LOCATION++;
      if(ITEM < temp->INFO)
        temp = temp->LINK;

  else if(temp->INFO == ITEM)
      {
     printf("nSearched Data Element Found at the %d LOCATION n", LOCATION);
         getch();
         clrscr();
 return ;
      }

      else
      {
   printf("nData Item Not Found In The LIST n");
         getch();
         clrscr();
 return ;
      }
   }
   getch();
   clrscr();
}