CODEWITHSUNDEEP
cdynamic-arrays
MiJyn
MiJyn

Reputation: 5867

How to _delete_ element from dynamic array?

I have seen other answers to questions like this, but none seemed to work for me. Say I have a dynamic array:

int* myarray;
myarray = malloc(myarray, 4*sizeof(int));
myarray[0] = 1;
myarray[1] = 2;
myarray[2] = 3;
myarray[3] = 4;

What I want to do is to remove (and free, because the array will keep on getting larger and larger) the first element of the array. I am well aware of realloc which removes the last element of the array if shrunk. Any ideas on this? Is this possible?

Thanks in advance!

Upvotes: 1

Views: 4119

Answers (4)

Afonso Tsukamoto
Afonso Tsukamoto

Reputation: 1214

I don't think that you'll find a proper/clean way to do that in C. C++ as some lybraries who do that, and almost all the OO oriented languages can do that, but not C. All I can think of is moving memory and, yes, calling realloc, or setting the position you want to free to a known value wich you'll consider empty in a memory re-use policy.

Another way to turn the problem is by a dynamic implementation of the array. DOn't know if you want to go there, but if you do, here's some brief example.

Since you're only saving integers, a struct like this: 

typedef struct DynamicArray_st{
 int x;
 struct DynamicArray_st *next;
}DynamicArray;

Makes it possible to alloc and free elements as the program needs to. It also allows insertion in the middle, begin or end and the same for frees.

The way you'll do it is by saving a pointer to the begin of this dynamic type and then iterate over it. The problem is that you can't access data by the [] notation. Iterations are necessary wich makes it heavier on processing time.

Besides that, your code would become something like this:

DynamicArray *array = malloc(sizeof(DynamicArray)); /*Just a first element that will stay empty so your Dynamic array persists*/
 array->next = NULL;
 DynamicArray *aux = array;
 DynamicArray *new;
 for(i = 0; i<4; i++){
    new = malloc(sizeof(DynamicArray));
    new->next = NULL;
    new->x = i+1;
    aux->next = new;
    aux = new;
 }

Here you have a sequence of structs in a way that each struct points to the next one and has a integer inside. If now you'd do something like: 

aux = array->next; /*array points to that empty one, must be the next*/
 while(aux != NULL){
   printf("%d\n",aux->x);
   aux = aux->next;
 }

You'll get the output: 

1
2
3
4

And freeing the first element is as easy as: 

  aux = array->next;
  array->next = aux->next;
  free(aux);

If you try to draw it(structs are boxes and next/aux/next are arrows) you'll see one boxe's arrow outline an box - the one you want to free.

Hope this helps.

Upvotes: 0

Karthik T
Karthik T

Reputation: 31952

Typically a "Delete" operation is not possible on an array. Perhaps you want to create and use a linked list?

C++ has its std::vector which supports this. What it would do is to shift elements that come later, forward by 1 element. You could implement this, and call realloc later.

Storing them in reverse is an obvious workaround if only first element needs to be deleted.

Upvotes: 0

paddy
paddy

Reputation: 63471

You have to shunt all the other elements along one. Conceptually, it's like this:

for( int i = 0; i < 3; i++ ) p[i] = p[i+1];

As others have mentioned, memmove is optimized for shifting memory segments that overlap, rather than using the above loop.

Moving data around is still inefficient as your array grows larger. Reallocating an array every time you add an item is even worse. General advice is don't do it. Just keep track of how large your array is and how many items are currently stored in it. When you grow it, grow it by a significant amount (typically you would double the size).

It sounds like you might want a circular queue, where you preallocate the array, and a head and tail pointer chase each other round and round as you push and pop items on.

Upvotes: 0

Grieverheart
Grieverheart

Reputation: 510

One method I can think of is doing


memmove(myarray, myarray+1, 3*sizeof(int))

and then use realloc to shrink the array. I'm not sure there are more efficient ways to do this in C.

Upvotes: 6

Related Questions