Deletions and insertions of elements

Operations like deleting an element from an array or inserting a new element into an array are common in practice: imagine having a list of students in a class, and one student leaves or a new one arrives. How do we update the list?

Deletion

Consider the following problem:

Given an array X with n integer elements and an index p. Delete the element at position p from array X.

Let's consider a vector with n=10 elements and p=4.

We want to remove the element at index 4, which has the value X[4] = 34. After deletion, the vector should look like this:

How do we proceed?

• The elements with indices p+1, p+2, …, n-1 shift left by one position.
• The size n of the array decreases by 1.

Deletion is done as follows:

for(int i = p ; i < n - 1; i ++)
      X[i] = X[i+1];
  n --;

Adding an element to an array

Adding an element to an array means increasing the logical size n of the array and storing the new value in the last element. The following sequences add a value to an array indexed from 0.

X[n] = val;
  n ++;

Or, more condensed:

X[n++] = val;

Inserting an element into an array

Consider the following problem:

Given an array X with n integer elements, an integer value val, and an index p. Insert the value val at position p in array X.

Similar to the algorithm for deleting an element from an array, inserting an element involves shifting elements to the right, starting from the end. The element X[p] is replaced with the new value, and the logical size of the array increases without exceeding the physical size.

for(int i = n - 1 ; i >= p ; i --)
      X[i+1] = X[i];
  X[p] = val;
  n ++;