Linked-list updates, deletion और storage reuse
उद्देश्य और representation contracts
Front insertion से आगे known predecessor के बाद insertion, सभी positions पर deletion और storage reuse सीखें। उसी singly linked list के दो models हैं: heap nodes के pointers, तथा bounded array slots के integer indices। Execution sequential है, live nodes अलग हैं और cycles नहीं। Search position या key के अनुसार स्पष्ट है। Deallocation में exclusive ownership मानते हैं; shared lists यहाँ नहीं।
Bounded model में slots 0..N−1 valid हैं और NIL=−1 absent link है। value[i],next[i] slot बताते हैं। head live chain का पहला slot और freeHead unused slots की disjoint free list का पहला slot है। हर slot ठीक एक बार live या free chain में है। NIL से arrays index न करें। Pointer model में NULL absent link और malloc/free acquisition/release हैं।
1. Known live predecessor के बाद insert
A→B→C list में p, B को बताता है। नया X पहले C को point करे, फिर B से X की link बने:
new.next = p.next p.next = new
परिणाम A→B→X→C। Assignments उलटने पर new.next खुद new बन जाएगा और saved suffix न हो तो पुरानी chain कटेगी। Allocation तथा initialization सफल होने के बाद ही live structure बदलें। Predecessor ज्ञात हो तो rewiring O(1), लेकिन उसे खोजना O(n) हो सकता है। Length-n list में zero-based insertion position k के लिए 0≤k≤n। k=0 में head बदलता है; k>0 में k−1 खोजें, append के लिए पुराना tail। Maintained tail pointer append O(1) बनाता है, arbitrary predecessor search नहीं।
Bounded trace: N=5, head=2, live 2→0→4→NIL, values A,B,C। Free chain 1→3→NIL। Slot 0 के बाद X insert करें। Slot 1 pop: freeHead=next[1]=3। value[1]=X, next[1]=next[0]=4, फिर next[0]=1। Live 2→0→1→4 और freeHead=3। Physical order 0,1,2,3,4 का logical traversal से संबंध नहीं। freeHead=NIL हो तो full report करके पुरानी list unchanged रखें; यह bounded allocation failure है।
2. Predecessor से delete; head अलग case
Known predecessor p के successor को delete करने से पहले p.next absent न हो। victim=p.next और successor=victim.next बचाएँ; p.next=successor करें, फिर victim release। Tail delete में absent link लगता है। Head का ordinary predecessor नहीं। head absent हो तो empty list unchanged रखें; अन्यथा victim=head, head=head.next, फिर victim release। Singleton में head absent होगा। Maintained tail हो तो उसका node हटाने पर tail predecessor बनेगा; sole node हटे तो head/tail दोनों absent।
उसी trace में slot 0 का B हटाएँ। Predecessor slot 2, successor slot 1 है। next[2]=1 करें। Freed slot 0 को free list में push: next[0]=freeHead=3, freeHead=0। Live 2→1→4 (A,X,C), free 0→3। पुरानी 0→1 link अब live link नहीं; next[0] free list का field है। Pointer node को free के बाद पढ़ना C में undefined है। Bounded slot पढ़ना physically in-bounds हो सकता है, लेकिन logically free/दूसरे object के storage को access करता है।
Key का पहला matching node हटाने के लिए prev और cur रखें। शुरू में prev=absent,cur=head। Match या absent मिलने तक prev=cur,cur=cur.next करें। Key नहीं मिले तो list unchanged। prev absent हो तो head बदलें, अन्यथा prev.next। Duplicate values node identity नहीं हैं; इसलिए “पहला matching key” policy जरूरी है।
3. Release/reuse और stale aliases
आगे C के बाद Y append करने के लिए freeHead से slot 0 लें। freeHead=3; value[0]=Y,next[0]=NIL,next[4]=0। Live 2→1→4→0 अर्थात A,X,C,Y। Index 0 पहले B था, अब Y है। Saved external index 0 deletion/reuse के पार stable node identity नहीं। Pointer model में same address reuse से dangling pointer फिर valid नहीं हो जाता। Long-lived handles को अलग validity scheme चाहिए; यहाँ released node के सभी external handles invalid मानते हैं।
Pointer list clear करते समय हर free से पहले next बचाएँ। Bounded list में next को free-chain link बनाने से पहले live successor बचाएँ। Slot दो बार release करने से free-list cycle बन सकती है; heap node double-free undefined behavior है। Stale next या missing head update से nodes unreachable/leaked हो सकते हैं, भले सभी indices array bounds में हों।
4. O(1) deletion की वास्तविक शर्त
Predecessor का pointer/index मिला हो तो successor unlink O(1)। केवल target pointer से singly linked list में general O(1) deletion नहीं, क्योंकि incoming link ढूँढनी है। “Successor का value target में copy कर successor हटाना” tail पर नहीं चलता, physical surviving node बदलता है और identity/ownership contract तोड़ सकता है। यह general deletion का विकल्प नहीं। Doubly linked list में previous link होने से known node local unlink हो सकता है, लेकिन दोनों neighbors और head/tail ठीक करने होते हैं।
Invariants और costs
हर operation के बाद live chain का order, termination और exact count जाँचें। Bounded pool में live/free disjointness तथा counts का sum N भी जाँचें। Search worst-case O(n); supplied predecessor के बाद update O(1), allocator cost छोड़कर। Pointer model में n live nodes का O(n) storage, fixed pool में O(N) slots। Logical position, key value, physical index और object identity चार अलग चीजें हैं।
मौलिक अभ्यास: छह single-correct MCQs
ये मौलिक शिक्षण प्रश्न हैं, previous-year questions नहीं। एक विकल्प चुनें।
P01. Suffix बचाकर p के बाद new insert करने का क्रम?
A. p.next=new; new.next=p.next; B. new.next=p.next; p.next=new; C. new.next=p; p.next=NULL; D. head=new; new.next=NULL;
उत्तर: B
A: दूसरी assignment new को self-point कराती है।
B: p redirect करने से पहले old successor new में रखें।
C: Successor खोता है और गलत दिशा बनती है।
D: यह पुरानी list छोड़ता है, p के बाद insert नहीं।
P02. Live 2→0→4, free 1→3। Slot 0 के बाद slot 1 insert करें। नया live order?
A. 0→1→2→4 B. 2→1→0→4 C. 2→0→1→4 D. 2→0→4→1
उत्तर: C
A: Physical indices list order नहीं तय करते।
B: यह slot 0 से पहले insertion है।
C: पुरानी 0→4 link अब 0→1→4 है।
D: यह tail append है।
P03. Head/tail maintained हों, sole node हटाने पर क्या बचे?
A. दोनों absent B. केवल head absent C. केवल tail absent D. दोनों released node पर
उत्तर: A
A: Empty-list invariant में दोनों absent हैं।
B: Stale tail invariant तोड़ता है।
C: Stale head invariant तोड़ता है।
D: Released storage live node नहीं रह सकता।
P04. Auxiliary indexing बिना n-node singly linked list में predecessor search की worst-case cost?
A. O(1) B. O(log n) C. O(n²) D. O(n)
उत्तर: D
A: Known predecessor के बाद rewiring constant है।
B: Random midpoint/search-tree guarantee नहीं।
C: एक traversal पर्याप्त है।
D: लगभग पूरी list traverse करनी पड़ सकती है।
P05. Freed slot 0 नए node को मिला। Saved old handle 0:
A. पुराना node पहचानता है B. अपने-आप नया index बनता है C. Bounds में होने पर भी identity के रूप में stale है D. Allocator निश्चित गलत है
उत्तर: C
A: पुराना logical node समाप्त है।
B: Plain integer स्वतः rewrite नहीं होते।
C: उसी storage position में नई identity हो सकती है।
D: Reuse सही है; clients old handles invalidate करें।
P06. Known singly linked target के successor-copy deletion trick की सामान्य सीमा?
A. हमेशा O(n²) B. Tail नहीं हटा सकता और identity तोड़ सकता है C. Sorted list चाहिए D. Stored values नहीं बदलता
उत्तर: B
A: Local copying constant हो सकती है।
B: Tail पर successor नहीं; अन्यत्र दूसरा physical node हटता है।
C: Sorting से यह सीमा संबंधित नहीं।
D: Trick target value overwrite करता है।
स्रोत और दायरा
GATE CS 2026 के मौजूदा आधार-पाठों का सीमित विस्तार। पूरे विषय की पूर्णता का दावा नहीं। उदाहरण और प्रश्न मौलिक हैं।
प्रगति सहेजने के लिए साइन इन करें। साइन इन