INSERTING New NODE at the End of the LINKED LIST

INSERTING New NODE at the End of the LINKED LIST – जब किसी Linked List की शुरूआत हो चुकी हो यानी START = NULL ना हो तब Linked List के अंत में नया node Add करने के लिए हमें निम्न काम करने होते हैं-

• एक Structure प्रकार का नया Pointer Variable लेकर Loop को तब तक चलाते हैं, जब तक कि Linked List का अंत नहीं आ जाता है।
• जब Linked List के अंत में पहुंच जाते हैं, तब नये node का Address Linked list के अंतिम node के LINK Part को NULL के स्थान पर दे देते हैं।
• नए node के next का मान NULL कर देते हैं।

चूंकि Linked List की शुरूआत पहले ही हो चुकी है यानी START का मान NULL नहीं है, इसलिए सबसे पहले तो हमें Linked List के अन्त पर पहुंचना होगा। किसी Linked List का अन्त वहां होता है जहां LIST[LINK] = NULL होता है। इसके लिए हमें Linked List की Traversing करनी होगी। किसी Linked List के सभी Data Items को Process करने की प्रक्रिया को TRAVERSING कहते हैं।

Traversing के लिए हम निम्न Algorithm का प्रयोग कर सकते हैं, जहां LIST एक Linked List है। START Linked List की शुरूआत बताता है। INFO Data Element का Information Part है और LINK अगले NODE का Pointer है। PTR एक Pointer है जो कि Currently Process हो रहे Data Item को Point करता है।

[code]
TRAVERSING A One – Way Linked List Algorithm 
SET PTR = START     [ Initialize Pointer PTR with the Address of START ]
REPEAT Step 3 and 4 WHILE PTR <> NULL
   SET PTR = PTR[LINK]                   [ PTR now Points to Next NODE ]
   PROCESS PTR[INFO]                    [ Process the Data of the Node ]
                                                  [ End of Step 2 Loop ]
EXIT
[/code]

चूंकि Linked List की शुरूआत पहले ही हो चुकी है और हर Linked List की शुरूआत का Address START में होता है, इसलिए हमें एक Variable PTR में START के Address को लेना होगा ताकि हम START के मान को Change किए बिना Linked List की विभिन्न Nodes को PTR द्वारा प्राप्त कर सकें।

यदि हम START Pointer द्वारा ही Linked List की Traversing करते हैं तो हमारी Linked List की शुरूआत को Point करने वाला Variable START का Address Damage हो जाएगा और फिर यदि हम वापस से Linked List की Traversing करना चाहें] तो हम ऐसा नहीं कर सकेंगे। क्योंकि हमारी Linked List की शुरूआत का Pointer ही Damage हो चुका होगा और START हमारी Linked List के अन्तिम Node को Point कर रहा होगा। यानी यदि हम START Pointer का प्रयोग Traversing के लिए करते हैं तो हम एक ही Traversing में अपने सारे Nodes को Damage कर देंगे।

ऐसा इसलिए होता है क्योकि हमारे इस Traversing Algorithm में START एक Actual Argument के रूप में आता है। इसलिए यदि START का मान Change किया जाए तो वास्तविक START का मान भी Change हो जाएगा जो कि नहीं होना चाहिए। इसीलिए हमने PTR में START का Address लिया है और PTR द्वारा Linked List की Traversing की है। क्योंकि PTR उसी Node को Point कर रहा है जिसे START Point कर रहा है।

हम जानते हैं कि किसी भी Linked List का अन्त हमेंशा LINK = NULL होने पर होता है, इसलिए एक Loop द्वारा Loop के हर Iteration पर PTR में हर अगले Node का Address Store किया गया है जब तक कि PTR का मान NULL नहीं हो जाता। इस Algorithm का प्रयोग करके हम निम्नानुसार एक Function लिख सकते हैं जो किसी Linked List के अन्त पर पहुंचता है।

[code]
Function
      void GoToEnd(struct LIST **PTR)
      {
            while(PTR != NULL)
                  PTR = PTR->LINK;
      }
[/code]

चूंकि हम किसी पहले से Created Linked List के अन्त में एक नया NODE Add करना चाहते हैं, इसलिए Linked List के अन्त पर पहुंचने के बाद हमें एक नया Node Create करना होता है और उस Node का Address पहले से बनी हुई Linked List के अन्तिम Node के LINK Part में जिसमें NULL Stored है, देना होता है। ऐसा करने पर Created नया Node पिछले Node से Link हो जाता है। अन्त में हमें Create होने वाले नए Node के Link Part के LINK को NULL करना पडता है, जिसका मतलब होता है कि इस Node के बाद कोई Node Linked List से Linked नहीं है।

इस पूरी प्रक्रिया को ध्‍यान से समय ने पर हम देख सकते हैं कि किसी पहले से Started Linked List के अन्त में नया Node INSERT करने के लिए हमें दो काम करने पडते हैं- पहला ये कि हम Linked List के अन्त पर पहुंचें और दूसरा ये कि हम नए Node को पिछले Node से Link करें। इन दोनों कामों के लिए हम निम्नानुसार एक ही Algorithm लिख सकते हैं-

[code]
Algorithm 

SET PTR = START       [Initialize Pointer PTR with the Address of START]
REPEAT Step 3 WHILE PTR <> NULL
    SET PTR = PTR[LINK]                    [PTR now Points to Next NODE]
                                                    [End of Step 2 Loop]
CREATE NEWNODE         [Create new Node from AVAILABLESPACE Linked List]
NEWNODE[INFO] = ITEM
NEWNODE[LINK] = NULL
PTR[LINK] = NEWNODE
EXIT
[/code]

इस Algorithm का प्रयोग करके हम निम्नानुसार एक Function बना सकते हैं जो किसी Linked List के अन्त में नया Node INSERT करता है-

[code]
Function 
      INSERT_END(struct LIST **PTR, ITEM)
      {
            struct LIST *NEWNODE, *temp;
            //Go to End of the Linked List
            while(temp->LINK != NULL)
                  temp = temp->LINK;
            //Create New Node
            NEWNODE = (struct LIST *)malloc(sizeof(struct LIST));
            NEWNODE->INFO = ITEM;
            NEWNODE->LINK = NULL;
            temp->LINK = NEWNODE;
      }
[/code]