Delete Node at Specific Position in DSA Typescript - Deep Dive

Overview - Delete Node at Specific Position

What is it?

Deleting a node at a specific position means removing an element from a linked list at the exact place you choose. A linked list is a chain of connected nodes, each holding data and a link to the next node. This operation changes the list by cutting out one node and linking its neighbors directly. It helps keep the list updated by removing unwanted or outdated data.

Why it matters

Without the ability to delete nodes at specific positions, linked lists would grow uncontrollably or require rebuilding from scratch to remove elements. This would make managing data inefficient and slow, especially when dealing with large or changing datasets. Being able to delete nodes precisely keeps data structures flexible and memory usage optimal, which is crucial in many real-world applications like databases, navigation systems, and real-time data processing.

Where it fits

Before learning this, you should understand what linked lists are and how to traverse them. After mastering deletion at specific positions, you can explore more complex linked list operations like reversing, sorting, or working with doubly linked lists and circular linked lists.

Mental Model

Core Idea

Deleting a node at a specific position means skipping over that node by linking its previous node directly to its next node, effectively removing it from the chain.

Think of it like...

Imagine a paper chain where each paper ring is linked to the next. To remove one ring in the middle, you open the ring before it and connect it directly to the ring after it, removing the middle ring without breaking the whole chain.

Linked List:
Head -> [Node1] -> [Node2] -> [Node3] -> [Node4] -> null

Delete Node at position 3:
Step 1: Find Node2 (previous node)
Step 2: Change Node2's next to Node4
Result:
Head -> [Node1] -> [Node2] -> [Node4] -> null

Build-Up - 7 Steps

1

Foundation

Understanding Linked List Structure

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

A linked list is made of nodes. Each node has two parts: data and a pointer to the next node. The first node is called the head. The last node points to null, meaning the list ends there. You can move through the list by following these pointers from one node to the next.

Result

You can visualize a linked list as a chain of connected nodes ending with null.

Understanding the basic structure of linked lists is essential because deletion depends on changing these connections carefully.

2

Foundation

Traversing to a Specific Position

Concept: Learn how to move through the list to reach the node before the one to delete.

To delete a node at position n, you must first reach the node at position n-1. Starting from the head, move one node at a time, counting positions until you reach n-1. This node is important because its pointer will be changed to skip the node at position n.

Result

You can find the node just before the one you want to delete.

Knowing how to reach the correct node is key to safely removing a node without breaking the list.

3

Intermediate

Deleting the Head Node

🤔Before reading on: Do you think deleting the first node requires changing the previous node's pointer or something else? Commit to your answer.

Concept: Deleting the first node (head) is a special case because there is no previous node.

To delete the head node, simply move the head pointer to the second node. The original first node is no longer linked and can be removed. This changes the start of the list.

Result

The head now points to the second node, effectively removing the first node.

Handling the head node separately prevents errors and keeps the list valid after deletion.

4

Intermediate

Deleting a Node in the Middle

🤔Before reading on: When deleting a middle node, do you think you need to move the previous node's pointer to the next node or to the node after next? Commit to your answer.

Concept: To delete a node in the middle, link its previous node directly to its next node, skipping the node to delete.

Find the node before the one to delete. Change its next pointer to point to the node after the one to delete. This removes the target node from the chain. The deleted node is then disconnected and can be cleaned up.

Result

The list skips the deleted node, maintaining continuity.

Changing the previous node's pointer is the core action that removes a node without breaking the list.

5

Intermediate

Deleting the Last Node

🤔Before reading on: Do you think deleting the last node requires special handling compared to middle nodes? Commit to your answer.

Concept: Deleting the last node means the previous node's next pointer should point to null.

Traverse to the node before the last node. Set its next pointer to null. This removes the last node from the list, marking the new end.

Result

The list ends one node earlier, with the last node removed.

Recognizing the end of the list is important to avoid dangling pointers after deletion.

6

Advanced

Handling Invalid Positions Gracefully

🤔Before reading on: Should the deletion function crash or handle invalid positions smoothly? Commit to your answer.

Concept: Deletion functions should check if the position is valid and handle errors without crashing.

Before deleting, check if the position is less than 1 or greater than the list length. If invalid, do nothing or return an error. This prevents runtime errors and keeps the list safe.

Result

The list remains unchanged if the position is invalid.

Validating input protects the program from unexpected crashes and data corruption.

7

Expert

Optimizing Deletion with Sentinel Nodes

🤔Before reading on: Do you think using a dummy head node simplifies deletion logic? Commit to your answer.

Concept: Using a sentinel (dummy) node before the head simplifies edge cases like deleting the head node.

Create a dummy node pointing to the head. Always delete nodes by changing the next pointer of the previous node, which now always exists. After deletion, update the head from dummy's next. This removes special cases and makes code cleaner.

Result

Deletion code becomes uniform and less error-prone.

Sentinel nodes reduce complexity and bugs by unifying deletion logic for all positions.

Under the Hood

Internally, a linked list node stores a reference (pointer) to the next node's memory address. Deleting a node means changing the previous node's pointer to skip the deleted node's address and point to the next node's address instead. The removed node's memory can then be freed or garbage collected. This pointer manipulation keeps the list connected without copying or moving data.

Why designed this way?

Linked lists were designed to allow efficient insertions and deletions without shifting elements, unlike arrays. Using pointers to link nodes enables dynamic memory use and flexible list size. The pointer-based structure requires careful updates during deletion to maintain list integrity.

Linked List Node Structure:
┌───────────┐    ┌───────────┐    ┌───────────┐
│ Data      │ -> │ Data      │ -> │ Data      │ -> null
│ Next Ptr  │    │ Next Ptr  │    │ Next Ptr  │
└───────────┘    └───────────┘    └───────────┘

Deletion Process:
Previous Node's Next Ptr
      │
      ▼
┌───────────┐    ┌───────────┐    ┌───────────┐
│ Data      │ -> │ Data      │ -> │ Data      │
│ Next Ptr  │    │ Next Ptr  │    │ Next Ptr  │
└───────────┘    └───────────┘    └───────────┘

Change Previous Node's Next Ptr to skip deleted node:

┌───────────┐    ┌───────────┐
│ Data      │ -> │ Data      │
│ Next Ptr  │    │ Next Ptr  │
└───────────┘    └───────────┘

Myth Busters - 4 Common Misconceptions

Quick: Does deleting a node always require moving all nodes after it? Commit to yes or no.

Common Belief: Deleting a node means shifting all nodes after it one position forward.

Reality: In linked lists, nodes are connected by pointers, so deleting a node only requires changing one pointer, not moving any nodes.

Why it matters: Believing nodes must be moved leads to inefficient code and misunderstanding of linked list advantages.

Quick: Can you delete a node without knowing the previous node? Commit to yes or no.

Common Belief: You can delete any node directly without needing to find its previous node.

Reality: To delete a node in a singly linked list, you must know the previous node to update its pointer; otherwise, you cannot unlink the target node.

Why it matters: Ignoring this causes bugs where the list becomes broken or memory leaks occur.

Quick: Is deleting the head node the same as deleting any other node? Commit to yes or no.

Common Belief: Deleting the head node is the same as deleting any other node in the list.

Reality: Deleting the head node is special because there is no previous node; you must update the head pointer itself.

Why it matters: Treating the head node like others causes errors and crashes in list operations.

Quick: Does deleting a node automatically free its memory in all languages? Commit to yes or no.

Common Belief: Deleting a node always frees its memory immediately.

Reality: In some languages, like those with garbage collection, memory is freed later; in others, manual freeing is required.

Why it matters: Assuming automatic memory freeing can cause memory leaks or crashes in manual memory management environments.

Expert Zone

1

Using sentinel nodes simplifies deletion logic by removing special cases for head deletion.

2

In concurrent environments, deleting nodes requires synchronization to avoid race conditions and corrupted lists.

3

Memory management strategies differ: manual free in low-level languages vs. garbage collection in high-level languages affects deletion implementation.

When NOT to use

Deleting nodes at specific positions is inefficient for very large lists if done repeatedly because traversal is O(n). Alternatives like balanced trees or indexed data structures are better for frequent random deletions.

Production Patterns

In production, deletion is often combined with validation and logging. Sentinel nodes or dummy heads are used to simplify code. In real-time systems, lock-free or concurrent linked lists use atomic operations for safe deletion.

Connections

Array Deletion

Contrast

Unlike linked lists, arrays require shifting elements after deletion, making linked lists more efficient for frequent deletions.

Garbage Collection

Dependency

Understanding how memory is freed after deletion depends on knowing if the language uses garbage collection or manual memory management.

Supply Chain Management

Process similarity

Removing a node from a linked list is like removing a supplier from a supply chain and rerouting connections to maintain flow without disruption.

Common Pitfalls

#1 Trying to delete a node without checking if the position exists.

Wrong approach:

function deleteNode(head: Node | null, position: number): Node | null {
let current = head;
let prev = null;
let count = 1;
while (count < position) {
prev = current;
current = current!.next;
count++;
}
prev!.next = current!.next;
return head;
}

Correct approach:

function deleteNode(head: Node | null, position: number): Node | null {
if (!head || position < 1) return head;
if (position === 1) return head.next;
let current = head;
let prev = null;
let count = 1;
while (current && count < position) {
prev = current;
current = current.next;
count++;
}
if (!current) return head; // position out of range
prev!.next = current.next;
return head;
}

Root cause:

Not validating position or list length leads to null pointer errors or crashes.

#2 Deleting the head node by changing the previous node's next pointer.

Wrong approach:

function deleteNode(head: Node | null, position: number): Node | null {
if (position === 1) {
// Incorrect: trying to access previous node
let prev = null;
prev.next = head.next; // Error: prev is null
return head;
}
// ... rest of code
}

Correct approach:

function deleteNode(head: Node | null, position: number): Node | null {
if (position === 1) {
return head ? head.next : null;
}
// ... rest of code
}

Root cause:

Misunderstanding that head has no previous node causes null reference errors.

#3 Not updating the head pointer after deleting the first node.

Wrong approach:

function deleteNode(head: Node | null, position: number): Node | null {
if (position === 1) {
// Deletes node but does not update head
let temp = head;
temp = temp.next;
return head; // head unchanged
}
// ... rest of code
}

Correct approach:

function deleteNode(head: Node | null, position: number): Node | null {
if (position === 1) {
return head ? head.next : null;
}
// ... rest of code
}

Root cause:

Failing to reassign head pointer means list still points to deleted node.

Key Takeaways

Deleting a node at a specific position in a linked list means changing pointers to skip that node, keeping the list connected.

Special care is needed when deleting the head node because it has no previous node; the head pointer must be updated.

Validating the position before deletion prevents errors and keeps the list safe.

Using sentinel nodes can simplify deletion logic by removing special cases.

Understanding pointer manipulation and memory management is key to mastering linked list deletions.

Practice

1. What does deleting a node at a specific position in a singly linked list mean?

easy

A. Removing the node located at that position and linking its previous node to the next node

B. Adding a new node at that position

C. Swapping the node at that position with the last node

D. Counting the total nodes in the list

Solution

1. Step 1: Understand node deletion in linked list

   Deleting a node means removing it and connecting the previous node to the next node to keep the list intact.

2. Step 2: Apply to specific position

   At a specific position, we find the node before it and change its next pointer to skip the node to delete.

3. Final Answer:

   Removing the node located at that position and linking its previous node to the next node -> Option A

4. Quick Check:

   Delete node = remove and link neighbors [OK]

Hint: Delete means remove and link neighbors, not add or swap [OK]

Common Mistakes:

• Thinking deletion adds a node
• Confusing deletion with swapping nodes
• Ignoring the need to link previous and next nodes

2. Which of the following TypeScript code snippets correctly deletes a node at position pos in a singly linked list starting with head?

easy

A. if (pos === 0) head = head.next; else { let temp = head; for (let i = 0; i < pos - 1; i++) temp = temp.next; temp.next = temp.next.next; }

B. if (pos === 0) head = head.next; else { let temp = head; for (let i = 0; i < pos; i++) temp = temp.next; temp.next = temp.next.next; }

C. if (pos === 0) head = head.next; else { let temp = head; for (let i = 0; i <= pos; i++) temp = temp.next; temp.next = temp.next.next; }

D. if (pos === 0) head = head.next; else { let temp = head; for (let i = 1; i <= pos; i++) temp = temp.next; temp.next = temp.next.next; }

Solution

1. Step 1: Handle deletion at head (position 0)

   If position is 0, simply move head to next node to delete the first node.

2. Step 2: Traverse to node before position

   Loop from 0 to pos-1 to reach node before the one to delete, then link its next to next.next.

3. Final Answer:

   if (pos === 0) head = head.next; else { let temp = head; for (let i = 0; i < pos - 1; i++) temp = temp.next; temp.next = temp.next.next; } -> Option A

4. Quick Check:

   Loop to pos-1, then skip node [OK]

Hint: Loop to pos-1 to delete node at pos [OK]

Common Mistakes:

• Looping to pos instead of pos-1
• Not handling deletion at head correctly
• Accessing temp.next.next when temp.next is null

3. Given the linked list: 10 -> 20 -> 30 -> 40 -> 50 -> null and the code below, what will be the list after deleting the node at position 2?

let head = { val: 10, next: { val: 20, next: { val: 30, next: { val: 40, next: { val: 50, next: null } } } } };
let pos = 2;
if (pos === 0) head = head.next;
else {
  let temp = head;
  for (let i = 0; i < pos - 1; i++) temp = temp.next;
  temp.next = temp.next.next;
}

medium

A. 10 -> 30 -> 40 -> 50 -> null

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

C. 10 -> 20 -> 40 -> 50 -> null

D. 20 -> 30 -> 40 -> 50 -> null

Solution

1. Step 1: Identify node at position 2

   Position 2 node has value 30 (0-based indexing: 10 at 0, 20 at 1, 30 at 2).

2. Step 2: Delete node at position 2

   Traverse to node at position 1 (value 20), then set its next to node at position 3 (value 40), skipping 30.

3. Final Answer:

   10 -> 20 -> 40 -> 50 -> null -> Option C

4. Quick Check:

   Node 30 removed, neighbors linked [OK]

Hint: Skip node at pos by linking previous to next.next [OK]

Common Mistakes:

• Deleting wrong node due to off-by-one error
• Not updating links properly
• Confusing position indexing

4. The following TypeScript code attempts to delete a node at position pos in a singly linked list but causes a runtime error. What is the error?

function deleteNode(head: Node | null, pos: number): Node | null {
  if (pos === 0) return head.next;
  let temp = head;
  for (let i = 0; i < pos; i++) {
    temp = temp.next!;
  }
  temp.next = temp.next!.next;
  return head;
}

medium

A. Incorrect loop range causes skipping the wrong node

B. Accessing temp.next when temp is null causes runtime error

C. Missing check for empty list before deletion

D. Returning head.next instead of head after deletion

Solution

1. Step 1: Analyze loop traversal

   The loop runs from 0 to pos, moving temp forward pos times, which can make temp null if pos >= list length.

2. Step 2: Identify null access

   After loop, temp may be null, so accessing temp.next causes runtime error.

3. Final Answer:

   Accessing temp.next when temp is null causes runtime error -> Option B

4. Quick Check:

   Loop overshoots, temp becomes null, then temp.next fails [OK]

Hint: Loop to pos-1, not pos, to avoid null access [OK]

Common Mistakes:

• Looping too far causing null pointer
• Not checking for empty list
• Misunderstanding return value after deletion

5. You have a singly linked list representing a playlist: Song1 -> Song2 -> Song3 -> Song4 -> Song5 -> null. You want to delete the 4th song (position 3). After deletion, you want to insert a new song Song6 at the same position. Which sequence of operations correctly achieves this?

hard

A. Delete node at position 3, then insert new node at head

B. Delete node at position 3, then traverse to position 3 and insert new node after it

C. Delete node at position 2, then traverse to position 3 and insert new node after it

D. Delete node at position 3, then traverse to position 2 and insert new node after it

Solution

1. Step 1: Delete node at position 3

   Remove the node at position 3 (Song4) by linking node at position 2 to node at position 4.

2. Step 2: Insert new node at position 3

   Traverse to position 2, then insert new node after it to place Song6 at position 3.

3. Final Answer:

   Delete node at position 3, then traverse to position 2 and insert new node after it -> Option D

4. Quick Check:

   Delete at pos 3, insert after pos 2 = new pos 3 [OK]

Hint: Insert after pos-1 to place new node at pos [OK]

Common Mistakes:

• Inserting at wrong position after deletion
• Deleting wrong node position
• Inserting at head instead of correct position