Array 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 remove elements from an array at desired positions seamlessly.

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.
2. Delete an element at the last index.
3. Delete an element at any given index (say, middle).

Learn about array insertion algorithms here - Array insertions.

Delete an item at the start/middle index

Think of a scenario where our array is filled with values. And we want to delete an item at the start/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.

Sketch

The sketch looks like this:

Code

Enough talk. Here is a simple algorithm that creates an array with a size 10, and inserts removes an item at the index 2. Finally, we remove an element, shift all right elements to 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.

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.

Sketch

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 removed the value at the end.
2. Space complexity: O(1), no extra space is occupied other than the input memory.