Linked List using Dynamic Memory Allocation

Linked List using Dynamic Memory Allocation – हम Dynamic Memory Allocation का प्रयोग करते हुए पिछले प्रारूप प्रोग्राम को ही यहां समझ रहे हैं कि किस प्रकार से Dynamic Memory Allocation द्वारा एक node को दूसरी node का Address दिया जाता है। यानी-

      struct stud
      {
            int roll_no;
            struct stud *next;
      }

अब Dynamic Memory Allocation के लिये एक Pointer Variable लेते हैं, जो Structure stud प्रकार का है। इसे start नाम देते हैं। यानी

      struct stud *start;

अब इसके लिये Memory Allocate करते हैं और उस Allocated Memory का Address इस start को देते हैं। यानी

      start = ( struct stud * ) malloc ( sizeof ( struct stud ) );

malloc() Function Memory में एक Block बनाएगा, जो कि Structure प्रकार का मान Store कर सकता है। इस Memory Block का Address start में दिया गया है। इसे निम्नानुसार देख सकते हैं-

इस node में हम निम्नानुसार मान प्रदान कर सकते हैं-

start->roll_no = 200;

start->next = NULL;

ये मान निम्नानुसार store होते हैं-

अब हम प्रथम node में एक दूसरी node बना कर उसे जोडते हैं। इसे निम्नानुसार किया गया है-

start->next = ( struct stud * ) malloc ( sizeof ( struct stud ) );

start एक Pointer है और next भी एक Pointer है। Start में Structure के प्रथम Memory Block का Address है। इस Memory Block में एक Pointer Variable next है। यदि इस next को भी Memory में कोई Memory Block बना कर उसका Address दे दिया जाए, तो इसमें भी एक Memory Block का Address होगा। इस Address द्वारा उस Memory में भी मान Store किये जा सकते हैं। इस प्रकार के Declaration से एक प्रकार की Series बन जाती है।

हमने start को एक Structure प्रकार के Memory block का Address प्रदान किया है। इस start द्वारा हम उस Structure में मान Store कर सकते हैं। जैसा कि start->roll_no = 200; and start->next = NULL; statement द्वारा किया है।

यदि इस Structure के Member next को, जो कि एक Pointer Member है, NULL करने के बजाय एक Memory Block बना कर उस Memory Block का Address दे दिया जाए, तो इस Structure प्रकार के Pointer Variable में बनाए गए Memory Block का Address होगा। इस Memory Block में हम वापस roll_no व next नाम के Variable में किसी अन्‍य Memory Block का Address store कर सकते हैं।

इस प्रकार से हम चाहे जितनी संख्‍या में nodes बना सकते हैं और एक दूसरे को Link कर सकते हैं। इसी नियम पर चलते हुए start = (struct stud *)malloc(sizeof(struct stud)); statement  द्वारा start को Structure का एक node बनाकर उस node का Address प्रदान किया है। फिर इस Structure के Member next को एक और Structure प्रकार का Memory Block (node) बना कर, उस Memory Block का Address start->next=(struct stud *) malloc(sizeof(struct stud)); statement  द्वारा next को दिया है।

अब यदि इस दूसरे node के next नाम के Member को कोई Memory Block बना कर उसका Address दे दिया जाए, तो ये तीसरा node बन जाता है। यही क्रम आगे से आगे चलाया जाए तो हम अनन्त तक nodes बना सकते हैं।

जब हम ये nodes बना लेते हैं, तो इनको मान देने का भी एक विशेष क्रम होता है। इस क्रम में हमें प्रथम node के Address से होते हुए उस हर node से गुजरना पडता है, जिसमें मान Input करना है। माना इस प्रक्रिया द्वारा हमने तीन node बनाए तो हमें तीनों nodes में मान Input करने के लिये क्रम से निम्नानुसार मान देना होगा-

प्रथम node को मान देना

start->roll_no = 200;
start->next = NULL;

नया node बनाना और इस node का Address प्रथम node के next को देना-

start->next = ( struct stud * ) malloc ( sizeof ( struct stud ) );

दूसरे node को मान प्रदान करना-

start->next->roll_no = 251;
start->next->next = NULL;

नया node बनाना और इस node का Address दूसरे node के next को देना।

start->next->next = ( struct * ) malloc (sizeof (struct stud ) );

तीसरे node को मान प्रदान करना-

start->next->next->roll_no = 230;
start->next->next->next = NULL;

Linked List का अंत करने के लिये अंतिम node के Member next को NULL प्रदान करना।

इस प्रकार से node बना कर हम हर node को मान प्रदान कर सकते हैं। Linked List में मान Initialize करते समय यदि कई nodes हों तो काफी बडे-बडे statements लिखने पडते हैं। इस असुविधा से बचने के लिये हम एक और Pointer Variable का प्रयोग करते हैं और Loop द्वारा node बनाने व मान Input करने का काम करते हैं। हम एक बार में एक node बना कर उसमें अन्‍य nodes को Insert करके आवश्‍यकतानुसार nodes बना सकते हैं।

हम किसी भी Linked List में मुख्‍यत: तीन प्रकार से nodes को Insert कर सकते हैं-

• Linked List के शुरू में नया node जोड कर ।
• Linked List के मध्‍य में नया node जोड कर व
• Linked List के अंत में नया node जोड कर ।

जब हमें किसी Linked List की शुरूआत में नया node जोडना हो, तब हमें निम्न क्रम में काम करना होता है-

1   यदि प्रथम Pointer start में NULL है तो इसका मतलब होता है, कि Linked List अभी शुरू ही नहीं हुई है। इसलिये एक node Create किया जाता है और उस node का Address Linked List के Start में दे दिया जाता है। ये node Linked List की प्रथम node होती है।

2   यदि प्रथम Pointer start में NULL नहीं हैं तो इसका मतलब है कि Linked List पहले से ही बनी हुई है। इस बनी हुई Linked List में नया node जोडने के लिये नए node का Address Pointer start को दे दिया जाता है और नए node के next Member को start का Address दे दिया जाता है। ऐसा करने पर Start नए node को Point करता है और नए Node का Pointer उस node को Point करता है जिसे पहले Start Point कर रहा था।

3    यदि Linked List शुरू ही नहीं हुई है यानी

      struct stud *start = NULL, *newnode;

तो नया node बनाऐंगे और इस नए node का Address start को दे देंगे। अब इस node को मान Initialize करेंगे साथ ही इस newnode के next Member को NULL कर देंगे। इसका मतलब ये होगा कि इस newnode के बाद कोई node Linked List में नहीं है।

माना नए Node का Address 2020 है तो इस नए node का Address start को देने से start का Address 2020 हो जाएगा और इस newnode के Members को start द्वारा मान प्रदान किया जा सकेगा। इस प्रकार से Linked List की शुरूआत हो जाएगी। अब माना की ऊपर बताई गई स्थिती के बाद Linked List की शुरूआत हो चुकी है और इसी Linked List में एक नया node Linked List की शुरूआत में जोडना है, तो इसके लिये एक नया node निम्नानुसार बनाऐंगे-

newnode = ( struct stud * ) malloc ( sizeof ( struct stud ) );

अब इस नए node को Linked List में जोडने के लिये सर्वप्रथम इस node के next Member को Pointer Variable start का Address देना होगा और उसके बाद इस नए node का Address start को दे देंगे जिससे start अब इस नए node को point करेगा और इस नए node का Member next पहले वाले node को point करेगा। यानी

newnode->next=start;
start=newnode;

यदि इसी प्रकार से आगे का क्रम बढाया जाए तो आवश्‍यकतानुसार Linked List को तब तक बढाया जा सकता है, जब तक कि Memory Space समाप्त ना हो जाए।