Data Structures - Arrays - Deletion

In this tutorial we will learn to delete elements from an Array data structure in different positions.

Table of Content

• Deletion
• Delete from the end
• Delete from the beginning
• Delete at index

Deletion

We can delete an element from the end, beginning and in between.

Delete from the end

In order to delete an element from the end of an array of a given SIZE, we will maintain a variable END that will always point to the last element of the array. If there is no element in the array then END will be set to -1 and we will not perform deletion. If there are elements in the array then END will be greater than -1 hence we can set the element at index END to some random value (optional) and then decrement END by 1.

Time complexity will be O(1).

Before
arr = 1 2 3 4 5
              ^
              END

Delete last element. Decrement END by 1.

After
arr = 1 2 3 4 0
            ^
            END

Delete from the beginning

We we delete from the beginning of the array i.e., index 0 then we move all the elements on the right side of index 0 by 1 position to the left and we decrement the END variable by 1 so that it points to the correct last position.

Time complexity will be O(n).

Before
arr = 1 2 3 4 5
      ^       ^
      DELETE  END

Move all the elements one position left. Decrement END by 1.

After
arr = 2 3 4 5 0
            ^
            END

Delete at index

When deleting an element at index I we have to left shift all the elements on the right side of index I by one position and then decrement the END variable by 1.

Time complexity will be O(n).

Before
arr = 1 2 3 4 5
          ^   ^
     DELETE   END

Move all the elements one position left. Decrement END by 1.

After
arr = 1 2 4 5 0
            ^
            END

Example

In the following C++ example we are going to demonstrate deletion of an element from an array.

#include <iostream>
using namespace std;

const int SIZE = 5;
int arr[SIZE];
int END = -1;

void freshInsertElements()
{
  cout << "REFRESH!" << endl;
  cout << "Inserting " << SIZE << " elements in the array arr..." << endl;
  int i;
  for (i = 0; i < SIZE; i++)
  {
    arr[i] = i + 1;
  }
  END = SIZE - 1;
}

void print()
{
  cout << "Printing the content of array arr..." << endl;
  int i;
  for (i = 0; i <= END; i++)
  {
    cout << "arr[" << i << "] = " << arr[i] << endl;
  }
  cout << endl;
}

void deleteFromEnd()
{
  cout << "Delete from end" << endl;
  END--;
}

void deleteFromBeginning()
{
  cout << "Delete from beginning" << endl;
  int i;
  for (i = 1; i <= END; i++)
  {
      arr[i - 1] = arr[i];
  }
  END--;
}

void deleteIndex(int index)
{
  cout << "Delete element at index " << index << "." << endl;
  int i;
  for (i = index + 1; i <= END; i++)
  {
    arr[i - 1] = arr[i];
  }
  END--;
}

int main(void)
{
  freshInsertElements();
  print();
  deleteFromEnd();
  print();

  freshInsertElements();
  print();
  deleteFromBeginning();
  print();

  freshInsertElements();
  print();
  deleteIndex(3);
  print();

  return 0;
}

Output

REFRESH!
Inserting 5 elements in the array arr...
Printing the content of array arr...
arr[0] = 1
arr[1] = 2
arr[2] = 3
arr[3] = 4
arr[4] = 5

Delete from end
Printing the content of array arr...
arr[0] = 1
arr[1] = 2
arr[2] = 3
arr[3] = 4

REFRESH!
Inserting 5 elements in the array arr...
Printing the content of array arr...
arr[0] = 1
arr[1] = 2
arr[2] = 3
arr[3] = 4
arr[4] = 5

Delete from beginning
Printing the content of array arr...
arr[0] = 2
arr[1] = 3
arr[2] = 4
arr[3] = 5

REFRESH!
Inserting 5 elements in the array arr...
Printing the content of array arr...
arr[0] = 1
arr[1] = 2
arr[2] = 3
arr[3] = 4
arr[4] = 5

Delete element at index 3.
Printing the content of array arr...
arr[0] = 1
arr[1] = 2
arr[2] = 3
arr[3] = 5