Algorithm - Inserting an item into a contiguous list

Like deletion, we have two cases in insertion:

Insert in the beginning and middle:

In this case, we need to look for the position of the element to be inserted. The operation is carried out in two steps:
  • Increment the size of the array with 1.
  • Shift all elements from n to k and then insert the element at the position k.

Insert at end:

This is a very simple case because the offset is not performed.

The algorithm that combines the two cases:

Insert algorithm;
Var 
  i,k,x: integer;
  T[1..n]: integer;
Start
  read(s);
  n:=n+1;
  for i from n to k not-1
  faire
    T[i+1] := T[i];
  finfaire
      T[k] := x;
End

Procedure:

Procedure insert(L:list,k:1..lmax, x:element)
var i,n:1..lmax;
Start
  n := L.length;
  L.Length:= n+1;
  for i from n to k not-1
  faire
    L.T[i+1] := L.T[i];
  finfaire
  L.T[i] := x;
End