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.

Practice

1. What does the insertion operation do in a data structure?

easy

A. Searches for an element in the collection

B. Removes an element from the collection

C. Adds a new element at a specific position

D. Sorts the elements in the collection

Solution

1. Step 1: Understand the meaning of insertion

   Insertion means adding something new into a collection or list.

2. Step 2: Identify what insertion does in data structures

   It places a new element at a chosen position, not removing or searching.

3. Final Answer:

   Adds a new element at a specific position -> Option C

4. Quick Check:

   Insertion = Add element [OK]

Hint: Insertion means adding, not removing or searching [OK]

Common Mistakes:

• Confusing insertion with deletion
• Thinking insertion sorts elements
• Mixing insertion with search operation

2. Which of the following is the correct syntax to insert an element x at position i in a Python list lst?

easy

A. lst.push(i, x)

B. lst.add(i, x)

C. lst.append(i, x)

D. lst.insert(i, x)

Solution

1. Step 1: Recall Python list insertion method

   Python lists use the method insert(position, element) to add elements at a specific index.

2. Step 2: Match the correct syntax

   lst.insert(i, x) correctly inserts x at index i.

3. Final Answer:

   lst.insert(i, x) -> Option D

4. Quick Check:

   Python list insertion = insert() method [OK]

Hint: Use insert(index, value) to add at position in Python list [OK]

Common Mistakes:

• Using append() to insert at a position
• Using add() which is not a list method
• Using push() which is from other languages

3. Consider a list lst = [10, 20, 30, 40]. After executing lst.pop(1), what is the resulting list?

medium

A. [10, 30, 40]

B. [10, 20, 30, 40]

C. [20, 30, 40]

D. [10, 20, 40]

Solution

1. Step 1: Understand pop(index) operation

   The pop method removes the element at the given index and returns it.

2. Step 2: Remove element at index 1 from the list

   Index 1 corresponds to element 20, so it is removed. The list becomes [10, 30, 40].

3. Final Answer:

   [10, 30, 40] -> Option A

4. Quick Check:

   pop(1) removes second element [OK]

Hint: pop(i) removes element at index i [OK]

Common Mistakes:

• Removing wrong index element
• Confusing pop() with remove(value)
• Expecting pop() to return the list

4. What is wrong with this code snippet for deleting an element val from a list lst?

for i in range(len(lst)):
    if lst[i] == val:
        lst.pop(i)

medium

A. pop() cannot be used inside a loop

B. It may skip elements after deletion due to index shift

C. The code will cause a syntax error

D. pop() removes all occurrences of val automatically

Solution

1. Step 1: Analyze loop and pop behavior

   When an element is popped, the list shrinks and elements shift left, but the loop index continues increasing.

2. Step 2: Identify the problem caused by index shift

   This causes the next element after a deletion to be skipped because the index moves forward without checking the shifted element.

3. Final Answer:

   It may skip elements after deletion due to index shift -> Option B

4. Quick Check:

   Deleting while iterating forward causes skipping [OK]

Hint: Avoid modifying list size while iterating forward [OK]

Common Mistakes:

• Thinking pop() causes syntax error
• Assuming pop() deletes all matching elements
• Ignoring index shift after deletion

5. You have a list lst = [5, 0, 3, 0, 2]. You want to delete all zero values using a single list comprehension. Which code correctly performs this deletion?

hard

A. lst = [x for x in lst if x != 0]

B. lst = [lst.pop(i) for i in range(len(lst)) if lst[i] == 0]

C. lst = [x for x in lst if x == 0]

D. lst = [lst.remove(0) for x in lst]

Solution

1. Step 1: Understand list comprehension for filtering

   List comprehension can create a new list including only elements that meet a condition.

2. Step 2: Filter out zero values

   The expression [x for x in lst if x != 0] keeps all elements except zeros, effectively deleting zeros.

3. Final Answer:

   lst = [x for x in lst if x != 0] -> Option A

4. Quick Check:

   Filter with condition x != 0 removes zeros [OK]

Hint: Use list comprehension to filter out unwanted elements [OK]

Common Mistakes:

• Using pop or remove inside list comprehension incorrectly
• Filtering to keep zeros instead of removing
• Expecting pop/remove to work inside comprehension