Stack Implementation Using Linked List in DSA Typescript - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is a stack and how does it work?

A stack is a collection where elements are added and removed from the top only. It follows Last In, First Out (LIFO) order, like a stack of plates where you add or remove the top plate first.

beginner

What is a linked list in simple terms?

A linked list is a chain of nodes where each node holds data and a link (pointer) to the next node. It’s like a treasure hunt where each clue leads to the next one.

intermediate

Why use a linked list to implement a stack?

Using a linked list for a stack allows dynamic size changes without fixed limits. It easily adds or removes elements at the top without shifting others, unlike arrays.

beginner

What does the push operation do in a stack implemented with a linked list?

Push adds a new node at the start (top) of the linked list. The new node points to the old top, and then it becomes the new top.

beginner

What happens during the pop operation in a stack implemented with a linked list?

Pop removes the top node from the linked list. The top pointer moves to the next node, effectively removing the first node from the stack.

What order does a stack follow?

A Random order

B First In, First Out (FIFO)

C Sorted order

D Last In, First Out (LIFO)

A stack follows Last In, First Out (LIFO) order, meaning the last element added is the first to be removed.

In a linked list, what does each node contain?

A Data and a pointer to the next node

B Only data

C Only a pointer to the previous node

D Data and a pointer to the previous node

Each node in a linked list contains data and a pointer to the next node.

What does the push operation do in a stack using a linked list?

A Removes the top node

B Adds a new node at the bottom

C Adds a new node at the top

D Removes the bottom node

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

What happens when you pop from an empty stack?

A Return null or error

B Add a new node

C Return the bottom node

D Nothing happens

Popping from an empty stack returns null or an error because there is no element to remove.

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

A Easier to sort

B Dynamic size and no shifting needed

C Uses less memory always

D Faster access to middle elements

Linked lists allow dynamic size changes and easy addition/removal at the top without shifting elements.

Explain how push and pop operations work in a stack implemented using a linked list.

Think about how nodes connect and disconnect at the start of the list.

Describe the advantages of using a linked list to implement a stack compared to using an array.

Consider how arrays have fixed size and shifting costs.

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