Implementing an ArrayList

I implemented ArrayList functionality in C as follows:

```
#include
#include
#include "ArrayList.h"

struct _arraylist {
size_t size;
void ** data;
};

struct _arraylist *arraylist_create() {
/ Allocate Memory /
struct _arraylist *list = malloc(sizeof(struct _arraylist));
assert(list != NULL);
list->size = 0;
list->data = calloc(2, sizeof(void *));
assert(list->data != NULL);
list->data[0] = NULL;
return list;
}

void arraylist_setdata(struct _arraylist *list, void ** data, int max, int clear_data) {
/ Sets the internal array of the arraylist /
clear_data ? arraylist_clear(list) : NULL;
list->data = data;
list->size = max;
}

void arraylist_add(struct _arraylist list, void elem) {
/ Adds one element of generic pointer type to the internal array /
void ** new_data = realloc(list->data, arraylist_getsizeof(list));
assert(new_data != NULL);
new_data[list->size] = elem;
arraylist_setdata(list, new_data, list->size + 1, 0);
}

void arraylist_get(struct _arraylist list, int index) {
/ Gets an member of the array at an index /
return list->data[index];
}

size_t arraylist_getsizeof(struct _arraylist *list) {
/ Returns the size of the internal array in memory /
return sizeof(*list->data);
}
size_t arraylist_getsize(struct _arraylist *list) {
/ Returns the number of elements in the arraylist /
return list->size;
}

void arraylist_remove(struct _arraylist *list, int index, int freeit) {
/ Removes one element at and index /
if (index > list->size - 1)
return;
if (list->size == 1) {
arraylist_clear(list);
return;
}
if (freeit)
free(arraylist_get(list, index));
for ( int i = index; i size; ++i ) {
if (i == list->size - 1)
list->data[i] = NULL;
else
list->data[i] = list->data[i + 1];
}
void ** new_data = realloc(list->data, arraylist_getsizeof(list));
--l

First, a word on naming:

The name you've chosen for your type, _arraylist is a bad name for a library interface
type. Names starting with _ are not pleasant to work with in user code. They are commonly
used inside library internals. Better names would be ArrayList or array_list.

Actually, in your usage example, you have ArrayList. Does this mean that in the header,
which is not included here, you have something like this?

typedef _arraylist ArrayList;

If you did define an opaque type in the header, like above, that would be a good practice.
But then you should not use any reference to _arraylist in your code. Use always the typedef'd name to avoid confusion.

The function name prefix should also follow exactly the name of the type, so for ArrayList all functions should be prefixed the ArrayList_, e.g.:

ArrayList * ArrayList_create();

Also, I would suggest that you avoid tightlypacked names, like in arraylist_getsize(). Adding an
underscore to separate words makes them a lot more readable. E.g.: ArrayList_get_size().

Problems with memory:

Lets look at arraylist_create():

struct _arraylist *arraylist_create() {
    struct _arraylist *list = malloc(sizeof(struct _arraylist));
    assert(list != NULL);
    list->size = 0;
    list->data = calloc(2, sizeof(void *));
    assert(list->data != NULL);
    list->data[0] = NULL;
    return list;
}

First thing unusual here is the assertions. Assertions are not the proper way to
handle a memory allocation failure. Plus, they are commonly disabled on release builds,
so on release, if you'd happen to run out of memory, the program would just crash silently.
You should probably return a NULL in this case (maybe also log to stderr) and let the caller handle this error as he/she sees fit.

Second problem here is with calloc(). You are allocating 2 void pointers, however, size is set to zero.
I don't really get the point of this. Since your structure is more like and array of arrays then a list,
what you should do is allocate the array of pointers with some predefined default size, then allocate the
individual arrays as needed. Growing the array of pointers on demand. How arraylist_create() should look like:

ArrayList * ArrayList_create() {
    ArrayList *list = malloc(sizeof *list);
    if (list == NULL) {
        return NULL;
    }

    list->size = 0;
    list->data = calloc(INITIAL_BASE_ARRAY_SIZE, sizeof(void *));
    if (list->data == NULL) {
        free(list); // Don't leek memory here!
        return NULL;
    }

    return list;
}

Another big memory issue is the constant re-allocations done by arraylist_add() and arraylist_remove().

Remove should not shrink the sequence. Keep that space around if the array grows again in the future. You can add an explicit way to let the user shrink the storage if necessary (a la std::vector::shrink_to_fit()).

Adding to the array can be made to run in amortised-constant time if you pre-allocate storage with a larger size then the requested. (Again inspired by the STL vector).

sizeof mistake:

This will not return what you expect:

size_t arraylist_getsizeof(struct _arraylist *list) {
    /* Returns the size of the internal array in memory */
    return sizeof(*list->data);
}

The sizeof operator always returns the size of the type it is applied to.
It cannot infer the size of an array pointed by a pointer, because it is a
compile-time operation. arraylist_getsizeof() will always return the same value,
the size of a void pointer, which will be 4 or 8, depending on the architecture.

Use assertions to check for invariants:

You should assert that the *list parameter of every function is valid. This is a precondition of every function, they cannot work without a valid ArrayList instance, so you should assert that once the function enters.

Miscellaneous:

You don't need to check if the pointer is null before freeing it. In arraylist_deallocate() the if (list->data != NULL) check is uneeded.

arraylist_deallocate would be more symmetric with arraylist_create if named arraylist_destroy.

StackExchange Code Review Q#64423, answer score: 12