C Vector/ArrayList/LinkedList

Question

I'm doing a little program in C and I'd need a kind of vector/ArrayList/LinkedList but I'm working with C. Any idea on how I could do that kind of thing in C?

I want to store structs and then append/remove some.

Answer 1

For resizable arrays you can use malloc() and realloc(). These allow you to reserve (with malloc()) and resize (with realloc()) a certain amount of space on the heap. They're used this way:

int* a = malloc(10 * sizeof(int));

if(a == NULL) {}     // malloc() was unable to allocate the memory, handle the
                     // error and DO NOT use this pointer anymore

// now you can treat a as a normal array of 10 ints:
a[4] = 51;

// suppose 10 ints aren't no more enough:
a = realloc(a, 20 * sizeof(int));

if(a == NULL) {}     // same thing as before

// here you have 20 ints, the previous 10 are still there
a[18] = a[4]

// don't forget to free the memory when you have finished:
free(a);

Just replace 'int' with your struct type. ;)

Answer 2

Use an existing implementation. There are billions. Glib is probably a good place to start, or LibH.

Answer 3

I used @Conrad Meyer's answer. Downloaded latest Glib library from here and compiled it using this manual. To test Glib libraries I used this test. You may have errors while compiling the test code. This will help you solve your problem.

Also I found that there is a some kind of memory leak in the test code. Valgrind result running the original code:

==20350== HEAP SUMMARY:
==20350==     in use at exit: 4,632 bytes in 12 blocks
==20350==   total heap usage: 12 allocs, 0 frees, 4,632 bytes allocated
==20350== 
==20350== LEAK SUMMARY:
==20350==    definitely lost: 0 bytes in 0 blocks
==20350==    indirectly lost: 0 bytes in 0 blocks
==20350==      possibly lost: 992 bytes in 4 blocks
==20350==    still reachable: 3,640 bytes in 8 blocks
==20350==         suppressed: 0 bytes in 0 blocks

So I inserted one line in the code:

#include <stdio.h>
#include <glib.h>

int main(int argc, char** argv) {
    GList* list = NULL;
    list = g_list_append(list, "Hello world!");
    printf("The first item is '%s'\n", (char *)g_list_first(list)->data);
    g_list_free(list);
    return 0;
}

Valgrind new results:

==20310== HEAP SUMMARY:
==20310==     in use at exit: 4,632 bytes in 12 blocks
==20310==   total heap usage: 12 allocs, 0 frees, 4,632 bytes allocated
==20310== 
==20310== LEAK SUMMARY:
==20310==    definitely lost: 0 bytes in 0 blocks
==20310==    indirectly lost: 0 bytes in 0 blocks
==20310==      possibly lost: 0 bytes in 0 blocks
==20310==    still reachable: 4,632 bytes in 12 blocks
==20310==         suppressed: 0 bytes in 0 blocks

This answer tells that there is no need to worry about still reachable memory.

Answer 4

C does not come with any form of a standard collection (unlike higher-level languages such as C++ and Java) so you're left with a few options:

1. Use an existing one created by some group/some individual (as mentioned above)
2. Create your own

You'll need to consider exactly what you need for this program to determine what you use. From what you're asking for, you're probably looking for one of two options:

1. An array that will dynamically grow when you've allocated. Essentially, you need to maintain how many elements are contained within your array at that point. If at any point during insertion you are over the maximum amount of elements, you must create a new array, copy the elements into the new array, insert the new element and finally delete the old array. This tends to be faster in terms of access time (since it's indexable) but slow and memory-consuming if you over-allocate. See BlackBear's code for an example.
2. A linked list that dynamically grows by design. See here: http://en.wikipedia.org/wiki/Linked_list#Singly-.2C_doubly-.2C_and_multiply-linked_lists. This has the main advantage of no extra maintenance in the special case but the disadvantage of slow access (look at each element until you find the element you want).

See the Wikipedia page for more information on trade offs between the two kinds of data structures.