Linked List

Linked List in Data Structure – ये Dynamic Memory Allocation का ही विस्तारित रूप है। एक Array Linked List का अच्छा उदाहरण है, जिसमें सभी Data One By One आपस में जुडे रहते हैं। लेकिन Array की Size प्रोग्राम की शुरूआत में ही Declare करनी पडती है, जिससे Memory का सही तरह से उपयोग नही हो पाता है। इसी समस्या से बचने के लिये Dynamic Memory Allocation का प्रयोग किया जाता है।

Structure के साथ Dynamic Memory Allocation का प्रयोग किया जा सकता है। जब हम Structure के साथ Dynamic Memory Allocation का प्रयोग करते हैं तो इस तरीके से Memory में Store होने वाले Data Items की List को ही Linked List कहते हैं। Linked List में हमेंशा एक Structure होता है, जिसका एक Member हमेंशा एक Structure प्रकार का Pointer Variable होता है, जिसमें अगले Structure का Address Store रहता है। हर Structure List को node कहा जाता है।

हर Structure List में कम से कम एक Member Data का व एक Member अगले node के Address को Store करने वाले Pointer Variable का होता है। Linked List के सभी Structure उसी प्रकार से जुडे रहते है, जिस प्रकार से एक Array के सभी Element आपस में जुडे रहते हैं। लेकिन Array की तरह इनकी Location एक श्रृंखला में नहीं होती है बल्कि ये Nodes Memory में कहीं भी हो सकते हैं। ये आपस में इनके Address द्वारा जुडे रहते हैं। इसे निम्न चित्रानुसार दर्शाया गया है-

जैसे माना हम एक Structure प्रयोग करते हैं, जिसके दो Members हैं। पहला एक int प्रकार का Member है व दूसरा उसी Structure प्रकार का एक Pointer Member है, जिसमें उसी Structure के दूसरे Data का Address है। इसे निम्नानुसार बताया गया है-

[code]
            struct stud
            {
                  int roll_no;
                  struct stud *next;
            }
[/code]

यह Structure Variable Memory में निम्नानुसार Store होगा-

यदि हम दो से अधिक Members की node बनाऐं तो उस Structure का Variable Memory में निम्नानुसार Store होगा-

[code]
            {
                  int roll_no;
                  char name[30];
                  int class1;
                  float grad;
                  struct stud *next;
            }
[/code]

आइये अब देखते हैं कि Link List किस प्रकार से बनाया जाता है। हम वापस ऊपर बताए गए पहले Structure को ही लेते हैं, जिसमें दो Members हैं। इस Structure के दो Variables node1 व node2 निम्नानुसार Declare करते हैं-

[code] struct stud node1,node2; [/code]

ये दोनों Variables Memory में निम्नानुसार Space बनाऐंगे-

अब हमें इन दोनों nodes में लिंक बनाना है। Link बनाने के लिये प्रथम node node1 के next नाम के Structure प्रकार के Pointer में दूसरे node node2 की Storage Cell का Address देना होगा। Address देने के लिये हम & Operator का प्रयोग करेंगे और Dot ( . ) Operator का प्रयोग करते हुए node1 के next में node2 का Address देंगे। इसके लिये निम्नानुसार statement लिखना होगा-

[code]node1.next = &node2; [/code]

माना कि node1 Memory में 2020 Location पर Stored है और node2 Memory में 5020 Location पर Stored है, तो उपरोक्त Statement के बाद node1 में ये Address निम्नानुसार Store होगा जो node2 को Point करेगा-

अब यदि हम दोनों Nodes में कोई मान Input करें, तो ये मान निम्नानुसार Store होंगे-

[code]
node1.roll_no = 200;
node2.roll_no = 300;
node2.next = NULL;
[/code]

Node2 के next को NULL मान दिया गया है क्योंकि अभी इसे किसी अन्‍य Variable से Link नहीं करना है। यानी ये Linked List अभी यहीं समाप्त हो रही है। अब यदि हमें node2 के Members के मान Screen पर Print करने हों तो हमें Arrow Operator का प्रयोग करना पडता है। जैसे node2 के roll_no का मान Screen पर दिखाने के लिये हमें निम्नानुसार Statement लिखना होगा-

[code] printf( “\n %d”, node1.next->roll_no); [/code]

हम किसी भी Pointer को दूसरी node का Address दो प्रकार से प्रदान कर सकते हैं। एक तरीका है & Operator द्वारा जिसे पिछले प्रारूप प्रोग्राम में Use किया गया है।