Deletions and Shifting Algorithms

Introduction

Java's array deletion and shifting algorithm is a fundamental technique to remove an element from an array at a specific position while efficiently shifting the existing elements to accommodate the deletion.

This algorithm is essential for dynamically modifying the contents of an array and maintaining its integrity.

By leveraging this algorithm, developers can easily handle array deletions, ensuring optimal performance and maintaining the order of elements.

In this article, you will learn the implementation of the array deletion and shifting algorithm in Java, providing a step-by-step guide and a code example that demonstrates how to seamlessly remove elements from an array at desired positions.

Deletion algorithms

Removing an array element is similar to Array insertions, but we remove an element with the following 3 different cases:

1. Delete an element at the first index (or) delete an element at any given index (say, middle).
2. Delete an element at the last index.

You have already learned about "Array Insertions" in the previous lesson. A similar logic is applied while deleting an entry.

1. Delete an item at the start/middle index.

Think of a scenario in which our array is filled with values, and we want to delete an item at the start or middle of the array.

Example: For example, consider an array A[10] that has elements {1, 2, 3, 4, 5, 6, 7, 8, 9, 10} stored in it, which is full.

The array capacity/length and size are both equal to 10. (array capacity is calculated using A.length, but the items inserted in the array are how size is calculated).

At any given index less than the size of the array. If we want to delete data, we must first shift all the elements from the next index to the left and then insert this new data.

Deleting an element at the start/middle of an array falls under array weaknesses, which might impact the performance if we are dealing with a massive array of elements as we need to shift the rest of the elements, which takes O(N) time unless we remove/delete an element at the end of the array, which takes O(1) time.

Illustration

The sketch looks like this:

Code

Enough talk. Here is a simple algorithm that creates an array with a size 10, and removes an item at the index 2. Finally, we remove an element, shift all right elements to the left(one index), and update the currentLength property of the array.

import java.util.Arrays;

public class ArrayDeletions {

    public static void main(String[] args) {
        int[] A = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
        // Say we want to delete the element at index 1
        int currentLength = A.length;

        System.out.println(Arrays.toString(A)); // [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
        System.out.println("current array items length: " + currentLength); // 10
        System.out.println("Array capacity: " + A.length); // 10
        for (int i = 2; i < A.length; i++) {
            // Shift each element one position to the left
            A[i - 1] = A[i];
        }

        // Again, the length needs to be consistent with the current
        // state of the array.
        currentLength -= 1;
        A[A.length - 1] = 0; // reset the last element to zero
        System.out.println("New array items length: " + currentLength); // 9

        System.out.println("After element is removed: " + Arrays.toString(A));
    }
}

/* 
Outputs:
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
current array items length 10
Array capacity 10
New array items length 9
After element is removed[1, 3, 4, 5, 6, 7, 8, 9, 10, 0]
*/

Complexity Analysis

1. Time complexity: O(N), as we remove the value at the start/middle index.
2. Space complexity: O(1), no extra space is occupied other than the input memory.

2. Delete an item at the end index

Removing an element at the last index consumes a single unit of time or constant time, as elements are not shifted to the left.

Illustration

Code

import java.util.Arrays;

public class ArrayDeleteFromEnd {
  public static void main(String[] args) {
    // Declare an integer array of 10 elements.
    int[] A = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};

    // Say we want to delete the element at index 1
    int currentLength = A.length;

    System.out.println(Arrays.toString(A)); // [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
    System.out.println("current array items length: " + currentLength); // 10
    System.out.println("Array capacity: " + A.length); // 10
    // The array currently contains 0 elements

    currentLength -= 1;
    A[A.length - 1] = 0;
    System.out.println("current array items length: " + currentLength); // 9
    System.out.println(Arrays.toString(A));
  }
}

/*
Outputs:
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
current array items length: 10
Array capacity: 10
current array items length: 9
[1, 2, 3, 4, 5, 6, 7, 8, 9, 0]
*/

Complexity Analysis

1. Time complexity: O(1), as we remove the value at the end/last index.
2. Space complexity: O(1), no extra space is occupied other than the input memory.