Linked List
Linked List एक ऐसी डेटा संरचना (Data Structure) है, जिसमें elements (nodes) sequentially connected रहते हैं, लेकिन memory में contiguous (साथ–साथ) store नहीं होते।
हर node में दो भाग होते हैं:
- Data – जिसमें actual value या जानकारी होती है।
- Link / Pointer – जो अगले node का address रखता है।
उदाहरण :
[Data | Next] → [Data | Next] → [Data | NULL]
यहाँ “NULL” का मतलब है, कि list यहीं खत्म हो जाती है।
अगर हम इसे real life में देखें, तो मान लीजिए एक बस में बैठे यात्री हैं — हर व्यक्ति (node) अपने बगल वाले व्यक्ति (next node) को जानता है। आखिरी व्यक्ति (last node) किसी को नहीं जानता — वो NULL है।
Representation of Linked List
Linked List को memory में दो मुख्य तरीकों से represent किया जा सकता है:
- Dynamic Representation (डायनामिक प्रतिरूप)
यह सबसे ज्यादा प्रयोग किया जाने वाला तरीका है। इसमें हर node को runtime पर memory में allocate किया जाता है।
इसमें होता क्या है :
- हर node अलग memory location पर होती है (non-contiguous memory)।
- हर node का “link” अगले node के address को रखता है।
- “Head” नामक pointer list की शुरुआत बताता है।
- आखिरी node का link NULL होता है।
उदाहरण से समझें :
माना कि हमें तीन students के नाम रखने हैं — राम, श्याम और मोहन।
तो memory representation कुछ इस तरह होगी:
Head → [राम | 1002] → [श्याम | 1050] → [मोहन | NULL]
हर box अलग-अलग जगह पर stored है, लेकिन pointers उन्हें जोड़ते हैं।
फायदे :
- Memory का efficient उपयोग होता है।
- Size dynamic होता है, जब चाहें node जोड़ सकते हैं।
- बीच में insertion या deletion करना आसान होता है।
नुकसान :
- Extra memory pointers में लगती है।
- Traversing (list को घूमना) थोड़ा धीमा होता है क्योंकि random access नहीं है।
- Static Representation (स्थैतिक प्रतिरूप)
कुछ पुराने systems या limited-memory environments में linked list को array के रूप में represent किया जाता है।
इस representation में दो arrays बनाए जाते हैं :
- एक data के लिए (data[])
- दूसरा link के लिए (link[])
उदाहरण :
data[] = {A, B, C, D}
link[] = {1, 2, 3, -1}
यहाँ “-1” का मतलब है list का अंत।
विशेषताएँ :
- Memory contiguous होती है।
- Implementation आसान है, लेकिन flexibility कम।
Linked List के प्रकार और उनका Representation
1️. Singly Linked List (सिंगली लिंक्ड लिस्ट)
- हर node में एक data और एक next pointer होता है।
- Head पहले node को point करता है और आखिरी node का link NULL होता है।
Example :
Paytm wallet में आपके transactions की list एक singly linked list जैसी हो सकती है — हर नया transaction पिछले से जुड़ा है।
Representation:
[10 | 200] → [20 | 350] → [30 | NULL]
2️. Doubly Linked List (डबली लिंक्ड लिस्ट)
- हर node में दो pointers होते हैं — एक previous node का और एक next node का।
- आप आसानी से आगे और पीछे दोनों दिशाओं में traverse कर सकते हैं।
Representation :
NULL ← [Prev | Data | Next] ↔ [Prev | Data | Next] ↔ [Prev | Data | NULL]
Example :
Flipkart की product browsing में जब आप “Next Product” और “Previous Product” पर क्लिक करते हैं — conceptually ये doubly linked list का उपयोग है।
3️. Circular Linked List
- इसमें last node का pointer first node को point करता है।
- इसलिए list में कोई “NULL” नहीं होता।
Representation :
[Data | Next] → [Data | Next] → [Data | Head]
Example :
IRCTC की ticket booking system में अगर waiting list circular form में बनाई जाए, तो जब एक व्यक्ति हटता है तो अगला अपने आप पहले स्थान पर आ जाता है — circular structure यही सुविधा देता है।
Linked List Memory Representation Diagram
कल्पना करें कि आपके पास 4 nodes हैं, जिनके data values हैं – 11, 22, 33, 44।
Head → [11 | 201] → [22 | 250] → [33 | 280] → [44 | NULL]
- हर node के दो हिस्से हैं — data और link (address)।
- Memory में ये nodes अलग-अलग जगहों पर हो सकते हैं।
- Head pointer पहली node की memory location रखता है।
इस तरीके से linked list memory में जुड़ी हुई chain की तरह दिखती है।
Linked List Representation के प्रमुख फायदे (Advantages)
- Dynamic Size :
Memory का उपयोग जरूरत के अनुसार होता है। - Efficient Insertion/Deletion :
Array की तरह shifting की ज़रूरत नहीं। - Flexible Memory Allocation :
Non-contiguous blocks का उपयोग। - Useful for Real-time Applications :
जैसे Hospital Emergency Queue, Railway Waiting List, Task Scheduling आदि।
Representation की कुछ सीमाएँ (Disadvantages)
- Extra Memory :
हर node में pointer होने के कारण अतिरिक्त space लगता है। - Slow Access :
Direct index access संभव नहीं, हर बार traversal करना पड़ता है। - Complex Implementation :
Pointers के कारण bug या memory leak का खतरा रहता है। - Static representation के नुकसान :
List का आकार fix रहता है और flexibility कम हो जाती है।
Difference between Linked List and Array Representation
विशेषता | Linked List | Array |
Memory Allocation | Dynamic (Heap में) | Static (Contiguous) |
Size | Flexible | Fixed |
Insertion/Deletion | आसान | मुश्किल (Shift करना पड़ता है) |
Access Time | Sequential | Direct (Index-based) |
Extra Memory | Pointer के लिए जरूरी | नहीं |
Practical Use | Dynamic Data Handling | Fixed Data Storage |
