C remove element from dynamic array

Question

I'm trying to write the equivalent of remove for Java's ArrayList in C.

Here is my code. It assumes that index is a valid index in the list.

void arrayListRemove(ArrayList* list, int index){
  int i;
  if (arrayListSize(list)==1){
    list->size = 0;
    free(list->data);
    list->data = NULL;
  } else {
    for(i=index;i<arrayListSize(list)-1;i++){
      list->data[i] = list->data[i+1];
    }
    list->data = realloc(list->data, (arrayListSize(list) - 1) * sizeof(void*));
    if (list->data != NULL){
      --list->size;
    } else {
      exit(1);
    }
  }
}

Is this correct?

Would the code work without the arrayListSize(list) == 1 check? I.e. does realloc(list->data, 0) free the arrayList? I've seen conflicting things online about what realloc(ptr, 0) would do.

"Is this correct" covers a lot of ground. Do you have any specific questions, like "why does this crash on line X for input Y", or "could this be made faster", etc.? — Nate Kohl
– Nate Kohl, Commented Jul 25, 2012 at 19:01
Would the code work without the arrayListSize(list) == 1 check? ie. does realloc(list->data, 0) free the arrayList? I've seen conflicting things online about what realloc(0) would do. — Sue Sueson
– Sue Sueson, Commented Jul 25, 2012 at 19:11
Note: you could avoid the explicit loop by using memmove(). And you could replace the sizeof(void*) by sizeof list->data[0]. If the list is unordered, it is cheaper to replace the deleted element by the last element in the array. Finally: if index is beyond the size, you still decrement the size, which looks wrong. — wildplasser
– wildplasser, Commented Jul 25, 2012 at 19:27

pb2q · Accepted Answer · 2012-07-25 22:32:18Z

3

I would leave the arrayListSize(list) == 1 case. Not relying on the behavior of realloc(ptr, 0) seems prudent, and it makes the code clearer, generally and by using an explicit free.

A few more notes:

When using realloc, be sure to capture the return value in a tmp variable. If realloc fails, then it can return NULL and leave the original pointer untouched. By doing ptr = realloc(ptr); you can cause a memory leak when realloc fails, because you've now lost your original pointer. Instead use this idiom:
```
tmp = realloc(ptr, newSize);
if (tmp != NULL)
    ptr = tmp;
else handleError();
```
Is it necessary to free the elements of your list when removing them from the list? Your data array consists of pointers, are you leaking memory by not calling free on removed elements? Naturally this isn't necessary in the java implementation. If your list contains the only reference to the contained objects, then you'll need to free them upon remove, or return the pointer in your function and leave it up to the caller to deal with the memory.
There's typically no need to use realloc for shrinking a list, unless you're on a platform that is really memory constrained, and even then, it's probably unnecessary to shrink allocated blocks for every deleted list element. Prefer to grow/shrink your allocated blocks by more than a single element.
This is really a nit, but since this is an API method, and you're using a size member of your data structure to track the list length, you might as well use size throughout, rather than relying on another API method arrayListSize.

edited Jul 25, 2012 at 22:32

answered Jul 25, 2012 at 18:59

pb2q

59.9k19 gold badges150 silver badges152 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

ardent Over a year ago

Going to also add a comment in that, if you are emulating Java's arraylist functionality, they don't shrink the array, only decrement the number of elements contained

Collectives™ on Stack Overflow

C remove element from dynamic array

1 Answer 1

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related