Operation on Linked List in [Data Structure] in Hindi

Operation on Linked List in [Data Structure] in Hindi

Operation on Linked List in Hindi

Linked list में निम्नलिखित operations किए जा सकते हैं-:

1. Linked list का निर्माण करना।
2. Linked list में traversal करना।
3. Linked list में nodes की कुल संख्या ज्ञात करना।
4. किन्ही दो linked list को concatenate (merge) करना।
5. Linked list में नया node insert कराना।
6. Linked list से पुराने nodes को delete करना।
7. Linked list में किसी node को search करना।
8. Linked list के nodes को sort करना।

Linked List क्या हैं?

Linked List एक ही प्रकार के structures की श्रृंखला (chain) होती है जिन्हें node कहते हैं। इसमें प्रत्येक node के दो भाग होते हैं। पहले भाग को info field कहते हैं जिसमें data store होता है एवं दूसरे भाग को link field कहते हैं जिसमें next node का address store होता है। 

अतः दूसरा भाग एक pointer होता है जो linked list में next node को point करता है इसलिए इसे next pointer भी कहते हैं। हम next pointer की सहायता से ही linked list में अगले node को access करते हैं।

Representation of Linked List in Memory:

माना List एक linked list है जिनके प्रत्येक node के दो भाग INFO व LINK है। START एक list pointer है जो LIST के पहले node को point करता है AVAIL एक empty pointer है जो LIST के सबसे पहले खाली node को point करता है। अब यदि NULL के स्थान पर 0 का प्रयोग करते तो LIST को memory में निम्नलिखित प्रकार के प्रदर्शित किया जा सकता है:

Note:

Underflow: यह तब होता है जब START=NULL हो और हमे deletion करना हो अर्थात linked list खाली हो।

Overflow: यह तब होता है जब AVAIL=NULL हो और हमें insertion करना हो अर्थात linked list पूरा भरा हो।

Traversal in Linked List:

Linked list में traversal करना बहुत आसान होता है। इसके लिए हम एक pointer लेते हैं और उसे list के START (first node) पर set करते हैं। फिर पहले node के info को access व process कर pointer को next node पर set करते हैं और इसी प्रकार को list के NULL (last node) तक करते जाते हैं।

LIST_TRAVERSE (LIST, INFO, LINK, START, PTR)

Here LIST is a linked list and INFO and LINK contains info and link of all nodes respectively. This algorithm traverses LIST writing its all elements one by one.

Step 1: PTR ← START

             [Initialize pointer]

Step 2: Repeat step 3 and 4 Until PTR ≠ NULL

             [Loop]

Step 3: Write: INFO[PTR]

             [Output info] 

Step 4: PTR ← LINK[PTR]

            [Update pointer] [End of step 2 loop]

Step 5: Exit

           [End of Algorithm]

Counting Number of Nodes in Linked List:

Linked list में node की कुल संख्या ज्ञात करना बहुत आसान होता है। इसके लिए हम एक counter लेते हैं और उसे 0 पर set करते हैं एवं pointer लेते हैं और उसे list के START (first node) पर set करते हैं। फिर counter के मान को 1 से increment करते हैं तथा pointer को next node पर set करते हैं और इसी प्रक्रिया को list के NULL (last node) तक करते जाते हैं। अंत मे node की कुल संख्या को Output करते हैं।

LIST_COUNT (LIST, INFO, LINK, START, PTR)

Here LIST is a linked list and INFO and LINK contains info and link of all nodes respectively. This algorithm counts a number of nodes in LIST.

Step 1: C ← 0 and PTR ← START

             [Initialize counter and pointer]

Step 2: Repeat step 3 and 4 Until PTR ≠ NULL

             [Loop]

Step 3: C ← C+1

             [Increment counter]

Step 4: PTR ← LINK[PTR]

             [Update pointer] [End of step 2 loop]

Step 5 : Write: C

            [Output number of nodes]

Step 6: Exit

            [End of Algorithm]

Concatenate two Linked List:

किन्ही दो linked list को concatenate करना बहुत आसान होता है। इसके लिए हम एक pointer लेते हैं और उसे पहले list के START (first node) पर set करते हैं। फिर pointer को next node पर set करते हैं और इसी प्रक्रिया को list के NULL (last node) तक करते जाते हैं। अंत मे जब pointer पहले list के NULL (last node) पर पहुँचता है तो इसे दूसरे list के START पर set कर देते हैं।

LIST_CAT (LIST1, START1, INFO, LINK, LIST2, START2, PTR)

Here LIST1 and LIST2 are linked list and INFO and LINK contains info and link of all nodes of LIST1 respectively. This algorithm concatenates LIST1 and LIST2.

Step 1: PTR ← START1

            [Initialize pointer]

Step 2: Repeat step 3 Until PTR ≠ NULL

            [Loop]

Step 3: PTR ← LINK[PTR]

            [Update Pointer] [End of step 2 loop]

Step 4: LINK[PTR] ← START2

            [Concatenate]

Step 5: Exit

            [End of algorithm]

Insertion in Linked List:

Linked list की शुरुआत में नया node जोड़ना बहुत आसान होता है। इसके लिए AVAIL pointer से जांच करते हैं कि memory में नए node के लिए खाली स्थान है या नही। यदि memory में नए node के लिए खाली स्थान नही होता है तो overflow message display करते हैं और exit ले लेते हैं। और यदि memory में नए node के लिए खाली स्थान होता है तो NEW नाम से एक pointer लेते हैं और उसे उस खाली स्थान पर set कर data को नए node में store कराते हैं। अंत मे नए node को original list के START (first node) पर set करते हैं और START को नए node पर set करते हैं।

LIST_INSERT (LIST, INFO, LINK, START, AVAIL, NEW, DATA)

Here LIST is a linked list and INFO and LINK contains info and link of all nodes respectively. This algorithm inserts a new node at the beginning of the LIST.

Step 1 : If AVAIL = NULL Then

           Write: Overflow and Exit [Check overflow]

Step 2: NEW  ← AVAIL

           [Set new pointer to avail node]

Step 3: AVAIL ← LINK[AVAIL]

           [Set available pointer to next free location]

Step 4: INFO[NEW] ← DATA

           [Store data in new node]

Step 5: LINK[NEW] ← START

           [Set  new node to start]

Step 6; START ← NEW

           [Set start pointer to new node]

Step 7: Exit

           [End of algorithm]

Deletion from the Linked List:

Linked list की शुरुआत से पुराने node को हटाना बहुत आसान होता है। इसके लिए List की जांच करते हैं कि वह खाली तो नही है। यदि LIST खाली होता है तो underflow manage display करते हैं और exit ले लेते हैं। और यदि LIST खाली नही होता तो PTR नाम से एक pointer लेते हैं और उसे START पर set करते हैं। 

फिर START को दूसरे node पर set करते हैं जिससे पहला node list से हट जाता है और दूसरा node list का पहला node बन जाता है। अंत मे हटाए गए पुराने पहले node को AVAIL में जोड़ देते हैं।

LIST_DELETE (LIST, INFO, LINK, START, AVAIL, PTR)

Here LIST is a linked list and INFO and LINK contains info and link of all nodes respectively. This algorithm deletes the old node from the beginning of the LIST.

Step 1: If START = NULL Then          

             Write: Underflow and Exit [Check underflow]

Step 2: PTR ← START

             [Set pointer to start]

Step 3: START ← LINK[PTR]

            [Set start to next/second node]

Step 4: LINK[PTR] ← AVAIL

            [Set deleted/old node to available]

Step 5: AVAIL ← PTR

            [Set available to deleted/old node]

Step 6: Exit

            [End of algorithm]