Insertion and deletion operations in Data Structures Theory - Practice Problems & Coding Challenges

Challenge - 5 Problems

🧠 Conceptual

intermediate

Insertion in a singly linked list

What happens when you insert a new node at the beginning of a singly linked list?

A The new node becomes the head, and its next pointer points to the old head.

B The new node is added at the end, and the head remains unchanged.

C The new node replaces the last node, and the list size decreases by one.

D The new node is inserted in the middle, splitting the list into two halves.

💡 Hint

Think about how the head pointer changes when adding at the start.

Inserting at the beginning means the new node points to the current head, then the head is updated to the new node.

📋 Factual

intermediate

Deletion in an array

What is the time complexity of deleting an element from the middle of an array?

A O(1) because you can directly access the element.

B O(n^2) because all elements are copied twice.

C O(log n) because of binary search to find the element.

D O(n) because elements after the deleted one must be shifted.

💡 Hint

Consider what happens to elements after the deleted position.

Deleting from the middle requires shifting all elements after it one position left, which takes linear time.

🔍 Analysis

advanced

Effect of insertion order on binary search tree shape

Given the sequence of numbers inserted into an empty binary search tree: 10, 5, 15, 3, 7, 12, 18, which statement is true about the tree's shape?

A The tree is balanced but not perfectly; left and right subtrees have similar heights.

B The tree is skewed to the left with all nodes having only left children.

C The tree is skewed to the right with all nodes having only right children.

D The tree is perfectly balanced with equal nodes on both sides.

💡 Hint

Visualize the insertion process step-by-step.

Inserting 10, 5, 15, 3, 7, 12, 18 creates a balanced BST: root 10, left subtree (5,3,7) and right (15,12,18), with similar heights but not perfectly balanced.

❓ Comparison

advanced

Comparing deletion in doubly linked list vs singly linked list

Which advantage does a doubly linked list have over a singly linked list when deleting a node given a pointer to that node?

A Deletion is slower because you must update two pointers instead of one.

B Deletion is faster because you can access the previous node directly.

C Deletion requires traversing from the head to find the node in both lists.

D Deletion is impossible in doubly linked lists without head pointer.

💡 Hint

Think about how you find the previous node in each list type.

In a doubly linked list, each node has a pointer to its previous node, so deletion can be done directly without traversal.

❓ Reasoning

expert

Impact of insertion order on hash table collisions

Consider a hash table using chaining for collision resolution. If keys are inserted in ascending order and the hash function is key modulo table size, which scenario is most likely?

A Keys cluster in a few chains, increasing collisions in those chains.

B All keys hash to the same index, causing one long chain.

C Keys distribute evenly across all chains, minimizing collisions.

D Keys are inserted randomly, so collisions are unpredictable.

💡 Hint

Think about how modulo operation distributes sequential keys.

Sequential keys (ascending order) modulo table size hash to 0, 1, 2, ..., m-1 cycling evenly across all buckets/chains, minimizing collisions.