Well it depends on your patterns of access. If you remove nodes a lot then you might end up moving large blocks of indices around. Unless you use a sentinel value, but then before you know it, you are implementing a hash table.

To reduce memory allocation time penalty you can use a memory pool.

However if memory size is a problem (maybe another 2 pointers per element) or if you do mostly adds and random access of elements an array could be a good choice.