PGDCA, BCA, B-Tech, MCA, M-Tech, B.Sc computer science राजस्थान सूचना सहायक व कंप्यूटर शिक्षक विशेष नोट्स: इस अध्याय में हम Linked List Implementation of Stack (Dynamic Stack) (स्टैक का लिंक्ड लिस्ट कार्यान्वयन: O(1) टाइम कॉम्प्लेक्सिटी) की संपूर्ण थ्योरी, मुख्य तकनीकी बिंदु, तुलनात्मक तालिका और विगत परीक्षाओं के पैटर्न पर आधारित 20 अति-महत्वपूर्ण बहुविकल्पीय प्रश्न (MCQs) विस्तृत हिंदी व अंग्रेजी व्याख्या सहित पढ़ेंगे।
Overview: A Linked List implementation of Stack (Dynamic Stack) points 'top' to the head of a singly linked list so both Push and Pop execute in O(1) time without scanning from the tail. It grows dynamically on the heap with no fixed MAX limit, requiring explicit deallocation on Pop to avoid memory leaks.
अध्याय सार: स्टैक का लिंक्ड लिस्ट कार्यान्वयन (Dynamic Stack) सिंगली लिंक्ड लिस्ट के पहले नोड (Head) को 'top' पॉइंटर बनाता है, जिससे Push और Pop दोनों O(1) समय में बिना ट्रैवर्सल के पूरे होते हैं। इसमें निश्चित MAX सीमा नहीं होती और Pop करते समय मेमोरी लीक रोकने के लिए नोड को मुक्त (free) करना आवश्यक है।
Linked List Implementation of Stack (Dynamic Stack): Detailed Notes & Architecture (स्टैक का लिंक्ड लिस्ट कार्यान्वयन: O(1) टाइम कॉम्प्लेक्सिटी)
1. Head-End Placement of Top for Strict O(1) Speed (O(1) कॉम्प्लेक्सिटी के लिए Head सिरे पर Top पॉइंटर)
[EN] In a Singly Linked List Stack, the external 'top' pointer MUST reference the head (front) node rather than the tail. Pushing a new node inserts at the front in O(1) via newNode->next = top; top = newNode;, and popping removes the front node in O(1) via top = top->next. Placing 'top' at the tail of a singly linked list would force Pop to traverse n - 1 nodes from head to locate the predecessor, degrading Pop from O(1) to O(n).
[HI] सिंगली लिंक्ड लिस्ट से स्टैक बनाते समय 'top' पॉइंटर हमेशा लिस्ट के शुरुआती सिरे (Head) पर रखा जाता है, न कि अंतिम सिरे (Tail) पर। हेड पर नया नोड जोड़ना (Push) और पहला नोड हटाना (Pop) दोनों O(1) समय में हो जाते हैं। यदि 'top' को टेल पर रखा जाए, तो Pop के समय पिछला नोड खोजने के लिए पूरी लिस्ट स्कैन करनी पड़ेगी और कॉम्प्लेक्सिटी O(n) हो जाएगी।
2. Dynamic Push & Heap-Based Overflow Behavior (डायनामिक Push और हीप मेमोरी आधारित ओवरफ्लो)
[EN] Initially top = NULL signifies an empty stack. During Push(x), a new Node is allocated dynamically from the heap via malloc() or new: if allocation fails (returning NULL or throwing std::bad_alloc), only then does Stack Overflow occur. Otherwise, newNode->data = x, newNode->next = top, and top = newNode run in constant O(1) time, removing any pre-allocated MAX size restriction.
[HI] प्रारंभ में top = NULL खाली स्टैक को दर्शाता है। Push(x) के समय हीप (Heap) से नया नोड डायनामिक रूप से आवंटित (malloc/new) किया जाता है; यदि सिस्टम की पूरी हीप मेमोरी समाप्त हो जाए तभी ओवरफ्लो होता है। अन्यथा newNode->next = top और top = newNode जोड़कर O(1) समय में डेटा सुरक्षित हो जाता है।
3. Safe Pop Sequence & Memory Leak Prevention (सुरक्षित Pop क्रम और मेमोरी लीक से बचाव)
[EN] Before popping or peeking, check isEmpty() via (top == NULL) to catch Stack Underflow. On a valid Pop, save temp = top, extract val = temp->data, advance top = top->next, and only THEN call free(temp) (or delete temp) in C/C++. Calling free(top) before advancing top causes a use-after-free dangling pointer bug, whereas skipping free(temp) causes a progressive memory leak.
[HI] Pop या Peek से पहले top == NULL जांचकर Stack Underflow रोका जाता है। वैध Pop में पहले temp = top सहेजकर val = temp->data पढ़ा जाता है, फिर top = top->next बढ़ाया जाता है और सबसे अंत में free(temp) चलाया जाता है। यदि free(temp) न किया जाए तो मेमोरी लीक होता है, और यदि पहले ही free(top) कर दिया जाए तो डैंगलिंग पॉइंटर त्रुटि आ जाती है।
4. Trade-offs: Dynamic Linked Stack vs Static Array Stack (तुलना: डायनामिक लिंक्ड स्टैक बनाम स्टेटिक एरे स्टैक)
[EN] A Linked Stack avoids wasted pre-allocated space and resizing pauses, always matching exact active element count O(n). However, each node incurs extra pointer storage (one next pointer per element), non-contiguous heap allocation weakens CPU cache spatial locality, and frequent malloc/free calls add slight allocator overhead compared to array indexing.
[HI] लिंक्ड स्टैक पहले से बड़ी मेमोरी ब्लॉक आरक्षित नहीं करता और रनटाइम जरूरत के अनुसार बढ़ता-घटता है। किंतु प्रत्येक नोड में next पॉइंटर की अतिरिक्त मेमोरी लगती है, नोड्स बिखरे रहने से CPU कैश लोकैलिटी कम होती है, और बार-बार डायनामिक मेमोरी आवंटन से थोड़ा ओवरहेड बढ़ता है।
Syntax, Formula & Technical Example (Linked List Implementation of Stack (Dynamic Stack))
struct Node { int data; struct Node *next; } *top = NULL;
void push(int x) {
struct Node *nw = malloc(sizeof(struct Node));
if (nw) { nw->data = x; nw->next = top; top = nw; }
}
int pop(void) {
if (!top) return -1; /* Underflow */
struct Node *t = top; int v = t->data;
top = top->next; free(t); return v;
}
Linked List Implementation of Stack (Dynamic Stack) Quick Reference & Comparison Table
| Dynamic Stack Property | Linked List Mechanism | Comparison vs Array Stack |
|---|---|---|
| Top Pointer Position | Points to Head (first node) of Singly Linked List | Avoids O(n) tail predecessor search during Pop |
| Empty Check (Underflow) | top == NULL | Replaces top == -1 integer index check |
| Overflow Condition | Triggers only when heap allocation returns NULL | No fixed MAX compile-time capacity constraint |
| Per-Node Space Overhead | Data payload + 1 next pointer per item | Array stack needs 0 pointers but wastes unused MAX |
Linked List Implementation of Stack (Dynamic Stack) Top 20 Bilingual MCQs with Answers
Q1. In a Singly Linked List implementation of a Stack, which end of the list should 'top' point to so both Push and Pop take O(1) time?
(सिंगली लिंक्ड लिस्ट से स्टैक बनाने पर Push और Pop दोनों O(1) समय में होने के लिए 'top' किस सिरे पर होना चाहिए?)
(A) Either head or tail gives O(1) Pop in SLL
(B) The Tail (end) of the linked list
(C) The Head (beginning) of the linked list
(D) The middle node of the list
Correct Answer: (C)
[EN] Inserting and deleting at the Head of an SLL require updating only head/top in O(1), whereas deleting at the Tail needs an O(n) scan.
[HI] SLL के शुरुआती सिरे (Head) पर जोड़ना व हटाना दोनों O(1) समय में हो जाते हैं, जबकि टेल से हटाने के लिए पिछला नोड खोजने में O(n) समय लगता है।
Q2. What happens to time complexity if someone places 'top' at the tail of a Singly Linked List (without prev pointers) and pops from tail?
(यदि कोई बिना prev पॉइंटर वाली सिंगली लिंक्ड लिस्ट के Tail पर 'top' रखे और वहीं से Pop करे, तो Pop की कॉम्प्लेक्सिटी क्या होगी?)
(A) O(log n)
(B) O(n)
(C) O(1)
(D) O(n^2)
Correct Answer: (B)
[EN] Removing the tail node in an SLL requires traversing from head to the second-to-last node, taking O(n) time.
[HI] SLL में अंतिम नोड हटाने से पहले उससे ठीक पहले वाले नोड तक पहुँचने के लिए पूरी लिस्ट स्कैन करनी पड़ती है, जिससे O(n) समय लगता है।
Q3. Which condition tests whether a Linked List Stack is empty?
(लिंक्ड लिस्ट स्टैक के खाली होने की जांच किस शर्त से की जाती है?)
(A) top->next == NULL
(B) top == MAX - 1
(C) top == -1
(D) top == NULL
Correct Answer: (D)
[EN] When no nodes are allocated, the pointer 'top' holds NULL.
[HI] जब स्टैक में कोई नोड नहीं होता, तब पॉइंटर 'top' का मान NULL रहता है।
Q4. Under what circumstance can Stack Overflow occur in a Dynamic Linked List Stack?
(डायनामिक लिंक्ड लिस्ट स्टैक में Stack Overflow किस परिस्थिति में हो सकता है?)
(A) When popping from a single-node stack
(B) Only when system heap memory is exhausted (malloc/new fails)
(C) Whenever element count reaches 100
(D) When top == -1
Correct Answer: (B)
[EN] Because nodes allocate dynamically rather than inside a fixed array, Overflow happens only if the OS/heap cannot allocate memory.
[HI] लिंक्ड स्टैक का कोई तय MAX आकार नहीं होता; इसमें ओवरफ्लो केवल तभी आता है जब हीप मेमोरी पूरी तरह समाप्त हो जाए।
Q5. During Push(x) on a non-empty Linked Stack, what is the correct order of pointer assignments for newNode?
(गैर-खाली लिंक्ड स्टैक में Push(x) करते समय नया नोड जोड़ने का सही पॉइंटर क्रम क्या है?)
(A) newNode->next = top; top = newNode;
(B) newNode->next = NULL; top = newNode;
(C) top->next = newNode; newNode->next = NULL;
(D) top = newNode; newNode->next = top;
Correct Answer: (A)
[EN] newNode->next must capture the old top first; overwriting top before saving it loses the entire existing stack!
[HI] पहले newNode->next में पुराना top जोड़ना अनिवार्य है, फिर top = newNode किया जाता है; उल्टा करने से बाकी स्टैक खो जाएगा।
Q6. In C, what bug arises if pop() advances top = top->next and returns top->data WITHOUT calling free(temp)?
(C भाषा में pop() के दौरान पुराना नोड हटाकर यदि free(temp) न चलाया जाए, तो कौन सी समस्या उत्पन्न होती है?)
(A) Infinite recursion
(B) Syntax compilation error
(C) Stack Overflow immediately
(D) Memory Leak
Correct Answer: (D)
[EN] Unfreed popped nodes stay orphaned on the heap unreachable by the program, leaking RAM over time.
[HI] पॉप किए गए नोड को मुक्त (free) न करने से वह हीप मेमोरी में अनावश्यक रूप से अटका रहता है, जिसे मेमोरी लीक कहते हैं।
Q7. What dangerous C bug occurs if you write 'free(top); top = top->next;' inside pop()?
(यदि pop() में पहले 'free(top);' और उसके बाद 'top = top->next;' लिखा जाए, तो कौन सा गंभीर बग उत्पन्न होगा?)
(A) Automatic double free protection
(B) Use-after-free (reading top->next from already freed memory)
(C) O(n) slowdown only
(D) Memory leak of top
Correct Answer: (B)
[EN] Once free(top) runs, top becomes a dangling pointer; reading top->next afterwards is undefined behavior.
[HI] पहले free(top) करने के बाद top डैंगलिंग पॉइंटर बन जाता है; उसके बाद top->next पढ़ना Use-after-free नामक गंभीर बग है।
Q8. What does peek() return in a non-empty Linked List Stack?
(गैर-खाली लिंक्ड लिस्ट स्टैक में peek() ऑपरेशन क्या लौटाता है?)
(A) top->data (without modifying top or freeing any node)
(B) top->next->data
(C) The data inside the very last node before NULL
(D) NULL pointer
Correct Answer: (A)
[EN] Since top always points to the topmost node at the head, peek() reads top->data in O(1) time.
[HI] चूँकि top हमेशा सबसे ऊपरी (Head) नोड पर रहता है, peek() बिना बदलाव किए O(1) में top->data दिखाता है।
Q9. How much memory does a single node of a Linked Stack storing a 4-byte int consume on a 64-bit system (ignoring padding)?
(64-बिट सिस्टम पर 4-बाइट int स्टोर करने वाले लिंक्ड स्टैक के एक नोड की मेमोरी (पैडिंग छोड़कर) कितनी होगी?)
(A) 8 bytes
(B) 4 bytes
(C) 20 bytes
(D) 12 bytes (4 bytes int + 8 bytes next pointer)
Correct Answer: (D)
[EN] Each SLL stack node stores the 4-byte integer payload plus one 8-byte next address pointer (12 bytes raw, 16 bytes aligned).
[HI] सिंगली लिंक्ड स्टैक नोड में 4 बाइट int और एक 8 बाइट next पॉइंटर होता है, अर्थात बिना पैडिंग के 12 बाइट्स।
Q10. If a Linked Stack currently has 1 node (top->next == NULL) and pop() executes, what becomes the value of 'top'?
(यदि लिंक्ड स्टैक में केवल 1 नोड है (top->next == NULL) और pop() चलाया जाए, तो 'top' का नया मान क्या होगा?)
(A) Points to the freed node
(B) NULL
(C) 0xFFFFFFFF
(D) Garbage address
Correct Answer: (B)
[EN] Executing top = top->next assigns NULL to top, accurately resetting the stack to its empty state.
[HI] एकमात्र नोड हटने पर top = top->next चलने से top का मान स्वतः NULL हो जाता है जो खाली स्टैक की स्थिति है।
Q11. What happens if you accidentally write 'top = newNode; newNode->next = top;' in push()?
(यदि push() में गलती से 'top = newNode; newNode->next = top;' लिख दिया जाए, तो क्या होगा?)
(A) Elements get pushed at the bottom instead of top
(B) newNode->next points to itself (a self-loop), losing access to all older stack elements
(C) It swaps the top two elements cleanly
(D) The list becomes doubly linked
Correct Answer: (B)
[EN] After top = newNode, newNode->next = top points newNode back to itself and severs the chain to previous nodes.
[HI] पहले top = newNode करने के बाद newNode->next = top लिखने से नया नोड स्वयं पर ही लूप बना लेता है और पुराने सभी तत्व खो जाते हैं।
Q12. Which statement accurately compares cache performance between an Array Stack and a Linked List Stack?
(एरे स्टैक और लिंक्ड लिस्ट स्टैक के कैश प्रदर्शन की सही तुलना कौन सी है?)
(A) Linked Stack has better cache locality because heap addresses are randomized
(B) Array Stack has superior cache locality because elements sit contiguously in RAM
(C) Linked Stack never accesses RAM
(D) Both have identical cache miss rates on all hardware
Correct Answer: (B)
[EN] Contiguous array layout benefits from hardware prefetching and cache lines, while heap nodes suffer pointer chasing misses.
[HI] एरे के तत्व मेमोरी में लगातार होने से CPU कैश लोकैलिटी बेहतर रहती है, जबकि लिंक्ड लिस्ट में नोड्स बिखरे होते हैं।
Q13. What is the worst-case time complexity of Push, Pop, Peek, and isEmpty in a Head-based Linked List Stack?
(Head-आधारित लिंक्ड लिस्ट स्टैक में Push, Pop, Peek और isEmpty की सबसे खराब (Worst-case) टाइम कॉम्प्लेक्सिटी क्या है?)
(A) O(1) for all four operations
(B) O(log n) for all operations
(C) O(n) for Push and O(1) for Pop
(D) O(1) amortized for Push and O(n) for Peek
Correct Answer: (A)
[EN] Because there is never any array resizing copy spike, every Push and Pop takes strict O(1) worst-case time (assuming O(1) allocator).
[HI] एरे रीसाइज़िंग की तरह पूरा डेटा कॉपी करने की जरूरत न होने से चारों ऑपरेशन्स की कॉम्प्लेक्सिटी O(1) होती है।
Q14. To implement a Linked Stack without passing a double pointer (**top) in C, what can push() return?
(C भाषा में डबल पॉइंटर (**top) का उपयोग किए बिना लिंक्ड स्टैक में push() को मुख्य पॉइंटर अपडेट करने के लिए क्या लौटाना चाहिए?)
(A) void
(B) The updated head/top pointer (struct Node*)
(C) The size of the node in bytes
(D) An integer status code only
Correct Answer: (B)
[EN] Returning the new top pointer allows the caller to reassign 'top = push(top, x);' cleanly in C.
[HI] यदि डबल पॉइंटर न दें, तो push() को नया शीर्ष पॉइंटर (struct Node*) लौटाना होगा ताकि कॉल करने वाला top को अपडेट कर सके।
Q15. Which scenario strongly favors choosing a Linked List Stack over a fixed-size Array Stack?
(किस परिस्थिति में फिक्स्ड-साइज एरे स्टैक की बजाय लिंक्ड लिस्ट स्टैक चुनना अधिक उपयुक्त होता है?)
(A) When maximum CPU cache hit ratio is the sole priority
(B) When random O(1) indexing into the middle of the stack is required
(C) When maximum depth is tiny (e.g., 8 elements) and memory per node must be minimized
(D) When maximum stack depth is completely unpredictable and fluctuates widely across runs
Correct Answer: (D)
[EN] Dynamic linked stacks avoid both premature Overflow and large unused static allocations when size varies unpredictably.
[HI] जब स्टैक का अधिकतम आकार पहले से पता न हो और रनटाइम पर बहुत घटता-बढ़ता हो, तब लिंक्ड लिस्ट स्टैक श्रेष्ठ रहता है।
Q16. Which of the following is NOT true about a Linked List implementation of a Stack?
(स्टैक के लिंक्ड लिस्ट कार्यान्वयन के बारे में कौन सा कथन असत्य (NOT true) है?)
(A) Push requires shifting all existing nodes one position right in O(n) time
(B) Top pointer equals NULL when the stack is empty
(C) Pop must deallocate the removed node in C/C++ to prevent memory leaks
(D) Each node stores at least a data field and a next pointer
Correct Answer: (A)
[EN] Push simply prepends one node at head in O(1) time without shifting any existing nodes.
[HI] Push करते समय पुराने नोड्स को खिसकाने की कोई आवश्यकता नहीं होती; नया नोड सीधे head पर O(1) में जुड़ जाता है।
Q17. Within Linked List Implementation of Stack (Dynamic Stack), which dynamic stack property directly maps to: "Points to Head (first node) of Singly Linked List"?
(Linked List Implementation of Stack (Dynamic Stack) में कौन सा Dynamic Stack Property सीधे "Points to Head (first node) of Singly Linked List" से संबंधित है?)
(A) Overflow Condition
(B) Per-Node Space Overhead
(C) Empty Check (Underflow)
(D) Top Pointer Position
Correct Answer: (D)
[EN] In Linked List Implementation of Stack (Dynamic Stack), 'Top Pointer Position' handles 'Points to Head (first node) of Singly Linked List' (Avoids O(n) tail predecessor search during Pop).
[HI] Linked List Implementation of Stack (Dynamic Stack) में 'Top Pointer Position' का कार्य/विवरण 'Points to Head (first node) of Singly Linked List' (Avoids O(n) tail predecessor search during Pop) है।
Q18. Which option accurately describes 'Empty Check (Underflow)' in Linked List Implementation of Stack (Dynamic Stack)?
(Linked List Implementation of Stack (Dynamic Stack) के संदर्भ में 'Empty Check (Underflow)' की सही विशेषता कौन सी है?)
(A) Points to Head (first node) of Singly Linked List
(B) Triggers only when heap allocation returns NULL
(C) Data payload + 1 next pointer per item
(D) top == NULL
Correct Answer: (D)
[EN] 'Empty Check (Underflow)' provides 'top == NULL' — key point: Replaces top == -1 integer index check.
[HI] 'Empty Check (Underflow)' का मुख्य विवरण 'top == NULL' है (Replaces top == -1 integer index check)।
Q19. In Linked List Implementation of Stack (Dynamic Stack), identify the correct parameter for the specification: "Triggers only when heap allocation returns NULL".
(Linked List Implementation of Stack (Dynamic Stack) में "Triggers only when heap allocation returns NULL" विवरण किस विकल्प के लिए सही है?)
(A) Empty Check (Underflow)
(B) Overflow Condition
(C) Per-Node Space Overhead
(D) Top Pointer Position
Correct Answer: (B)
[EN] 'Overflow Condition' corresponds to 'Triggers only when heap allocation returns NULL' (No fixed MAX compile-time capacity constraint).
[HI] 'Overflow Condition' का संबंध 'Triggers only when heap allocation returns NULL' (No fixed MAX compile-time capacity constraint) से है।
Q20. Considering Linked List Implementation of Stack (Dynamic Stack), what key behavior defines 'Per-Node Space Overhead'?
(Linked List Implementation of Stack (Dynamic Stack) में 'Per-Node Space Overhead' की मुख्य भूमिका या मान क्या है?)
(A) top == NULL
(B) Data payload + 1 next pointer per item
(C) Triggers only when heap allocation returns NULL
(D) Points to Head (first node) of Singly Linked List
Correct Answer: (B)
[EN] 'Per-Node Space Overhead' represents 'Data payload + 1 next pointer per item' (Array stack needs 0 pointers but wastes unused MAX).
[HI] 'Per-Node Space Overhead' का अर्थ/मान 'Data payload + 1 next pointer per item' है (Array stack needs 0 pointers but wastes unused MAX)।
Linked List Implementation of Stack (Dynamic Stack) — Exam FAQs
Q1: Why is a Doubly Linked List unnecessary for a standard Dynamic Stack?
सामान्य डायनामिक स्टैक के लिए डबली लिंक्ड लिस्ट की आवश्यकता क्यों नहीं होती?
[EN] All Stack operations (Push, Pop, Peek) only touch the single head node, so a forward 'next' pointer in a Singly Linked List already gives O(1) performance without wasting memory on 'prev'.
[HI] स्टैक के सभी ऑपरेशन्स केवल शीर्ष (Head) नोड पर होते हैं, जो सिंगली लिंक्ड लिस्ट से ही O(1) में हो जाते हैं; अतः prev पॉइंटर अनावश्यक मेमोरी लेगा।
Q2: Does a Dynamic Linked Stack have better worst-case Push time than a dynamic resizing array (vector)?
क्या लिंक्ड स्टैक की सबसे खराब (Worst-case) Push कॉम्प्लेक्सिटी डायनामिक एरे (Vector) से बेहतर होती है?
[EN] Yes, strictly speaking: a resizing array occasionally takes O(n) to copy elements when capacity doubles (O(1) amortized), whereas a Linked Stack never copies old items.
[HI] हाँ: डायनामिक एरे में क्षमता दोगुनी करते समय कभी-कभी O(n) कॉपी लागत आती है (अमॉर्टाइज्ड O(1)), जबकि लिंक्ड स्टैक में हर Push बिना कॉपी के होता है।
Q3: How is Stack size tracked in O(1) time in a Linked List Stack?
लिंक्ड लिस्ट स्टैक में तत्वों की कुल संख्या (Size) O(1) समय में कैसे जानी जाती है?
[EN] Maintain an integer 'count' variable incremented on Push and decremented on Pop, avoiding an O(n) traversal of all nodes.
[HI] एक अलग 'count' वैरिएबल रखकर (Push पर +1 और Pop पर -1), जिससे बार-बार पूरी लिस्ट गिनने (O(n)) की जरूरत नहीं पड़ती।
Post a Comment
Post a Comment