Deletion in array
Deletion in array
Deletion in array refers to removing an existing element from the array and reorganzing all element of an array.Deleting an element does not affect the size of the array.
This operation is use to delete an element from specific position from one dimensional array.
In deletion shift the elements to their adjacent left to fill the void created after deleting an element at some index.
Diagramatic Representation
Step by step logic to remove element from array.
- Firstly,Move to the specified location which you want to remove in given array.
- Then copy the next element to the current element of array. Which is you need to perform
array[i] = array[i + 1]. - Repeat above steps till last element of array.
- Finally decrement the size of array by one.
Algorithm
Consider LA is a linear array with N elements and K is a positive integer such that K<=N. Following is the algorithm to delete an element available at the Kth position of LA.
1. Start
2. Set J = K
3. Repeat steps 4 and 5 while J < N
4. Set LA[J] = LA[J + 1]
5. Set J = J+1
6. Set N = N-1
7. Stop
Program in C
#include<stdio.h>
// This function removes an element x from arr[] and
// returns new size after removal (size is reduced only
// when x is present in arr[]
int deleteElement(int arr[], int n, int x)
{
// Search x in array
int i;
for (i=0; i<n; i++)
if (arr[i] == x)
break;
// If x found in array
if (i < n)
{
// reduce size of array and move all
// elements on space ahead
n = n - 1;
for (int j=i; j<n; j++)
arr[j] = arr[j+1];
}
return n;
}
/* Driver program to test above function */
int main()
{
int arr[] = {11, 15, 6, 8, 9, 10};
int n = sizeof(arr)/sizeof(arr[0]);
int x = 6;
// Delete x from arr[]
n = deleteElement(arr, n, x);
printf("Modified array is \n");
for (int i=0; i<n; i++)
printf( arr[i]);
return 0;
}
Output
Modified array is 11 15 8 9 10
Program in CPP
#include<bits/stdc++.h>
using namespace std;
int deleteElement(int arr[], int n, int x)
{
int i;
for (i=0; i<n; i++)
if (arr[i] == x)
break;
if (i < n)
{
n = n - 1; // reduce size of array and move all elements on space
for (int j=i; j<n; j++)
arr[j] = arr[j+1];
}
return n;
}
int main()
{
int arr[] = {11, 15, 6, 8, 9, 10};
int n = sizeof(arr)/sizeof(arr[0]);
int x = 6;
n = deleteElement(arr, n, x); // Delete x from arr[]
cout << "Modified array is \n";
for (int i=0; i<n; i++)
cout << arr[i] << " ";
return 0;
}
Output
Modified array is 11 15 8 9 10
Deletion in array in Java
Approach
Firstly,We start to iterate from the position from which we want to delete the element. The reason for this is so that all the elements after the element which is deleted will be shifted by one place towards the left.
Different methods to delete an element from an array
1.Using Another Array
In this method we define a new array with size less than 1 to the original array. Then we copy the elements from the original array to the new array. But while doing this copying, we skip the element at the specified index.
Program in Java
import java.util.Arrays;
class ABC {
public static int[] removeTheElement(int[] arr, int index)
{
if (arr == null || index < 0
|| index >= arr.length) {
return arr;
}
int[] anotherArray = new int[arr.length - 1];
for (int i = 0, k = 0; i < arr.length; i++) {
// if the index is
// the removal element index
if (i == index) {
continue;
}
anotherArray[k++] = arr[i];
}
return anotherArray;
}
public static void main(String[] args)
{
int[] arr = { 1, 2, 3, 4, 5 };
System.out.println("Original Array: "
+ Arrays.toString(arr));
// Get the specific index
int index = 2;
// Print the index
System.out.println("Index to be removed: " + index);
// Remove the element
arr = removeTheElement(arr, index);
// Print the resultant array
System.out.println("Resultant Array: "
+ Arrays.toString(arr));
}
}
Output
Original Array: [1, 2, 3, 4, 5] Index to be removed: 2 Resultant Array: [1, 2, 4, 5]
2.Using ArrayList
In this method we first convert the array to an ArrayList and then use the ‘remove’ method of ArrayList to remove the element at a particular index
Program
import java.util.Arrays;
import java.util.List;
import java.util.stream.Collectors;
import java.util.stream.IntStream;
class ABC {
public static int[] removeTheElement(int[] arr, int index)
{
if (arr == null
|| index < 0
|| index >= arr.length) {
return arr;
}
List<Integer> arrayList = IntStream.of(arr)
.boxed()
.collect(Collectors.toList());
arrayList.remove(index);
return arrayList.stream()
.mapToInt(Integer::intValue)
.toArray();
}
public static void main(String[] args)
{
int[] arr = { 1, 2, 3, 4, 5 };
System.out.println("Original Array: "
+ Arrays.toString(arr));
int index = 2;
System.out.println("Index to be removed: "
+ index);
arr = removeTheElement(arr, index);
System.out.println("Resultant Array: "
+ Arrays.toString(arr));
}
}
Output
original Array: [1, 2, 3, 4, 5] Index to be removed: 2 Resultant Array: [1, 2, 4, 5]
Program in Python
def deleteElement(arr,n,x):
if arr[n-1]==x:
return n-1
prev = arr[n-1]
for i in range(n-2,1,-1):
if arr[i]!=x:
curr = arr[i]
arr[i] = prev
prev = curr
if i<0:
return 0
arr[i] = prev
return n-1
arr = [11,15,6,8,9,10]
n = len(arr)
x = 6
n = deleteElement(arr,n,x)
print("Modified array is")
for i in range(n):
print(arr[i],end=" ")
Output
Modified array is 11 15 8 9 10
Program in Javascript
<script>
function deleteElement( arr, n, x)
{
let i;
for (i=0; i<n; i++)
if (arr[i] == x)
break;
if (i < n)
{
n = n - 1;
for (let j=i; j<n; j++)
arr[j] = arr[j+1];
}
return n;
}
let arr = [11, 15, 6, 8, 9, 10];
let n = arr.length;
let x = 6;
n = deleteElement(arr, n, x);
document.write("Modified array is </br>");
for (let i=0; i<n; i++)
document.write(arr[i] + " ");
</script>
Output
Modified array is 11 15 8 9 10
Time Complexity
Deleting an element from an array takes O(n) time.
Also read various Array operation