1.3 Array Operations | Deletion from Array | Explanation with Code | Data Structure
Education
Introduction
In this article, we will explain the deletion operation in an array using a specific example. Understanding how to delete an element from a specific position in an array will make it easier to understand deletions from the beginning or the end of the array.
Deletion Operation Explanation
Initial Setup
We begin by declaring an array of size 50. Memory is allocated 200 bytes for this array, with variable size
representing the current size of the array. Let's say the user wants to store only 5 elements in the array. We prompt the user to enter the size and the elements to initialize the array at runtime.
Example
Suppose the array is initialized with the following elements:
A = [6, 2, 10, 4, 5]
The user asks to delete the element at position 2 (i.e., array[1]
which is 2
). When you delete 2
at position 2, you cannot leave that position blank. Instead, you will shift subsequent elements to the left and decrease the size by one.
Shifting Elements
To shift elements:
- A loop starts from
index = position - 1
untilindex = size - 2
. - Move the element at
index + 1
toindex
. - Decrease the size of the array by 1.
For example:
A = [6, 2, 10, 4, 5]
After deletion of 2
from position 2:
A = [6, 10, 4, 5]
Updated size is now 4.
Code Implementation
Now, let's look at the code to implement this logic:
#include <stdio.h>
int main() (
int a[50];
int size, position;
printf("Enter the size of the array: ");
scanf("%d", &size);
printf("Enter the elements of the array: ");
for (int i = 0; i < size; i++) {
scanf("%d", &a[i]);
)
printf("Enter the position from which to delete: ");
scanf("%d", &position);
if (position <= 0 || position > size) (
printf("Invalid position!\n");
) else (
for (int i = position - 1; i < size - 1; i++) {
a[i] = a[i + 1];
)
size--; // Reduce the size of the array
printf("Array after deletion: \n");
for (int i = 0; i < size; i++) (
printf("%d ", a[i]);
)
}
return 0;
}
Handling Special Cases
- Valid Position Check: Ensure the entered position is within range.
- Underflow Check: Ensure there are elements to delete.
Time Complexity
The time complexity of the deletion operation depends on the position:
- Best Case: Deleting from the end (position
size - 1
), time complexity is (O(1)). - Worst Case: Deleting from the beginning (position
0
), it requires shifting all elements, time complexity is (O(n)).
Optimized Approach for Unsorted Arrays
If the array is unsorted, a quick alternative method can be applied:
- Replace the element to be deleted with the last element.
- Reduce the size by one.
Conclusion
This article covered the detailed process of deleting an element from an array including code implementation and time complexity. This forms the basis for understanding deletions in more complex data structures like linked lists.
Keywords
- Array
- Deletion
- Position
- Shifting
- Time Complexity
- Underflow
- Valid Position Check
- Unsorted Array
FAQs
Q1: What happens if I try to delete from an invalid position? A1: The program will print "Invalid position!" and no deletion will occur.
Q2: Can elements be deleted without shifting in the array? A2: Yes, in unsorted arrays, by replacing the element to be deleted with the last element, followed by reducing the array size.
Q3: What is the time complexity of the deletion operation from an array? A3: It varies; (O(n)) for deleting from the beginning and (O(1)) for deleting from the end.
Q4: How can handling overflows and underflows in arrays prevent bugs? A4: By checking array boundaries and ensuring valid positions, we can prevent underflow and overflow, thus avoiding potential runtime errors.
Q5: Why is shifting necessary when deleting an element? A5: Shifting fills the gap left by the deleted element, maintaining the array's structure and ensuring no null spaces are left within it.