Node क्लास और सूची निर्माण
Node dataclass परिभाषित कीजिए, नोड को मैन्युअल रूप से जोड़कर सूचियाँ बनाइए और संकेतक परिवर्तनों को दृश्य रूप से समझने के लिए insert/delete/print सहायक लिखिए।
Node क्लास और सूची निर्माण, CoddyKit पर कोडिंग साक्षात्कार की तैयारी का एक निःशुल्क पाठ है। यह 4 में से 1वाँ पाठ है। आप नीचे पूरा पाठ निःशुल्क पढ़ सकते हैं—फिर अंतर्निहित कोड संपादक और 24/7 एआई ट्यूटर के साथ ब्राउज़र में इसका व्यावहारिक अभ्यास कर सकते हैं। यह कोडिंग साक्षात्कार की तैयारी सीखने के मार्ग का हिस्सा है और आपकी प्रगति वेब तथा CoddyKit ऐप पर सिंक होती रहती है। कोडिंग साक्षात्कार की तैयारी पाठ्यक्रम में कुल 4 पाठ शामिल हैं।
लिंक्ड लिस्ट क्या होती है
लिंक्ड लिस्ट नोड्स का एक क्रम होती है, जिसमें प्रत्येक नोड एक मान और अगले नोड का पॉइंटर रखता है। सरणियों के विपरीत, नोड मेमोरी में अलग-अलग स्थानों पर होते हैं — इंडेक्स-आधारित O(1) पहुँच उपलब्ध नहीं होती। इसके बदले, किसी ज्ञात स्थान पर तत्वों को खिसकाए बिना O(1) में जोड़ने और हटाने की सुविधा मिलती है।
पाइथन में हम प्रत्येक नोड को एक छोटे वर्ग के रूप में दर्शाते हैं, जिसमें val और next होते हैं। नोड्स को एक-दूसरे से जोड़ने पर लिस्ट बनती है; अंतिम नोड का next अंत का संकेत देने के लिए None होता है।
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
# Build: 1 -> 2 -> 3 -> None
head = ListNode(1)
head.next = ListNode(2)
head.next.next = ListNode(3)
# Traverse and print
curr = head
while curr:
print(curr.val, end=' -> ')
curr = curr.next
print('None')सरणियों से लिस्ट बनाना
साक्षात्कारों में अक्सर आपको एक सूची दी जाएगी और उसका लिंक्ड-लिस्ट रूप बनाने के लिए कहा जाएगा, या इसका उल्टा करने के लिए कहा जाएगा। सहायक फ़ंक्शन build और to_list याद रखने योग्य हैं: build किसी सरणी से नोड्स को जोड़ता है, और to_list मानों को आसानी से सत्यापित करने के लिए लिस्ट पर आगे बढ़ते हुए उन्हें एकत्र करता है।
n तत्वों से लिंक्ड लिस्ट बनाने में O(n) समय और O(n) स्थान लगता है। डमी हेड नोड का उपयोग करने से उन सीमांत स्थितियों को संभालना आसान हो जाता है, जहाँ पहला नोड बदल सकता है।
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def build(arr):
dummy = ListNode(0)
curr = dummy
for val in arr:
curr.next = ListNode(val)
curr = curr.next
return dummy.next
def to_list(head):
result = []
while head:
result.append(head.val)
head = head.next
return result
head = build([1, 2, 3, 4, 5])
print(to_list(head)) # [1, 2, 3, 4, 5]हेड और टेल पर जोड़ना
हेड पर नया नोड जोड़ना O(1) का कार्य है: नोड बनाइए, उसके next को पुराने हेड की ओर इंगित कीजिए और नए नोड को हेड के रूप में लौटाइए। टेल पर जोड़ने के लिए अंतिम नोड तक जाना (O(n)) और फिर नए नोड को जोड़ना आवश्यक है।
डमी हेड नोड का उपयोग करने से दोनों प्रकार के जोड़ने में खाली लिस्ट की विशेष स्थिति समाप्त हो जाती है, क्योंकि dummy.next हमेशा वास्तविक हेड होता है।
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def insert_head(head, val):
return ListNode(val, head) # O(1)
def insert_tail(head, val):
new_node = ListNode(val)
if not head:
return new_node
curr = head
while curr.next:
curr = curr.next
curr.next = new_node
return head
head = None
for v in [1, 2, 3]:
head = insert_tail(head, v)
head = insert_head(head, 0)
curr = head
while curr:
print(curr.val, end=' -> ')
curr = curr.next
print('None') # 0 -> 1 -> 2 -> 3 -> Noneमान के आधार पर नोड हटाना
दिए गए मान वाला पहला नोड हटाने के लिए prev पॉइंटर को curr से एक कदम पीछे रखिए। जब curr.val == target हो, तो नोड को छोड़कर आगे बढ़ने के लिए prev.next = curr.next सेट कीजिए। यहाँ डमी हेड विशेष रूप से उपयोगी है, क्योंकि इससे वास्तविक हेड नोड को हटाने की विशेष स्थिति समाप्त हो जाती है — prev हमेशा डमी से शुरू हो सकता है।
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def delete_val(head, target):
dummy = ListNode(0)
dummy.next = head
prev, curr = dummy, head
while curr:
if curr.val == target:
prev.next = curr.next
break
prev, curr = curr, curr.next
return dummy.next
def to_list(h):
r = []
while h:
r.append(h.val)
h = h.next
return r
head = None
for v in [1, 2, 3, 2, 4]:
dummy2 = ListNode(v)
dummy2.next = head
head = dummy2 # build in reverse for speed
head = delete_val(head, 2)
print(to_list(head))पॉइंटर में बदलावों को देखना
पॉइंटर अपडेट करते समय किसी नोड का संदर्भ खो देना एक सामान्य गलती है। उसे अधिलेखित करने से पहले हमेशा next को सुरक्षित रखिए: saved = curr.next, फिर उसे दोबारा निर्दिष्ट कीजिए। लिस्ट को तीरों से जुड़े डिब्बों के रूप में बनाइए और कोड लिखने से पहले कागज़ पर प्रत्येक पॉइंटर अपडेट का अनुकरण कीजिए। यह दृश्य तरीका साक्षात्कारों के दौरान होने वाली अनजाने नल-पॉइंटर त्रुटियों को रोकता है।
याद रखिए: पाइथन में curr.next को दोबारा निर्दिष्ट करने से curr स्वयं प्रभावित नहीं होता, लेकिन उसे सुरक्षित रखने से पहले curr.next का संदर्भ खो देने पर आप आगे नहीं बढ़ सकते।
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
# Demonstrate safe pointer update
def swap_first_two(head):
if not head or not head.next:
return head
first = head
second = head.next
# Save third before losing the reference
third = second.next
# Rewire
second.next = first
first.next = third
return second
from functools import reduce
nodes = [ListNode(i) for i in range(1, 5)]
for i in range(len(nodes) - 1):
nodes[i].next = nodes[i+1]
head = swap_first_two(nodes[0])
curr = head
while curr:
print(curr.val, end=' ')
curr = curr.next
# 2 1 3 4सिंगली बनाम डबल्ली लिंक्ड लिस्ट
सिंगली लिंक्ड लिस्ट केवल next पॉइंटर रखती है; उसमें एक ही दिशा में आगे बढ़ा जा सकता है। डबल्ली लिंक्ड लिस्ट prev और next दोनों रखती है, जिससे O(1) में पीछे की ओर बढ़ना और किसी सीधे नोड संदर्भ के साथ O(1) में नोड हटाना संभव होता है; इसके लिए prev को ट्रैक करने वाले लूप की आवश्यकता नहीं होती।
पाइथन का collections.deque डबल्ली लिंक्ड लिस्ट के रूप में कार्यान्वित है, इसलिए यह O(1) में appendleft और popleft का समर्थन करता है। साक्षात्कारों में आप सिंगली लिंक्ड लिस्ट लागू करेंगे; डबल्ली लिंक्ड लिस्ट LRU कैश के डिज़ाइन में दिखाई देती हैं।
class DLNode:
def __init__(self, val=0):
self.val = val
self.prev = None
self.next = None
# Build doubly linked: 1 <-> 2 <-> 3
a, b, c = DLNode(1), DLNode(2), DLNode(3)
a.next = b; b.prev = a
b.next = c; c.prev = b
# Traverse forward
curr = a
while curr:
print(curr.val, end=' <-> ')
curr = curr.next
print('None')
# Traverse backward from c
curr = c
while curr:
print(curr.val, end=' <-> ')
curr = curr.prev
print('None')लंबाई, टेल और प्रदर्शित करने वाले सहायक फ़ंक्शन
लिंक्ड-लिस्ट के किसी भी साक्षात्कार के दौरान आपके पास तीन उपयोगी सहायक फ़ंक्शन होने चाहिए: length(head) O(n) में नोड्स की गिनती करता है, tail(head) O(n) में अंतिम नोड लौटाता है, और print_list(head) डिबगिंग के लिए लिस्ट को व्यवस्थित रूप में दिखाता है। इनके तैयार होने पर आप सहायक तर्क को दोबारा लिखने के बजाय मुख्य एल्गोरिदम पर ध्यान दे सकते हैं।
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def length(head):
count = 0
while head:
count += 1
head = head.next
return count
def tail(head):
while head and head.next:
head = head.next
return head
def print_list(head):
parts = []
while head:
parts.append(str(head.val))
head = head.next
print(' -> '.join(parts) + ' -> None')
# Build and test
nodes = [ListNode(i) for i in [10, 20, 30, 40]]
for i in range(len(nodes) - 1):
nodes[i].next = nodes[i+1]
head = nodes[0]
print('Length:', length(head))
print('Tail:', tail(head).val)
print_list(head)लिंक्ड लिस्ट पर दो-पॉइंटर की तैयारी
दो-पॉइंटर तकनीक लिंक्ड लिस्ट के लिए उतनी ही महत्वपूर्ण है जितनी सरणियों के लिए, लेकिन यहाँ पॉइंटर इंडेक्स के बजाय लिंक्ड-लिस्ट नोड होते हैं। सामान्य व्यवस्थाओं में मध्य-बिंदु खोजने और चक्र पहचानने के लिए धीमा और तेज़ पॉइंटर शामिल हैं, जिसमें तेज़ पॉइंटर 2 गुना तेज़ चलता है, तथा हटाने और उलटने के लिए पूर्ववर्ती और वर्तमान की जोड़ी शामिल है।
दोनों पॉइंटर को हमेशा स्पष्ट रूप से आरंभ कीजिए और नल-समाप्ति जाँच सावधानी से कीजिए — fast and fast.next तब नल-पॉइंटर त्रुटियों को रोकता है जब तेज़ पॉइंटर अंत के पास हो।
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
# Find middle node using slow-fast pointers
def find_middle(head):
slow = fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
return slow # for even length, returns second of two middle nodes
nodes = [ListNode(i) for i in range(1, 6)]
for i in range(len(nodes) - 1):
nodes[i].next = nodes[i+1]
print(find_middle(nodes[0]).val) # 3 (middle of 1->2->3->4->5)डमी हेड का प्रारूप
डमी हेड (सेंटिनल नोड) प्रारूप लिंक्ड-लिस्ट समस्याओं की सबसे उपयोगी युक्तियों में से एक है। मान 0 वाले डमी नोड को शुरुआत में जोड़कर आपको खाली लिस्ट या वास्तविक हेड में बदलाव के लिए कभी अलग स्थिति नहीं लिखनी पड़ती। आपका परिणाम हमेशा dummy.next होता है। यह प्रारूप क्रमबद्ध लिस्ट को मिलाने, अंत से nवाँ नोड हटाने, लिस्ट को विभाजित करने और कई अन्य समस्याओं में दिखाई देता है।
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
# Remove all nodes with val == target (may include head)
def remove_all(head, target):
dummy = ListNode(0)
dummy.next = head
curr = dummy
while curr.next:
if curr.next.val == target:
curr.next = curr.next.next # skip the node
else:
curr = curr.next
return dummy.next
def to_list(h):
r = []
while h:
r.append(h.val)
h = h.next
return r
nodes = [ListNode(v) for v in [1, 2, 6, 3, 4, 5, 6]]
for i in range(len(nodes) - 1):
nodes[i].next = nodes[i+1]
head = remove_all(nodes[0], 6)
print(to_list(head)) # [1, 2, 3, 4, 5]समय और स्थान जटिलता
अधिकांश लिंक्ड-लिस्ट क्रियाओं की जटिलताएँ इस प्रकार होती हैं। इंडेक्स से पहुँचना: O(n) — हेड से आगे बढ़ना आवश्यक है। ज्ञात नोड पर जोड़ना या हटाना: O(1) — केवल पॉइंटर फिर से जोड़ने होते हैं। स्थिति k पर जोड़ना या हटाना: O(k) — पहले k तक आगे बढ़ना होता है। खोज: O(n) — सबसे खराब स्थिति में पूरी लिस्ट देखनी पड़ती है। सभी यथास्थान क्रियाओं के लिए स्थान O(1) है, अतिरिक्त डेटा संरचनाओं को छोड़कर।
इसकी तुलना सरणियों से कीजिए: सरणियाँ O(1) पहुँच देती हैं, लेकिन तत्वों को खिसकाने के कारण जोड़ने या हटाने में O(n) समय लेती हैं। जब मनमाने स्थानों पर बार-बार जोड़ना और हटाना हो, तब लिंक्ड लिस्ट बेहतर होती हैं।
लिंक्ड लिस्ट के लिए साक्षात्कार सुझाव
किसी भी लिंक्ड-लिस्ट का कोड लिखने से पहले लिस्ट को डिब्बों और तीरों के साथ दृश्य रूप में बनाइए। सीमांत स्थितियों को ज़ोर से स्पष्ट कीजिए: खाली लिस्ट, एक नोड, और सम बनाम विषम लंबाई। सीमा स्थितियों को सरल बनाने के लिए डमी हेड का उपयोग कीजिए। शुरुआत में ही हमेशा if not head जाँचिए। कोड लिखने के बाद साक्षात्कारकर्ता से पहले पॉइंटर संबंधी त्रुटियाँ पकड़ने के लिए तीन-नोड वाली लिस्ट पर अपने समाधान का अनुकरण कीजिए।
लिंक्ड-लिस्ट की अधिकांश त्रुटियाँ तीन कारणों से होती हैं: उसे अधिलेखित करने से पहले next को सुरक्षित रखना भूल जाना, समाप्ति की शर्त में एक की त्रुटि होना, या हेड बदलने की सीमांत स्थिति को न संभालना — डमी नोड तीसरी समस्या को पूरी तरह समाप्त कर देता है।
त्वरित जाँच
इस पाठ में सिखाई गई डेटा संरचनाएँ और एल्गोरिदम — कोडिंग इंटरव्यू की तैयारी की अवधारणाओं की अपनी समझ जाँचें।
पाठ का पुनरावलोकन
इस पाठ में आपने सीखा: लिंक्ड लिस्ट val और next फ़ील्ड वाली नोड वस्तुओं से बनती है, डमी हेड का प्रारूप हेड बदलने वाली सीमांत स्थितियों को समाप्त करता है, और धीमे-तेज़ दो-पॉइंटर की व्यवस्था मध्य-बिंदु खोजने और चक्र पहचानने का आधार है। अगले भाग में हम लिंक्ड लिस्ट को उलटने पर काम करेंगे — यह पॉइंटर से जुड़ी सबसे अधिक पूछी जाने वाली समस्याओं में से एक है।
एआई शिक्षक के साथ कोडिंग साक्षात्कार की तैयारी सीखें — निःशुल्क
अपने ब्राउज़र में वास्तविक कोड लिखें और चलाएँ, चौबीसों घंटे एआई शिक्षक से तुरंत सहायता पाएँ, और वेब या ऐप पर वहीं से शुरू करें जहाँ आपने छोड़ा था।
- पाठ्यक्रम
- 90
- पाठ
- 360
अक्सर पूछे जाने वाले प्रश्न
क्या “Node क्लास और सूची निर्माण” पाठ निःशुल्क है?
हाँ—“Node क्लास और सूची निर्माण” का पूरा पाठ यहाँ वेब पर निःशुल्क पढ़ा जा सकता है। इंटरैक्टिव अभ्यास (अंतर्निहित कोड संपादक और 24/7 एआई ट्यूटर) करने और कोडिंग साक्षात्कार की तैयारी पाठ्यक्रम का बाकी हिस्सा अनलॉक करने के लिए CoddyKit PRO लें। कोडिंग साक्षात्कार की तैयारी पाठ्यक्रम में कुल 4 पाठ शामिल हैं।
“Node क्लास और सूची निर्माण” में मैं क्या सीखूँगा?
Node dataclass परिभाषित कीजिए, नोड को मैन्युअल रूप से जोड़कर सूचियाँ बनाइए और संकेतक परिवर्तनों को दृश्य रूप से समझने के लिए insert/delete/print सहायक लिखिए। आप ब्राउज़र में सीधे चलाए जाने वाले व्यावहारिक कोड के साथ कोडिंग साक्षात्कार की तैयारी का अभ्यास करते हैं, और पाठ पूरा करते समय 24/7 एआई ट्यूटर आपके प्रश्नों के उत्तर देता है।
क्या कोडिंग साक्षात्कार की तैयारी शुरू करने के लिए मुझे किसी अनुभव की आवश्यकता है?
पहले के अनुभव की आवश्यकता नहीं है। CoddyKit पर कोडिंग साक्षात्कार की तैयारी शुरुआती से लेकर उन्नत शिक्षार्थियों तक सभी के लिए व्यवस्थित किया गया है, इसलिए आप यहीं से या शुरुआत से सीखना शुरू कर सकते हैं और अपनी गति से आगे बढ़ सकते हैं। यह 4 में से 1वाँ पाठ है।
“Node क्लास और सूची निर्माण” पाठ पूरा करने में कितना समय लगता है?
CoddyKit का अधिकांश पाठ लगभग 5–10 मिनट में पूरा हो जाता है। हर पाठ छोटा और संवादात्मक है, इसलिए आप लगातार प्रगति करते हैं और वेब या ऐप पर वहीं से सीखना जारी रख सकते हैं जहाँ आपने छोड़ा था।
क्या मैं इस कोडिंग साक्षात्कार की तैयारी पाठ में कोड लिख और चला सकता हूँ?
हाँ। हर कोडिंग साक्षात्कार की तैयारी पाठ में एक अंतर्निर्मित कोड संपादक शामिल है, जिससे आप सीधे अपने ब्राउज़र में वास्तविक कोड लिख और चला सकते हैं और तुरंत एआई प्रतिक्रिया पा सकते हैं—स्थानीय सेटअप की आवश्यकता नहीं है।
इस पाठ्यक्रम के सभी पाठ
- Node क्लास और सूची निर्माण
- लिंक्ड सूची को उलटना
- Floyd के एल्गोरिदम से चक्र पहचान
- मिलाना, विभाजित करना और अंत से Nवाँ ढूँढ़ना