Delete Node at End in DSA Typescript - Deep Dive

Overview - Delete Node at End

What is it?

Deleting a node at the end means removing the last element from a linked list. A linked list is a chain of nodes where each node points to the next one. Removing the last node changes the list so it ends one node earlier. This operation updates the list to no longer include the last node.

Why it matters

Without the ability to delete the last node, linked lists would grow endlessly or require rebuilding to remove elements. This would waste memory and slow down programs. Deleting the last node helps manage memory and keeps data structures efficient and up-to-date, which is important in many real-world applications like undo features or managing queues.

Where it fits

Before learning this, you should understand what a linked list is and how nodes connect. After this, you can learn about deleting nodes at other positions, inserting nodes, or more complex linked list types like doubly linked lists or circular lists.

Mental Model

Core Idea

Deleting the last node means finding the second-to-last node and making it the new end by removing its link to the last node.

Think of it like...

Imagine a chain of paper clips linked together. To remove the last paper clip, you hold the second-to-last clip and detach the last one, so the chain ends there.

Head -> Node1 -> Node2 -> Node3 -> null
To delete last node:
Head -> Node1 -> Node2 -> null
(Node3 removed)

Build-Up - 6 Steps

1

Foundation

Understanding Linked List Structure

Concept: Learn what a linked list is and how nodes connect.

A linked list is a sequence of nodes. Each node has data and a pointer to the next node. The last node points to null, meaning the end of the list. For example, a list with three nodes looks like: Head -> Node1 -> Node2 -> Node3 -> null.

Result

You can visualize and trace a linked list from head to end by following pointers.

Understanding the basic structure is essential because deleting nodes depends on changing these pointers correctly.

2

Foundation

What Does Deleting a Node Mean?

Concept: Deleting a node means removing it from the chain and updating links.

To delete a node, you must change the pointer of the previous node to skip the node being deleted and point to the next node instead. For the last node, the previous node's pointer should become null.

Result

The list no longer includes the deleted node, and the chain remains connected.

Knowing that deletion is about changing pointers helps avoid breaking the list or losing nodes.

3

Intermediate

Finding the Last Node in a List

🤔Before reading on: Do you think you can find the last node by checking each node's next pointer until it is null? Commit to yes or no.

Concept: To delete the last node, you first need to find it by traversing the list.

Start at the head node and move to the next node repeatedly until you find a node whose next pointer is null. This node is the last node. Also, keep track of the node before it (second-to-last) because you will need to update its pointer.

Result

You identify both the last node and the second-to-last node needed for deletion.

Understanding traversal is key because linked lists do not have direct access to the last node.

4

Intermediate

Deleting the Last Node Safely

🤔Before reading on: When deleting the last node, do you think you must set the second-to-last node's next pointer to null or to the head? Commit to your answer.

Concept: Deleting the last node means setting the second-to-last node's next pointer to null.

Once you find the second-to-last node, set its next pointer to null. This removes the last node from the list. If the list has only one node, deleting it means setting the head to null.

Result

The list ends one node earlier, and the last node is removed.

Knowing how to handle the edge case of a single-node list prevents errors and crashes.

5

Advanced

TypeScript Implementation of Delete at End

🤔Before reading on: Do you think the delete function should return the updated head or modify it in place? Commit to your answer.

Concept: Implement the delete at end operation in TypeScript with proper handling of edge cases.

class Node { data: number; next: Node | null; constructor(data: number) { this.data = data; this.next = null; } } function deleteAtEnd(head: Node | null): Node | null { if (!head) return null; // empty list if (!head.next) return null; // single node list let current = head; while (current.next && current.next.next) { current = current.next; } current.next = null; // remove last node return head; } // Example usage: // List: 1 -> 2 -> 3 -> null // After deleteAtEnd: 1 -> 2 -> null

Result

The function removes the last node and returns the updated list head.

Implementing the function clarifies how traversal and pointer updates work together in code.

6

Expert

Handling Edge Cases and Performance

🤔Before reading on: Is deleting the last node in a singly linked list always O(n) time? Commit to yes or no.

Concept: Understand the limitations and edge cases of deleting the last node in singly linked lists.

Deleting the last node requires traversal from head to second-to-last node, which takes O(n) time. For very long lists, this can be slow. Doubly linked lists can delete the last node in O(1) time because they have backward pointers. Also, deleting from an empty list or single-node list needs special handling to avoid errors.

Result

You know when this method is efficient and when other data structures might be better.

Knowing the time cost and edge cases helps choose the right data structure and avoid bugs.

Under the Hood

Internally, a singly linked list stores nodes in memory with each node holding data and a pointer to the next node's memory address. Deleting the last node means changing the second-to-last node's pointer from the last node's address to null, effectively removing the last node's reference. The removed node becomes unreachable and can be cleaned up by memory management.

Why designed this way?

Singly linked lists are simple and use minimal memory by storing only one pointer per node. This design makes insertion and deletion at the front fast but requires traversal for operations at the end. The tradeoff favors simplicity and memory efficiency over constant-time end operations.

Head
 │
 ▼
┌─────┐    ┌─────┐    ┌─────┐
│Node1│ -> │Node2│ -> │Node3│ -> null
└─────┘    └─────┘    └─────┘

To delete last node:
Find Node2 (second-to-last)
Set Node2.next = null
Node3 is removed

Myth Busters - 3 Common Misconceptions

Quick: Do you think you can delete the last node without traversing the list? Commit to yes or no.

Common Belief: You can delete the last node directly without checking other nodes.

Reality: In a singly linked list, you must traverse from the head to find the second-to-last node before deleting the last node.

Why it matters: Trying to delete without traversal leads to errors or memory leaks because you don't update the correct pointer.

Quick: Do you think deleting the last node in a single-node list leaves the head unchanged? Commit to yes or no.

Common Belief: Deleting the last node in a single-node list just removes the node but keeps the head pointing to null.

Reality: Deleting the only node means the head must be set to null, indicating the list is empty.

Why it matters: Failing to update the head causes the list to appear non-empty, leading to bugs.

Quick: Do you think deleting the last node is always a fast O(1) operation? Commit to yes or no.

Common Belief: Deleting the last node is always quick and constant time.

Reality: In singly linked lists, deleting the last node takes O(n) time because you must traverse the list to find the second-to-last node.

Why it matters: Assuming constant time can cause performance issues in large lists.

Expert Zone

1

In singly linked lists, maintaining a tail pointer can reduce deletion time at the end but requires careful updates on insertions and deletions.

2

Memory management after deletion depends on the language; in garbage-collected languages like TypeScript, unreferenced nodes are cleaned automatically.

3

Edge cases like empty lists or single-node lists must be explicitly handled to avoid null pointer errors.

When NOT to use

Deleting the last node in a singly linked list is inefficient for frequent end deletions. Use doubly linked lists or data structures like arrays or deques for faster end operations.

Production Patterns

In real systems, singly linked lists are often used for stacks or queues where deletion at the end is rare. For frequent end deletions, doubly linked lists or specialized data structures are preferred.

Connections

Doubly Linked List

Builds-on

Understanding singly linked list deletion helps grasp how doubly linked lists improve efficiency by adding backward pointers for O(1) end deletions.

Garbage Collection

Depends-on

Deleting nodes relies on garbage collection or manual memory management to free unused memory, linking data structure operations to system memory behavior.

Supply Chain Management

Analogy in process flow

Removing the last node is like removing the last item in a supply chain line, requiring knowledge of the previous step to safely remove the end without breaking the chain.

Common Pitfalls

#1 Not handling empty list before deletion.

Wrong approach:

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

Correct approach:

function deleteAtEnd(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;
}

Root cause:

Assuming the list always has at least two nodes causes errors when the list is empty or has one node.

#2 Setting the second-to-last node's next pointer incorrectly.

Wrong approach:

current.next = head; // wrong: points back to head instead of null

Correct approach:

current.next = null; // correct: ends the list properly

Root cause:

Confusing the pointer update leads to circular references or broken lists.

#3 Not updating head when deleting the only node.

Wrong approach:

if (!head.next) {
// do nothing
return head;
}

Correct approach:

if (!head.next) {
return null;
}

Root cause:

Failing to recognize that deleting the only node empties the list.

Key Takeaways

Deleting the last node in a singly linked list requires finding the second-to-last node and setting its next pointer to null.

Edge cases like empty lists and single-node lists must be handled carefully to avoid errors.

This operation takes O(n) time because traversal from the head is necessary.

Doubly linked lists can optimize this operation to O(1) by keeping backward pointers.

Understanding pointer updates is crucial to maintaining list integrity after deletion.

Practice

1. What does the operation Delete Node at End do in a singly linked list?

easy

A. Adds a new node at the beginning of the list

B. Removes the first node from the list

C. Removes the last node from the list

D. Adds a new node at the end of the list

Solution

1. Step 1: Understand the operation

   Deleting a node at the end means removing the last node in the linked list.

2. Step 2: Identify the effect on the list

   After removal, the second last node becomes the new last node.

3. Final Answer:

   Removes the last node from the list -> Option C

4. Quick Check:

   Delete Node at End = Remove last node [OK]

Hint: Delete last node means remove tail node [OK]

Common Mistakes:

• Confusing delete at end with delete at start
• Thinking it adds a node instead of removing
• Assuming it deletes a middle node

2. Which of the following TypeScript code snippets correctly deletes the last node of a singly linked list named head?

easy

A. if (!head) return null;
head = head.next;

B. if (!head) return null;
let temp = head;
while (temp.next && temp.next.next) {
temp = temp.next;
}
temp.next = null;

C. let temp = head;
while (temp.next) {
temp = temp.next;
}
temp = null;

D. head = null;

Solution

1. Step 1: Analyze code for deleting last node

   if (!head) return null; let temp = head; while (temp.next && temp.next.next) { temp = temp.next; } temp.next = null; traverses to the second last node and sets its next to null, removing the last node.

2. Step 2: Check other options

   if (!head) return null; head = head.next; deletes the first node, C tries to set temp to null but does not affect list, D deletes entire list.

3. Final Answer:

   Traverse to second last node, set next to null -> Option B

4. Quick Check:

   Traverse to second last node, set next to null = A [OK]

Hint: Stop at second last node, set next to null [OK]

Common Mistakes:

• Setting temp to null does not remove node from list
• Deleting head instead of last node
• Not checking for empty or single-node list

3. Given the linked list: 1 -> 2 -> 3 -> 4 -> null, what will be the list after deleting the node at the end using this code?

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

medium

A. 2 -> 3 -> 4 -> null

B. 1 -> 2 -> 3 -> 4 -> null

C. null

D. 1 -> 2 -> 3 -> null

Solution

1. Step 1: Understand the code logic

   The code removes the last node by stopping at second last node and setting its next to null.

2. Step 2: Apply to given list

   Original list ends with 4. After deletion, 3's next becomes null, so list is 1 -> 2 -> 3 -> null.

3. Final Answer:

   1 -> 2 -> 3 -> null -> Option D

4. Quick Check:

   Last node removed, list ends at 3 [OK]

Hint: Last node removed, second last points to null [OK]

Common Mistakes:

• Not updating second last node's next to null
• Returning null for multi-node list
• Deleting first node instead of last

4. Identify the bug in this TypeScript function that deletes the last node of a singly linked list:

function deleteAtEnd(head: Node | null): Node | null {
  if (!head) return null;
  let temp = head;
  while (temp.next) {
    temp = temp.next;
  }
  temp = null;
  return head;
}

medium

A. It does not update the second last node's next pointer

B. It does not handle empty list

C. It deletes the head node instead of last

D. It causes infinite loop

Solution

1. Step 1: Analyze the loop

   The loop moves temp to the last node, but does not track second last node.

2. Step 2: Check deletion step

   Setting temp = null only changes local variable, does not remove last node from list.

3. Final Answer:

   It does not update the second last node's next pointer -> Option A

4. Quick Check:

   Must update second last node's next to null [OK]

Hint: Update second last node's next to null, not temp variable [OK]

Common Mistakes:

• Setting temp to null does not remove node
• Not tracking second last node in loop
• Ignoring single-node list case

5. You have a singly linked list with nodes: 10 -> 20 -> 30 -> 40 -> null. Write a TypeScript function to delete the last node and return the updated list. Which of the following implementations correctly handles the edge case when the list has only one node?

hard

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

B. function deleteAtEnd(head: Node | null): Node | null {
if (!head) return null;
let temp = head;
while (temp.next) {
temp = temp.next;
}
temp = null;
return head;
}

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

D. function deleteAtEnd(head: Node | null): Node | null {
if (!head) return null;
if (!head.next) return head;
let temp = head;
while (temp.next) {
temp = temp.next;
}
temp.next = null;
return head;
}

Solution

1. Step 1: Check handling of single-node list

   function deleteAtEnd(head: Node | null): Node | null { if (!head) return null; if (!head.next) return null; let temp = head; while (temp.next && temp.next.next) { temp = temp.next; } temp.next = null; return head; } returns null if only one node exists, correctly deleting it.

2. Step 2: Verify deletion of last node for longer lists

   For longer lists, it traverses to the second last node using while (temp.next && temp.next.next) and sets temp.next = null, correctly removing the last node.

3. Final Answer:

   Correctly handles single-node by returning null -> Option A

4. Quick Check:

   Return null for single node, else remove last node [OK]

Hint: Return null if single node, else remove last node [OK]

Common Mistakes:

• Not returning null for single-node list
• Setting temp to null instead of updating next pointer
• Incorrect loop condition causing errors