How to insert an element into an array on malloc?

Question

say we are going to insert an element into an array on malloc. I know where and how to insert, but I'm having trouble shuffling every succeeding element down by 1. What would be the technical approach for this? Thanks

| x x x x x x x x x x x | original array
| x x x x x 0 x x x x x x | new array

Suppose the "memmove" function is not available to us...

Answer 1

As Don suggested, memmove() will allow moving part of this array, in order to make room for the new element.

Depending on the size of the elements in the array, you may also consider storing only pointers, in the array, allowing easier/faster re-shuffling of the array, at the cost of a extra indirection when accessing individual elements. (and also at the cost of having to manage individual element-sized memory blocks). Deciding on this type of approach depends on the amount of reorganization of the array elements, as well as their size.

Alert: in view of the added "picture" in the question, memmove(), or indeed any operation, may be impossible, if the memory move implies writing past the size of memory originally allocated!
If this is really what is desired, the idea of an array of pointers may be more appropriate as this allows allocating an over-sized memory block initially (for the array proper) and to allocate (or dispose of) individual elements as needed.

Edit: "We're not allowed to use memmove()" indicates some form of homework. (BTW do tag it as such !!!)
To better help you we need to understand the particular premise of the question. Here's what appears to be the situtation:

1) we readily have an array, containing say N elements.
2) the array on the heap, i.e. it was allocated using malloc() (or related
   functions)
3) the effective size of the malloc-ated block of memory is bigger than that of
   the array.  
  Is #3  true ?
4) Depending on #3 we need to either allocate a new memory block (a bigger one)
   and copy the array.  We expect this copy would be done in 3 steps
       - copy the elements that precede the new element
       - copy the new element
       - copy the elements that are after the new element
   or...  (if we have enough room), we'd require two steps
       - "shift" the elements that are supposed to be after the new element
         This can be done one element at a time, if we wish to avoid memcopy
       - copy the new element.

Answer 2

Yes, if you need to do this without memmove, you can do it with a simple loop. Note that you might also need to use realloc first, to expand the size of the allocated array so that it can fit the new element.

The trick to this is having the loop move each element one forward, starting from the last one. A moment's reflection should tell you why this is necessary.

Answer 3

The basic principle is the same whether the array is dynamically allocated, statically allocated or automatically allocated. The main difference is that if there is insufficient room in a dynamically allocated array, you can reallocate it with more space (subject to some system-imposed limits. Assuming there is enough space in the array, you could use memmove() to copy the section of the array after target location up one space, and then set the target location to the inserted value. Or you could write a loop to do the job.

int *dynarr = malloc(24 * sizeof(*dynarr));
int  idx = 0;
dynarr[idx++] = 0;
dynarr[idx++] = 23;
dynarr[idx++] = 34;
dynarr[idx++] = 9;
dynarr[idx++] = 15;

Now insert at position n = 2:

memmove(&dynarr[n+1], &dynarr[n], (idx - n) * sizeof(int));
dynarr[n] = 19;
idx++;

That's a bulk move, an assignment, and increment the counter because there's one more element in the array.

---

Since the question was edited to disallow memmove(), here is a solution with simple array indexing, assuming that the same initialization sequence is used:

int i;
int n = 2;

for (i = idx; i > n; i--)
{
    dynarr[i] = dynarr[i-1];
}
dynarr[n] = 19;
idx++;

---

Complete example code:

#include <stdlib.h>
#include <string.h>
#include <stdio.h>

static void print_array(int *a, int n)
{
    int i;
    for (i = 0; i < n; i++)
    {
     printf("a[%d] = %d\n", i, a[i]);
    }
}

int main()
{
    {
     int *dynarr = malloc(24 * sizeof(*dynarr));
     int  idx = 0;
     dynarr[idx++] = 0;
     dynarr[idx++] = 23;
     dynarr[idx++] = 34;
     dynarr[idx++] = 9;
     dynarr[idx++] = 15;

     printf("Before insert\n");
     print_array(dynarr, idx);
     int n = 2;
     memmove(&dynarr[n+1], &dynarr[n], (idx - n) * sizeof(int));
     dynarr[n] = 19;
     idx++;
     printf("After insert\n");
     print_array(dynarr, idx);
     free(dynarr);
    }

    {
     int *dynarr = malloc(24 * sizeof(*dynarr));
     int  idx = 0;
     dynarr[idx++] = 0;
     dynarr[idx++] = 23;
     dynarr[idx++] = 34;
     dynarr[idx++] = 9;
     dynarr[idx++] = 15;

     printf("Before insert\n");
     print_array(dynarr, idx);

     int n = 2;
     int i;

     for (i = idx; i > n; i--)
     {
      dynarr[i] = dynarr[i-1];
     }
     dynarr[n] = 19;
     idx++;
     printf("After insert\n");
     print_array(dynarr, idx);
     free(dynarr);
    }

    return(0);
}