Delete Node at Specific Position in DSA Go - 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 place you choose. A linked list is a chain of nodes where each node points to the next one. When you delete a node, you change the links so the chain stays connected without the removed node. This operation helps manage data by removing unwanted or outdated items.

Why it matters

Without the ability to delete nodes at specific positions, linked lists would grow endlessly or require rebuilding from scratch to remove items. This would waste memory and slow down programs. Being able to delete nodes efficiently keeps data structures clean and responsive, which is important in many real-world applications like managing playlists, undo features, or task lists.

Where it fits

Before learning this, you should understand what linked lists are and how to traverse them. After this, you can learn about more complex linked list operations like reversing, sorting, or deleting nodes by value. This topic is a stepping stone to mastering dynamic data structures.

Mental Model

Core Idea

Deleting a node at a specific position means changing the link from the previous node to skip the target 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 link it directly to the ring after, so the chain stays whole without the removed ring.

Head -> [Node1] -> [Node2] -> [Node3] -> [Node4] -> null
To delete Node3:
Head -> [Node1] -> [Node2] --------> [Node4] -> null
(Node2's next now points to Node4, skipping Node3)

Build-Up - 7 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 holds data and a pointer to the next node. The first node is called the head. The last node points to null, meaning the end of the list.

Result

You can visualize a chain of nodes connected by pointers, starting from the head and ending at null.

Understanding the basic structure of linked lists is essential because all operations, including deletion, depend on navigating and updating these connections.

2

Foundation

Traversing to a Specific Position

Concept: Learn how to move through the list to reach a node at a given position.

To find a node at position n, start at the head and move to the next node repeatedly until you reach position n. Positions start at 1 for the head node.

Result

You can reach any node by counting steps from the head.

Knowing how to traverse the list by position is crucial because deletion requires locating the node before the one to remove.

3

Intermediate

Deleting the Head Node

🤔Before reading on: do you think deleting the head node requires special handling or is it the same as deleting any other node? Commit to your answer.

Concept: Deleting the first node (head) is a special case because it changes the starting point of the list.

To delete the head node, move the head pointer to the second node. The original head node is then removed from memory.

Result

The list starts from the second node, effectively removing the first node.

Recognizing the head node as a special case prevents errors like losing access to the entire list.

4

Intermediate

Deleting a Node in the Middle or End

🤔Before reading on: do you think you need to change the node to delete or the node before it to remove a middle node? Commit to your answer.

Concept: To delete a node that is not the head, update the previous node's pointer to skip the target node.

Find the node before the one to delete. Change its next pointer to point to the node after the target node. This removes the target node from the chain.

Result

The list remains connected without the deleted node.

Understanding that you update the previous node's pointer, not the target node itself, is key to correctly deleting nodes.

5

Intermediate

Handling Invalid Positions

🤔Before reading on: what should happen if you try to delete a node at a position beyond the list length? Commit to your answer.

Concept: You must check if the position is valid before deleting to avoid errors.

If the position is less than 1 or greater than the number of nodes, do nothing or return an error. This prevents crashes or undefined behavior.

Result

The list stays unchanged if the position is invalid.

Validating input positions protects your program from unexpected failures.

6

Advanced

Go Implementation with Memory Safety

🤔Before reading on: do you think Go's garbage collector handles deleted nodes automatically or do you need to free memory manually? Commit to your answer.

Concept: Implement deletion in Go, relying on garbage collection to clean up removed nodes.

In Go, you update pointers to remove nodes. The garbage collector frees memory of unreferenced nodes automatically, so no manual free is needed.

Result

Deleted nodes are removed from the list and memory is reclaimed safely.

Knowing Go's memory model simplifies deletion code and avoids manual memory management errors.

7

Expert

Edge Cases and Performance Considerations

🤔Before reading on: do you think deleting nodes frequently at random positions in a singly linked list is efficient? Commit to your answer.

Concept: Deleting nodes at arbitrary positions requires traversal, which can be slow for large lists. Special cases and optimizations exist.

Repeated deletions at random positions cause O(n) traversal each time. Using doubly linked lists or auxiliary data structures can improve performance. Also, careful handling of edge cases like empty lists or single-node lists is needed.

Result

Understanding these limits helps design better data structures for specific needs.

Recognizing performance trade-offs guides you to choose the right data structure for your problem.

Under the Hood

Deleting a node involves changing the pointer of the previous node to point to the node after the one being deleted. The removed node becomes unreachable and is cleaned up by Go's garbage collector. The list remains a continuous chain without gaps.

Why designed this way?

Linked lists use pointers to connect nodes because this allows dynamic memory use and easy insertion or deletion without shifting elements. Deletion by pointer adjustment is simple and efficient compared to arrays, which require shifting elements.

Head -> [Node1] -> [Node2] -> [Node3] -> [Node4] -> null
To delete Node3:
Head -> [Node1] -> [Node2] --------> [Node4] -> null
(Node2's next pointer updated to Node4)

Myth Busters - 4 Common Misconceptions

Quick: Do you think deleting a node at position 1 is the same as deleting any other node? Commit to yes or no.

Common Belief: Deleting any node is the same process regardless of position.

Reality: Deleting the head node requires updating the head pointer itself, which is different from deleting other nodes.

Why it matters: Treating the head node like others can cause loss of the entire list or dangling pointers.

Quick: Do you think you can delete a node without accessing the previous node? Commit to yes or no.

Common Belief: You can delete a node by just changing its own pointer.

Reality: In singly linked lists, you must access the previous node to update its pointer to skip the deleted node.

Why it matters: Trying to delete without the previous node leads to broken links and corrupted lists.

Quick: Do you think deleting a node automatically frees memory in all languages? Commit to yes or no.

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

Reality: In Go, garbage collection frees memory automatically, but in some languages like C, you must free memory manually.

Why it matters: Assuming automatic memory freeing can cause memory leaks or crashes in languages without garbage collection.

Quick: Do you think deleting a node at an invalid position changes the list? Commit to yes or no.

Common Belief: Trying to delete at an invalid position will remove the closest valid node.

Reality: Invalid positions should be checked and ignored to keep the list unchanged.

Why it matters: Ignoring validation can cause unexpected data loss or runtime errors.

Expert Zone

1

Deleting nodes in a singly linked list requires careful pointer updates to avoid losing access to the rest of the list.

2

Go's garbage collector simplifies memory management but understanding when nodes become unreachable helps avoid subtle bugs.

3

Repeated deletions at random positions in large lists are inefficient; alternative data structures or indexing can improve performance.

When NOT to use

Deleting nodes at arbitrary positions in singly linked lists is inefficient for large datasets due to O(n) traversal. Use doubly linked lists or balanced trees for faster deletions. For fixed-size collections, arrays or slices may be better.

Production Patterns

In real systems, deletion often combines with search or update operations. Using sentinel nodes or dummy heads simplifies edge cases. Batch deletions or lazy deletions (marking nodes deleted without immediate removal) improve performance in high-load scenarios.

Connections

Doubly Linked List

Builds-on

Understanding deletion in singly linked lists helps grasp the added flexibility and complexity of doubly linked lists, where nodes have pointers both ways.

Garbage Collection

Depends-on

Knowing how Go's garbage collector works clarifies why manual memory freeing is unnecessary when deleting nodes, preventing memory leaks.

Supply Chain Management

Analogy

Deleting a node is like removing a step in a supply chain process; understanding how removing one step affects the flow helps manage dependencies and continuity.

Common Pitfalls

#1 Losing the entire list by deleting the head incorrectly.

Wrong approach:

func deleteAtPosition(head *Node, pos int) *Node {
if pos == 1 {
head = nil // wrong: loses rest of list
return head
}
// ... rest of code
}

Correct approach:

func deleteAtPosition(head *Node, pos int) *Node {
if pos == 1 {
return head.next // correct: move head to next node
}
// ... rest of code
}

Root cause:

Misunderstanding that head must point to the next node, not nil, to keep the list.

#2 Not checking for invalid positions causing runtime errors.

Wrong approach:

func deleteAtPosition(head *Node, pos int) *Node {
current := head
for i := 1; i < pos-1; i++ {
current = current.next
}
current.next = current.next.next
return head
}

Correct approach:

func deleteAtPosition(head *Node, pos int) *Node {
if pos < 1 || head == nil {
return head
}
if pos == 1 {
return head.next
}
current := head
for i := 1; i < pos-1 && current.next != nil; i++ {
current = current.next
}
if current.next == nil {
return head
}
current.next = current.next.next
return head
}

Root cause:

Failing to validate position and list length before deletion.

#3 Trying to delete a node without accessing the previous node.

Wrong approach:

func deleteAtPosition(head *Node, pos int) *Node {
current := head
for i := 1; i < pos; i++ {
current = current.next
}
current = current.next // wrong: does not update previous node's pointer
return head
}

Correct approach:

func deleteAtPosition(head *Node, pos int) *Node {
if pos == 1 {
return head.next
}
current := head
for i := 1; i < pos-1 && current.next != nil; i++ {
current = current.next
}
if current.next == nil {
return head
}
current.next = current.next.next
return head
}

Root cause:

Not realizing deletion requires changing the previous node's next pointer.

Key Takeaways

Deleting a node at a specific position in a linked list means changing the previous node's pointer to skip the target node.

The head node is a special case because deleting it changes the starting point of the list.

Always validate the position before deleting to avoid errors or data loss.

In Go, garbage collection automatically frees memory of deleted nodes, simplifying management.

Repeated deletions at random positions in singly linked lists can be inefficient; choose data structures wisely.

Practice

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

easy

A. Adding a new node at that position

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

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

D. Counting the number of nodes before that position

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: Identify what happens at the specific position

   The node at the given position is removed, and the previous node's next pointer is updated to skip the deleted node.

3. Final Answer:

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

4. Quick Check:

   Delete node = remove and link neighbors [OK]

Hint: Delete means remove node and link neighbors [OK]

Common Mistakes:

• Thinking deletion adds a node
• Swapping nodes instead of deleting
• Only counting nodes without deletion

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

easy

A. curr := head; for i := 0; i <= pos; i++ { curr = curr.next }; curr.next = curr.next.next

B. head = head.next; for i := 0; i < pos; i++ { head = head.next }

C. if pos == 0 { head = head.next } else { curr := head; for i := 0; i < pos-1; i++ { curr = curr.next }; curr.next = curr.next.next }

D. for i := 0; i < pos; i++ { head = head.next }; head = head.next.next

Solution

1. Step 1: Check deletion at position 0

   If position is 0, we update head to head.next to remove the first node.

2. Step 2: Traverse to node before position and update links

   For other positions, we move to node before the target and set its next to skip the deleted node.

3. Final Answer:

   if pos == 0 { head = head.next } else { curr := head; for i := 0; i < pos-1; i++ { curr = curr.next }; curr.next = curr.next.next } -> Option C

4. Quick Check:

   Correct traversal and link update = if pos == 0 { head = head.next } else { curr := head; for i := 0; i < pos-1; i++ { curr = curr.next }; curr.next = curr.next.next } [OK]

Hint: Update previous node's next to skip deleted node [OK]

Common Mistakes:

• Not handling position 0 separately
• Looping one extra time causing nil pointer
• Incorrectly updating head inside loop

3. What is the output linked list after deleting the node at position 2 from the list: 10 -> 20 -> 30 -> 40 -> 50 -> null?

type Node struct {
  data int
  next *Node
}

// Assume head points to 10
// Delete node at position 2
func deleteAtPosition(head *Node, pos int) *Node {
  if pos == 0 {
    return head.next
  }
  curr := head
  for i := 0; i < pos-1; i++ {
    curr = curr.next
  }
  curr.next = curr.next.next
  return head
}

medium

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

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

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

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

Solution

1. Step 1: Identify node at position 2

   Position 2 node is the third node with value 30.

2. Step 2: Update links to remove node 30

   Node at position 1 (20) next pointer is updated to node at position 3 (40), skipping 30.

3. Final Answer:

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

4. Quick Check:

   Deleted 30 at pos 2 = 10->20->40->50 [OK]

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

Common Mistakes:

• Deleting wrong node index
• Not updating links correctly
• Returning wrong head pointer

4. The following Go code tries to delete a node at position pos but causes a runtime error. What is the error and how to fix it?

func deleteAtPosition(head *Node, pos int) *Node {
  curr := head
  for i := 0; i < pos; i++ {
    curr = curr.next
  }
  curr.next = curr.next.next
  return head
}

medium

A. Logic error because loop goes to pos instead of pos-1; fix loop to i < pos-1

B. Syntax error due to missing return statement; fix by adding return head

C. No error; code works fine

D. Runtime error due to nil pointer when pos is 0; fix by handling pos 0 separately

Solution

1. Step 1: Analyze loop traversal

   The loop moves curr to the node at position pos, but we need the node before pos to update links.

2. Step 2: Fix loop to stop at node before pos

   Change loop condition to i < pos-1 so curr points to previous node, allowing safe link update.

3. Final Answer:

   Logic error because loop goes to pos instead of pos-1; fix loop to i < pos-1 -> Option A

4. Quick Check:

   Loop to pos-1 for previous node [OK]

Hint: Loop to node before position, not at position [OK]

Common Mistakes:

• Looping to pos causing nil pointer
• Not handling pos 0 case
• Assuming curr.next always exists

5. Given a singly linked list with nodes: 5 -> 10 -> 15 -> 20 -> 25 -> null, write the resulting list after deleting nodes at positions 0, 2, and then 1 in that order. What is the final list?

hard

A. 10 -> 20 -> null

B. 10 -> 15 -> 25 -> null

C. 5 -> 15 -> 25 -> null

D. 10 -> 25 -> null

Solution

1. Step 1: Delete node at position 0

   Remove first node (5), list becomes 10 -> 15 -> 20 -> 25 -> null.

2. Step 2: Delete node at position 2

   Positions now: 0=10,1=15,2=20,3=25. Remove node 20, list becomes 10 -> 15 -> 25 -> null.

3. Step 3: Delete node at position 1

   Positions now: 0=10,1=15,2=25. Remove node 15, list becomes 10 -> 25 -> null.

4. Final Answer:

   10 -> 25 -> null -> Option D

5. Quick Check:

   Delete 0,2,1 in order = 10->25 [OK]

Hint: Update list after each deletion before next [OK]

Common Mistakes:

• Not updating positions after deletions
• Deleting wrong nodes due to stale positions
• Confusing zero-based indexing