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

Challenge - 5 Problems

❓ Predict Output

intermediate

What is the output after pushing and popping elements?

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

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

What is the printed state of the stack from top to bottom?

DSA Typescript

class Node {
  value: number;
  next: Node | null;
  constructor(value: number) {
    this.value = value;
    this.next = null;
  }
}

class Stack {
  top: Node | null = null;

  push(value: number) {
    const newNode = new Node(value);
    newNode.next = this.top;
    this.top = newNode;
  }

  pop(): number | null {
    if (!this.top) return null;
    const poppedValue = this.top.value;
    this.top = this.top.next;
    return poppedValue;
  }

  printStack(): string {
    let current = this.top;
    let result = '';
    while (current) {
      result += current.value + ' -> ';
      current = current.next;
    }
    return result + 'null';
  }
}

const stack = new Stack();
stack.push(10);
stack.push(20);
stack.push(30);
stack.pop();
stack.push(40);
console.log(stack.printStack());

A 30 -> 20 -> 10 -> null

B 40 -> 30 -> 20 -> 10 -> null

C 40 -> 20 -> 10 -> null

D 20 -> 10 -> null

💡 Hint

Remember that pop removes the top element, and push adds a new top.

After pushing 10, 20, 30, the stack is 30 -> 20 -> 10 -> null.

Pop removes 30, so stack becomes 20 -> 10 -> null.

Push 40 adds 40 on top, so stack is 40 -> 20 -> 10 -> null.

🧠 Conceptual

intermediate

What is the time complexity of push and pop operations in a stack implemented using a linked list?

Consider a stack implemented using a linked list. What is the time complexity of the push and pop operations?

A Both push and pop are O(1)

B Push is O(n), pop is O(1)

C Push is O(1), pop is O(n)

D Both push and pop are O(n)

💡 Hint

Think about how many nodes you need to traverse for push and pop.

Both push and pop only change the top pointer and possibly one node's next pointer, so both are constant time O(1).

🔧 Debug

advanced

What error occurs when popping from an empty stack?

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

pop(): number {
  const poppedValue = this.top.value;
  this.top = this.top.next;
  return poppedValue;
}

A ReferenceError: top is not defined

B TypeError: Cannot read property 'value' of null

C SyntaxError: Unexpected token

D No error, returns undefined

💡 Hint

What happens if this.top is null and you try to access this.top.value?

If the stack is empty, this.top is null. Accessing this.top.value causes a TypeError because null has no property 'value'.

❓ Predict Output

advanced

What is the stack state after multiple push and pop operations?

Given the following sequence of operations on an empty stack implemented with a linked list:

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

What is the printed stack state from top to bottom?

DSA Typescript

class Node {
  value: number;
  next: Node | null;
  constructor(value: number) {
    this.value = value;
    this.next = null;
  }
}

class Stack {
  top: Node | null = null;

  push(value: number) {
    const newNode = new Node(value);
    newNode.next = this.top;
    this.top = newNode;
  }

  pop(): number | null {
    if (!this.top) return null;
    const poppedValue = this.top.value;
    this.top = this.top.next;
    return poppedValue;
  }

  printStack(): string {
    let current = this.top;
    let result = '';
    while (current) {
      result += current.value + ' -> ';
      current = current.next;
    }
    return result + 'null';
  }
}

const stack = new Stack();
stack.push(5);
stack.push(15);
stack.pop();
stack.push(25);
stack.push(35);
stack.pop();
stack.pop();
console.log(stack.printStack());

A null

B 25 -> 5 -> null

C 15 -> 5 -> null

D 5 -> null

💡 Hint

Track each push and pop carefully from top to bottom.

Push 5: stack is 5 -> null

Push 15: 15 -> 5 -> null

Pop removes 15: 5 -> null

Push 25: 25 -> 5 -> null

Push 35: 35 -> 25 -> 5 -> null

Pop removes 35: 25 -> 5 -> null

Pop removes 25: 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 when implementing a stack?

A Linked list allows dynamic size without resizing, arrays require resizing which is costly

B Arrays use more memory than linked lists for the same number of elements

C Linked lists provide faster access to elements by index than arrays

D Arrays cannot implement stack operations like push and pop

💡 Hint

Think about memory allocation and resizing costs.

Linked lists grow dynamically without needing to resize or copy elements, unlike arrays which may need costly resizing operations.

Practice

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

easy

A. It allows random access to elements

B. It uses less memory than an array

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

D. It is faster to access elements by index

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 stack size is not fixed.

3. Final Answer:

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

4. Quick Check:

   Linked list stacks grow dynamically = A [OK]

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

Common Mistakes:

• Thinking linked lists use less memory always
• Confusing stack with queue behavior
• Assuming random access is possible in linked lists

2. Which of the following is the correct TypeScript syntax to define a node class for a linked list stack?

easy

A. class Node { value: number; next: Node; constructor(value: number) { this.value = value; this.next = null; } }

B. class Node { value: number; next: Node | null; constructor(value: number) { this.value = value; this.next = null; } }

C. class Node { value: number; next: null; constructor(value: number) { this.value = value; this.next = null; } }

D. class Node { value: number; next: any; constructor(value: number) { this.value = value; this.next = undefined; } }

Solution

1. Step 1: Check next pointer type

   In a linked list, next can be another node or null if it's the last node.

2. Step 2: Verify constructor initialization

   The constructor sets value and initializes next to null.

3. Final Answer:

   class Node { value: number; next: Node | null; constructor(value: number) { this.value = value; this.next = null; } } -> Option B

4. Quick Check:

   next can be Node or null = B [OK]

Hint: next must allow null for last node [OK]

Common Mistakes:

• Not allowing next to be null
• Initializing next as undefined
• Using incorrect type for next

3. Given the following TypeScript code for a stack push operation, what will be the top node's value after pushing 10, then 20?

medium

A. undefined

B. 10

C. null

D. 20

Solution

1. Step 1: Understand push operation

   Push adds a new node at the top, so the last pushed value becomes the top.

2. Step 2: Trace pushing 10 then 20

   First push 10: top.value = 10; then push 20: top.value = 20 (new node).

3. Final Answer:

   20 -> Option D

4. Quick Check:

   Last pushed value is top = 20 [OK]

Hint: Top always holds last pushed value [OK]

Common Mistakes:

• Assuming bottom value is top
• Confusing push with pop
• Not updating top pointer

4. Identify the error in this pop method of a linked list stack implementation:

pop(): number | null {
  if (!this.top) return null;
  const value = this.top.value;
  this.top = this.top.next;
  return this.top.value;
}

medium

A. Returns the new top value instead of popped value

B. Does not check if stack is empty

C. Does not update top pointer

D. Throws error when stack is empty

Solution

1. Step 1: Analyze return value

   The method returns this.top.value after updating top, which is the new top, not the popped value.

2. Step 2: Correct return value

   It should return the saved value before updating top to return the popped element.

3. Final Answer:

   Returns the new top value instead of popped value -> Option A

4. Quick Check:

   Pop must return popped value, not new top [OK]

Hint: Return saved value before updating top [OK]

Common Mistakes:

• Returning top after update instead of popped value
• Not handling empty stack
• Forgetting to update top pointer

5. You want to implement a method peek() in your linked list stack that returns the top value without removing it. Which is the correct implementation?

hard

A. peek(): number | null { return this.top ? this.top.value : null; }

B. peek(): number | null { const val = this.top.value; this.top = this.top.next; return val; }

C. peek(): number | null { if (!this.top) return null; this.top = this.top.next; return this.top.value; }

D. peek(): number | null { return this.top.next ? this.top.next.value : null; }

Solution

1. Step 1: Understand peek operation

   Peek returns the top value without changing the stack.

2. Step 2: Check each option

   peek(): number | null { return this.top ? this.top.value : null; } returns top value if exists, else null, without modifying stack. Others modify top or return wrong node.

3. Final Answer:

   peek(): number | null { return this.top ? this.top.value : null; } -> Option A

4. Quick Check:

   Peek returns top value without removal = C [OK]

Hint: Peek returns top value without changing stack [OK]

Common Mistakes:

• Modifying top pointer in peek
• Returning next node's value
• Not handling empty stack