Pop Using Linked List Node in DSA Typescript - Cheat Sheet & Quick Revision

Recall & Review

beginner

What does the 'pop' operation do in a linked list?

It removes the last node from the linked list and returns its value, effectively shortening the list by one node.

intermediate

In a singly linked list, why do we need to traverse the list to pop the last node?

Because each node only knows about the next node, we must go through the list to find the second last node to update its next pointer to null.

intermediate

What is the time complexity of popping the last node in a singly linked list?

O(n), where n is the number of nodes, because we need to traverse the list to find the second last node.

beginner

What happens if you pop from an empty linked list?

Since there are no nodes, the operation returns null or undefined, indicating the list is empty and nothing can be popped.

beginner

Show the TypeScript signature of a pop method for a singly linked list node class.

pop(): T | null; // Removes and returns the last node's value or null if the list is empty.

What is the first step when popping the last node from a singly linked list?

A Traverse to the second last node

B Remove the head node

C Create a new node

D Reverse the list

To pop the last node, you must find the second last node to update its next pointer to null.

What value does pop return if the linked list is empty?

A The head node's value

B null or undefined

C 0

D An error

Popping from an empty list returns null or undefined because there is no node to remove.

What is the time complexity of pop operation in a singly linked list?

A O(n)

B O(log n)

C O(1)

D O(n^2)

Pop requires traversal to the second last node, so it takes O(n) time.

After popping the last node, what should the second last node's next pointer be set to?

A It should point to the head

B It should point to itself

C It should be null

D It should point to a new node

Setting next to null marks the new end of the list.

If the linked list has only one node, what does pop do?

A Duplicates the node

B Throws an error

C Does nothing

D Removes the node and sets head to null

Popping the only node removes it and the list becomes empty.

Explain step-by-step how to pop the last node from a singly linked list.

Think about how nodes link to each other and what changes when the last node is removed.

Describe the time complexity of popping the last node in a singly linked list and why it is that way.

Consider how linked lists store references only to next nodes.

Practice

1. What does the pop() operation do in a linked list when implemented using nodes?

easy

A. Removes the last node and returns its value

B. Adds a new node at the beginning

C. Removes the first node and returns its value

D. Searches for a node with a specific value

Solution

1. Step 1: Understand pop operation in linked list context

   Pop means removing the last element from the list, similar to popping from a stack.

2. Step 2: Identify what pop returns

   Pop removes the last node and returns its stored value.

3. Final Answer:

   Removes the last node and returns its value -> Option A

4. Quick Check:

   Pop = remove last node [OK]

Hint: Pop removes last node and returns its value [OK]

Common Mistakes:

• Confusing pop with push operation
• Thinking pop removes the first node
• Assuming pop searches for a value

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

easy

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

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

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

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

Solution

1. Step 1: Check property types for linked list node

   Node should have a value and a next pointer which can be null if no next node.

2. Step 2: Verify constructor initialization

   Constructor sets value and initializes next to null (no next node initially).

3. Final Answer:

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

4. Quick Check:

   Node next can be null [OK]

Hint: Next pointer must allow null for list end [OK]

Common Mistakes:

• Not allowing next to be null
• Using undefined instead of null
• Mismatching property names

3. Given the following linked list code, what will be the printed output after calling pop() once?

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

class LinkedList {
  head: Node | null = null;

  append(value: number) {
    const newNode = new Node(value);
    if (!this.head) {
      this.head = newNode;
      return;
    }
    let current = this.head;
    while (current.next) {
      current = current.next;
    }
    current.next = newNode;
  }

  pop() {
    if (!this.head) return null;
    if (!this.head.next) {
      const val = this.head.value;
      this.head = null;
      return val;
    }
    let current = this.head;
    while (current.next && current.next.next) {
      current = current.next;
    }
    const val = current.next!.value;
    current.next = null;
    return val;
  }

  print() {
    let current = this.head;
    let result = '';
    while (current) {
      result += current.value + ' -> ';
      current = current.next;
    }
    result += 'null';
    console.log(result);
  }
}

const list = new LinkedList();
list.append(10);
list.append(20);
list.append(30);
list.pop();
list.print();

medium

A. null

B. 10 -> 20 -> null

C. 20 -> 30 -> null

D. 10 -> 20 -> 30 -> null

Solution

1. Step 1: Understand list before pop

   List after appending 10, 20, 30 is: 10 -> 20 -> 30 -> null.

2. Step 2: Trace pop operation

   Pop removes last node (30), so list becomes 10 -> 20 -> null.

3. Final Answer:

   10 -> 20 -> null -> Option B

4. Quick Check:

   Pop removes last node [OK]

Hint: Pop removes last node, print shows remaining [OK]

Common Mistakes:

• Assuming pop removes first node
• Not updating next pointer to null
• Printing old list without pop effect

4. Identify the bug in the following pop() method for a singly linked list and select the correct fix.

pop() {
  if (!this.head) return null;
  let current = this.head;
  while (current.next) {
    current = current.next;
  }
  const val = current.value;
  current = null;
  return val;
}

medium

A. Return current.next.value instead of current.value

B. Initialize current as null before the loop

C. The loop should stop at the second last node; set current.next = null to remove last node

D. No bug; code works correctly

Solution

1. Step 1: Analyze loop behavior

   The loop moves current to the last node, but we need to stop at second last to remove last node.

2. Step 2: Fix removal of last node

   Set current.next = null at second last node to remove last node properly.

3. Final Answer:

   The loop should stop at the second last node; set current.next = null to remove last node -> Option C

4. Quick Check:

   Stop at second last node to remove last [OK]

Hint: Stop at second last node to remove last [OK]

Common Mistakes:

• Setting current = null does not remove node
• Loop goes to last node instead of second last
• Returning wrong node value

5. You have a singly linked list with nodes: 5 -> 15 -> 25 -> 35 -> null. You want to implement a pop() method that removes the last node and returns its value. However, if the list has only one node, pop() should remove it and set the list to empty. What will be the state of the list after calling pop() twice?
Choose the correct printed output after these operations:

const list = new LinkedList();
list.append(5);
list.append(15);
list.append(25);
list.append(35);
list.pop();
list.pop();
list.print();

hard

A. null

B. 5 -> 15 -> 25 -> null

C. 25 -> 35 -> null

D. 5 -> 15 -> null

Solution

1. Step 1: Initial list and first pop

   List starts as 5 -> 15 -> 25 -> 35 -> null. First pop removes 35, list becomes 5 -> 15 -> 25 -> null.

2. Step 2: Second pop removes last node 25

   After second pop, list is 5 -> 15 -> null.

3. Final Answer:

   5 -> 15 -> null -> Option D

4. Quick Check:

   Two pops remove last two nodes [OK]

Hint: Each pop removes last node, so two pops remove last two nodes [OK]

Common Mistakes:

• Removing nodes from front instead of end
• Not updating list head when one node left
• Assuming pop removes all nodes