Pop Using Linked List Node in DSA Typescript - Time & Space Complexity

Time Complexity: Pop Using Linked List Node

O(n)

Understanding Time Complexity

We want to understand how long it takes to remove the last item from a linked list.

How does the time needed change as the list grows?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

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

function pop(head: Node | null): Node | null {
  if (!head) return null;
  if (!head.next) return null;
  let current = head;
  while (current.next && current.next.next) {
    current = current.next;
  }
  current.next = null;
  return head;
}
    

This code removes the last node from a singly linked list by walking through nodes until the second last one.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: The while loop that moves through nodes one by one.
• How many times: It runs once for each node until the second last node, so about n-2 times for n nodes.

How Execution Grows With Input

As the list gets longer, the loop runs more times, roughly one less than the number of nodes.

Input Size (n)	Approx. Operations
10	About 8 steps
100	About 98 steps
1000	About 998 steps

Pattern observation: The number of steps grows roughly in a straight line with the number of nodes.

Final Time Complexity

Time Complexity: O(n)

This means the time to remove the last node grows directly with the list size.

Common Mistake

[X] Wrong: "Removing the last node is always quick and takes constant time."

[OK] Correct: Because we must walk through the list to find the second last node, the time depends on list length.

Interview Connect

Knowing how linked list operations scale helps you explain trade-offs clearly and shows you understand data structure behavior.

Self-Check

"What if the linked list kept a pointer to the last node? How would the time complexity of pop change?"

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