Linked list versus malloc and realloc.

This is a discussion on Linked list versus malloc and realloc. within the C Programming forums, part of the General Programming Boards category; I have a question reguarding the use of a linked list of structures versus an array of structures. I would ...

  1. #1
    Registered User Bajanine's Avatar
    Join Date
    Dec 2001
    Location
    The most peaks over 10,000 feet!
    Posts
    396

    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.
    Favorite Quote:

    >For that reason someone invented C++.
    BLASPHEMY! Begone from my C board, you foul lover of objects, before the gods of C cast you into the void as punishment for your weakness! There is no penance for saying such things in my presence. You are henceforth excommunicated. Never return to this house, filthy heretic!



  2. #2
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    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.
    Hope is the first step on the road to disappointment.

  3. #3
    Registered User Bajanine's Avatar
    Join Date
    Dec 2001
    Location
    The most peaks over 10,000 feet!
    Posts
    396
    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!
    Favorite Quote:

    >For that reason someone invented C++.
    BLASPHEMY! Begone from my C board, you foul lover of objects, before the gods of C cast you into the void as punishment for your weakness! There is no penance for saying such things in my presence. You are henceforth excommunicated. Never return to this house, filthy heretic!



Popular pages Recent additions subscribe to a feed

Similar Threads

  1. malloc, realloc..wat on earth!
    By zesty in forum C Programming
    Replies: 3
    Last Post: 12-21-2007, 12:42 PM
  2. malloc and realloc
    By jayfriend in forum C Programming
    Replies: 4
    Last Post: 01-05-2007, 01:25 PM
  3. malloc, realloc
    By figo2476 in forum C Programming
    Replies: 3
    Last Post: 04-28-2006, 10:11 PM
  4. malloc and realloc
    By odysseus.lost in forum C Programming
    Replies: 3
    Last Post: 05-27-2005, 08:44 AM
  5. Need help on malloc and realloc
    By YevGenius in forum C Programming
    Replies: 8
    Last Post: 03-06-2004, 12:55 AM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21