Thread: Linked list versus malloc and realloc.

I have a question reguarding the use of a linked list of structures versus an array of structures. I would think that being able to use malloc and realloc as needed would be easier.

What am I missing? Where should each method be used?

Let us say using a linked list that you wanted to get some data from the user:

1. Create node.
2. Check the user supplied data.
3. Store data in node.
4. Goto 1.

Using an array to get data from user:

1. malloc or calloc some memory.
2. Check the user supplied data.
3. Store the data in the array.
4. If out of malloc’d memory, realloc.

The overhead of you calling realloc compared to me just mallocing another node and setting up a few pointers is much more costly. Let's say you have 100 elements. Now in addition to the 100 you have, you have to allocate 101. Or maybe you just double it.

Now you have: 100 + 200 = 300, then you copy over the first 100, and free then free it. Let's compare that to a linked list:

100 elements in the list.
malloc one more. done.

Now 100 elements is fairly small. What if you have 1000? Or 10000? You have to at the very minimum, for every single realloc call have at least twice the space available that you actually need. One for the origional amount to be reallocated, and another + whatever else new space you want, just to add a single new one.


Quzah.

Thanks quzah for pointing that out for me. Sometimes it's hard to see the problem while programming simple applications like I do.

Thanks again!