Dynamic list in ANSI C?

Question

Am i right in thinking the only way to create a list which grows during run time in C, is to use a linked list?

Answer 1

You could use a combination of malloc and realloc. To first initialize a C array (malloc) and to grow it (realloc). However, you won't want to grow it by 1 element at a time if you are doing a lot of inserts. It's best to come up with a scheme to make the list grow as you need it (ie add 10 elements each time the list size reaches the allocated size).

Answer 2

There are always other possibilities: for instance an array that you keep reallocing when the space runs out (mind you this isn't very efficient if constant-time element access is not needed).

Answer 3

Linked list is one way. It has O(1) insertion (assuming you're already at the insertion point) and deletion, but O(n) n'th element lookup.

Resizing a dynamically allocated array with malloc is another. It has O(1) n'th element lookup but O(n) insertion (due to having to copy all later elements after the insertion point, and possibly all elements on realloc) and deletion.

If you're really worried about performance for both these operations, I would go with some sort of self-balancing tree structure. You can surely attain O(log n)for lookup, insertion, and deletion. And for all practical purposes if objects are in main memory, log n is bounded by 32 or 64 and O(log n) might as well be O(1).