लिंक्ड लिस्ट क्या है?
डेटा स्ट्रक्चर मेमोरी में डेटा को सजाने का तरीक़ा है। लिंक्ड लिस्ट नोड की एक ज़ंजीर है। हर नोड में:
- data: जो मान रखना है (संख्या, नाम…)
- next: एक पॉइंटर, यानी अगले नोड का मेमोरी पता
head वेरिएबल पहले नोड का पता रखता है। आख़िरी नोड का next NULL (Python में None) होता है, मतलब "आगे कोई नोड नहीं"। हम नोड को डिब्बा और पॉइंटर को तीर बनाते हैं: 12 → 7 → 25 → 3 → NULL।
लिंक्ड लिस्ट पुनरावर्ती (recursive) है: लिस्ट या तो ख़ाली है, या एक नोड + उसके बाद एक छोटी लिस्ट।
स्थिर (static) बनाम गतिशील (dynamic) मेमोरी
ऐरे स्थिर है: पहले से सटे हुए खानों का एक तय ब्लॉक लेते हैं। बढ़ाने के लिए सब कुछ बड़े ब्लॉक में कॉपी करना पड़ता है।
लिंक्ड लिस्ट गतिशील है: हर नोड ज़रूरत पड़ने पर ही बनता है (C/C++ में malloc/new, Python या Java में नया ऑब्जेक्ट) और हटाने पर मेमोरी लौट जाती है। नोड पास-पास होने ज़रूरी नहीं, क्योंकि हर नोड जानता है कि अगला कहाँ है।
लिस्ट को ऐरे के अंदर स्थिर रूप में भी बना सकते हैं: data[] और next[] ऐरे रखो, जहाँ next[i] अगले आइटम का इंडेक्स है (अंत के लिए −1)। परीक्षा में और बिना पॉइंटर वाली भाषाओं में यह आम है।
क्रियाएँ: ट्रैवर्स, इंसर्ट, डिलीट, सर्च, लंबाई
- ट्रैवर्स: p = head; जब तक p NULL नहीं: p.data देखो; p = p.next।
- लंबाई: ट्रैवर्स करके नोड गिनो। O(n)।
- सर्च: मान मिलने तक ट्रैवर्स। सबसे बुरी हालत n कदम, O(n)।
- शुरू में इंसर्ट: new.next = head; head = new। O(1), बस 2 पॉइंटर।
- नोड p के बाद इंसर्ट: new.next = p.next; p.next = new। क्रम ज़रूरी है! उलटा करोगे तो बाक़ी लिस्ट खो जाएगी।
- p के बाद वाला डिलीट: p.next = p.next.next (C में हटाए नोड को free करो)।
class Node:
def __init__(self, data):
self.data = data
self.next = None
def push_front(head, x):
n = Node(x); n.next = head
return n # नया head
लिंक्ड लिस्ट बनाम ऐरे, और इसका परिवार
| ऐरे | लिंक्ड लिस्ट | |
|---|---|---|
| k-वाँ आइटम | O(1) सीधी छलाँग | O(k) चलना |
| शुरू में जोड़ना/हटाना | O(n) खिसकाना | O(1) |
| आकार | तय या दोबारा कॉपी | नोड-नोड बढ़ता है |
| अतिरिक्त मेमोरी | नहीं | हर नोड में एक पॉइंटर |
डबली लिंक्ड लिस्ट: हर नोड में prev पॉइंटर भी, ताकि पीछे भी चल सको। सर्कुलर लिस्ट: आख़िरी नोड वापस पहले को दिखाता है। स्टैक वह लिस्ट है जिसमें सिर्फ़ head पर push/pop होता है; क्यू में पीछे जोड़ते और आगे से हटाते हैं।
करके देखो
5 पर्चियों पर 5 संख्याएँ लिखो। हर पर्ची के पीछे लिखो कि कमरे में अगली पर्ची कहाँ छिपी है। दोस्त को सिर्फ़ पहली पर्ची (head) दो। देखो आख़िरी तक पहुँचने में कितना समय लगा। अब शुरू में एक नई पर्ची जोड़ो: तुम्हें क्या-क्या बदलना पड़ा?
मुख्य सूत्र और परिभाषाएँ
- नोड = (data, next)
- शुरू में इंसर्ट: new.next = head; head = new → O(1)
- p के बाद इंसर्ट: new.next = p.next; p.next = new
- p के बाद डिलीट: p.next = p.next.next
- सर्च / लंबाई / k-वाँ आइटम: O(n)
- आख़िरी नोड: next = NULL (None)
हल किए गए उदाहरण
1. लिस्ट: head → 4 → 9 → 2 → NULL। शुरू में 7 जोड़ो।
new(7).next = head (नोड 4); head = new। लिस्ट: 7 → 4 → 9 → 2 → NULL।
2. 4 → 9 → 2 में से 9 हटाओ।
p = नोड 4। p.next = p.next.next, अब 4 सीधे 2 को दिखाता है। लिस्ट: 4 → 2 → NULL।
3. 7 → 4 → 9 → 2 में 2 खोजने के लिए कितने नोड देखने पड़ेंगे?
head से: 7 (1), 4 (2), 9 (3), 2 (4)। 4 नोड।
4. स्थिर लिस्ट: data = [D, A, C, B], next = [−1, 3, 0, 2], head = 1। लिस्ट पढ़ो।
इंडेक्स 1 = A, next 3 = B, next 2 = C, next 0 = D, next −1 = अंत। लिस्ट: A → B → C → D।
5. 'p.next = new; new.next = p.next' ग़लत क्यों है?
पहली लाइन के बाद p.next तो new हो चुका, तो new.next = new बनता है: एक लूप, और बाक़ी लिस्ट खो जाती है। पहले new.next सेट करो।
आम गलतियाँ
- p.next को new.next में सहेजे बिना बदल देना। बाक़ी लिस्ट खो जाती है।
- शुरू में जोड़ते या हटाते समय head अपडेट करना भूलना।
- head.next पढ़ने से पहले ख़ाली लिस्ट (head = NULL) की जाँच न करना।
- सोचना कि लिंक्ड लिस्ट में ऐरे की तरह k-वाँ आइटम तुरंत मिलता है। head से चलना पड़ता है।