Deletion
Deletion from an array is the process of eliminating the value at a particular index.
Let’s return to our original example array and delete the value at index 2. In our example, this value is "cucumbers".
Step 1: We delete "cucumbers" from the array:
While the actual deletion of "cucumbers" technically took just one step, we now have a problem: we have an empty cell sitting smack in the middle of our array. An array isn’t effective when there are gaps in the middle of it, so to resolve this issue, we need to shift "dates" and "elderberries" to the left. This means our deletion process requires additional steps.
Step 2: We shift "dates" to the left:
Step 3: We shift "elderberries" to the left:
It turns out that for this deletion, the entire operation took three steps. The first step involved the actual deletion, and the other two steps involved data shifts to close the gap.
Like insertion, the worst-case scenario of deleting an element is deleting the very first element of the array. This is because index 0 would become empty, and we’d have to shift all the remaining elements to the left to fill the gap.
For an array of 5 elements, we’d spend 1 step deleting the first element and 4 steps shifting the 4 remaining elements. For an array of 500 elements, we’d spend 1 step deleting the first element, and 499 steps shifting the remaining data. We can say then, that for an array containing N elements, the maximum number of steps that deletion would take is N steps.
Congratulations! We’ve analyzed the time complexity of our first data structure. Now that you’ve learned how to analyze a data structure’s efficiency, you can now discover how different data structures have different efficiencies. This is crucial, because choosing the correct data structure for your code can have serious ramifications on your software’s performance.
The next data structure—the set—seems so similar to the array at first glance. However, you’ll see that the operations performed on arrays and sets have different efficiencies.
