Stack Implementation Using Linked List in DSA C# - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

What is the output of the stack after these operations?

Consider a stack implemented using a linked list. The following operations are performed in order:

1. Push 10
2. Push 20
3. Pop
4. Push 30

What is the printed state of the stack (top to bottom)?

DSA C#

class Node {
    public int data;
    public Node next;
    public Node(int d) { data = d; next = null; }
}

class Stack {
    private Node top;

    public void Push(int x) {
        Node newNode = new Node(x);
        newNode.next = top;
        top = newNode;
    }

    public int Pop() {
        if (top == null) throw new InvalidOperationException("Stack is empty");
        int val = top.data;
        top = top.next;
        return val;
    }

    public void PrintStack() {
        Node temp = top;
        while (temp != null) {
            Console.Write(temp.data + " -> ");
            temp = temp.next;
        }
        Console.WriteLine("null");
    }
}

Stack s = new Stack();
s.Push(10);
s.Push(20);
s.Pop();
s.Push(30);
s.PrintStack();

A 30 -> 20 -> null

B 10 -> 30 -> null

C 20 -> 30 -> 10 -> null

D 30 -> 10 -> null

💡 Hint

Remember that push adds to the top and pop removes from the top.

After pushing 10 and 20, the stack is 20 -> 10 -> null. Popping removes 20, leaving 10. Pushing 30 adds it on top, so stack is 30 -> 10 -> null.

🧠 Conceptual

intermediate

What is the time complexity of Push and Pop operations in a linked list stack?

For a stack implemented using a linked list, what is the time complexity of the Push and Pop operations?

A Push: O(1), Pop: O(1)

B Push: O(n), Pop: O(1)

C Push: O(1), Pop: O(n)

D Push: O(n), Pop: O(n)

💡 Hint

Think about where the top pointer is and how nodes are added or removed.

Both Push and Pop add or remove nodes at the head of the linked list, which takes constant time O(1).

🔧 Debug

advanced

What error occurs when popping from an empty linked list stack?

Given the following Pop method in a linked list stack, what error will occur if Pop is called on an empty stack?

public int Pop() {
    int val = top.data;
    top = top.next;
    return val;
}

A NullReferenceException

B InvalidOperationException

C IndexOutOfRangeException

D No error, returns default value

💡 Hint

Consider what happens if top is null and you try to access top.data.

If top is null, accessing top.data causes a NullReferenceException because you are dereferencing a null object.

❓ Predict Output

advanced

What is the output after pushing and popping multiple elements?

Consider the following sequence of operations on a linked list stack:

1. Push 5
2. Push 15
3. Push 25
4. Pop
5. Push 35
6. Pop

What is the printed state of the stack (top to bottom)?

DSA C#

class Node {
    public int data;
    public Node next;
    public Node(int d) { data = d; next = null; }
}

class Stack {
    private Node top;

    public void Push(int x) {
        Node newNode = new Node(x);
        newNode.next = top;
        top = newNode;
    }

    public int Pop() {
        if (top == null) throw new InvalidOperationException("Stack is empty");
        int val = top.data;
        top = top.next;
        return val;
    }

    public void PrintStack() {
        Node temp = top;
        while (temp != null) {
            Console.Write(temp.data + " -> ");
            temp = temp.next;
        }
        Console.WriteLine("null");
    }
}

Stack s = new Stack();
s.Push(5);
s.Push(15);
s.Push(25);
s.Pop();
s.Push(35);
s.Pop();
s.PrintStack();

A 5 -> 15 -> null

B 15 -> 5 -> null

C 25 -> 15 -> 5 -> null

D 35 -> 15 -> 5 -> null

💡 Hint

Trace each push and pop carefully, updating the top pointer.

Push 5: stack 5 -> null
Push 15: 15 -> 5 -> null
Push 25: 25 -> 15 -> 5 -> null
Pop removes 25: 15 -> 5 -> null
Push 35: 35 -> 15 -> 5 -> null
Pop removes 35: 15 -> 5 -> null

🧠 Conceptual

expert

Why is a linked list preferred over an array for stack implementation in some cases?

Which of the following is the best reason to choose a linked list over an array for implementing a stack?

A Linked list uses less memory than arrays always

B Linked list provides faster access to middle elements

C Linked list allows dynamic size without resizing overhead

D Linked list operations are always faster than arrays

💡 Hint

Think about resizing arrays and memory allocation.

Linked lists can grow and shrink dynamically without needing to resize or copy elements, unlike arrays which may need resizing.

Practice

1. What is the main advantage of implementing a stack using a linked list instead of an array?

easy

A. It uses less memory than an array

B. The stack can grow dynamically without a fixed size limit

C. It allows random access to elements

D. It automatically sorts the elements

Solution

1. Step 1: Understand stack size limitation in arrays

   Arrays have a fixed size, so stacks implemented with arrays have a maximum capacity.

2. Step 2: Linked list dynamic size

   Linked lists can grow or shrink dynamically by adding or removing nodes, so the stack size is limited only by memory.

3. Final Answer:

   The stack can grow dynamically without a fixed size limit -> Option B

4. Quick Check:

   Linked list stacks grow dynamically [OK]

Hint: Linked list stacks grow dynamically, arrays do not [OK]

Common Mistakes:

• Thinking linked list uses less memory always
• Assuming linked list allows random access
• Confusing stack sorting with implementation

2. Which of the following is the correct way to push an element onto a stack implemented using a linked list in C#?

easy

A. Create a new node, set its next to current top, then update top to new node

B. Create a new node, set its previous to current top, then update top to new node

C. Add the new element at the end of the linked list

D. Replace the top node's value with the new element

Solution

1. Step 1: Understand push operation in linked list stack

   Push adds a new node at the beginning (top) of the linked list.

2. Step 2: Correct pointer update

   The new node's next points to the current top, then top is updated to new node.

3. Final Answer:

   Create a new node, set its next to current top, then update top to new node -> Option A

4. Quick Check:

   Push adds node at front [OK]

Hint: Push adds node at front, update top pointer [OK]

Common Mistakes:

• Using previous pointer instead of next
• Adding node at end instead of front
• Overwriting top node value instead of adding new node

3. What will be the output after the following C# code executes?

StackNode top = null;
// Push 10
StackNode node1 = new StackNode(10);
node1.next = top;
top = node1;
// Push 20
StackNode node2 = new StackNode(20);
node2.next = top;
top = node2;
// Pop
int popped = top.data;
top = top.next;
// Print top data
Console.WriteLine(top.data);

medium

A. NullReferenceException

B. 20

C. 10

D. 0

Solution

1. Step 1: Trace push operations

   Push 10: top points to node with data 10.
   Push 20: top points to node with data 20, next points to node 10.

2. Step 2: Trace pop operation

   Pop removes top node (20), top updated to next node (10).

3. Step 3: Print top data

   Top now points to node with data 10, so output is 10.

4. Final Answer:

   10 -> Option C

5. Quick Check:

   After pop, top data = 10 [OK]

Hint: Pop removes top, next node becomes new top [OK]

Common Mistakes:

• Printing popped value instead of new top
• Confusing push order
• Not updating top after pop

4. Identify the error in this pop method for a stack implemented using a linked list:

public int Pop() {
    if (top == null) {
        Console.WriteLine("Stack Underflow");
    }
    int value = top.data;
    top = top.next;
    return value;
}

medium

A. It does not return a value when stack is empty

B. It does not update the top pointer

C. It incorrectly prints "Stack Overflow" instead of "Underflow"

D. It removes the bottom node instead of the top

Solution

1. Step 1: Check behavior when stack is empty

   If top is null, method prints message but continues to access top.data causing error or returns no value.

2. Step 2: Missing return for empty stack case

   Method should return or throw exception when stack is empty to avoid runtime error.

3. Final Answer:

   It does not return a value when stack is empty -> Option A

4. Quick Check:

   Empty stack must return or throw [OK]

Hint: Always return or throw on empty stack pop [OK]

Common Mistakes:

• Ignoring empty stack case
• Confusing overflow with underflow
• Not updating top pointer

5. You want to implement a method ReverseStack that reverses the elements of a stack implemented using a linked list without using extra data structures. Which approach is correct?

hard

A. Use a queue to dequeue and enqueue elements to reverse order

B. Traverse the linked list and swap data values of nodes pairwise

C. Create a new linked list and push elements from old stack to new stack

D. Use recursion to pop all elements, then push them back in reverse order

Solution

1. Step 1: Understand constraints

   No extra data structures allowed, so using recursion (call stack) is allowed but no explicit new lists or queues.

2. Step 2: Recursion approach

   Recursively pop all elements, then insert them back at bottom to reverse order without extra storage.

3. Step 3: Other options use extra structures

   Swapping data or using new lists or queues violates constraints or is incorrect for stack reversal.

4. Final Answer:

   Use recursion to pop all elements, then push them back in reverse order -> Option D

5. Quick Check:

   Recursion reverses stack without extra structures [OK]

Hint: Use recursion to reverse stack without extra data structures [OK]

Common Mistakes:

• Using extra linked lists or queues
• Trying to swap node data incorrectly
• Ignoring no extra structure constraint