#1
  1. No Profile Picture
    Registered User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Sep 2013
    Posts
    22
    Rep Power
    0

    How to build linked list using realloc


    hello to all

    i cant build a linked list that get string form the user and store that in the memory,I need to use the dinamic realloc for that.

    i build reguler list but i need also list that build by realloc and dont have limit .

    can some one help me to build this list


    best regards
    tamir
  2. #2
  3. Contributing User
    Devshed Supreme Being (6500+ posts)

    Join Date
    Jan 2003
    Location
    USA
    Posts
    7,156
    Rep Power
    2222
    I do not see where there would be any use for realloc in building and maintaining the linked list itself. The only use for it that I can imagine would be for updating a char* field within an existing node in the list (eg, you had malloc'd for a name field and then later you come back and change that name, so you'd use realloc to allocate the memory for the new name data).

    Could you please provide us with much more specific requirements?
  4. #3
  5. No Profile Picture
    Registered User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Sep 2013
    Posts
    22
    Rep Power
    0
    i need to build a program that get 1 char or list of char (string).

    i will give the user 2 choice:
    first choice is get the char or the list of char and implement on link list.

    second choice is get the char or the list of char and implement by using the Library of realloc

    i build a link list and i use the malloc
    but i dont know how to build linked list using realloc?
  6. #4
  7. Contributing User
    Devshed Supreme Being (6500+ posts)

    Join Date
    Jan 2003
    Location
    USA
    Posts
    7,156
    Rep Power
    2222
    I still don't understand just what you want to do and how that would involve realloc. That is why I asked you to be more specific. Part of what I had in mind was a declaration of a node structure.

    When you malloc, you tell it the size to allocate and it returns a pointer to you. When you call realloc, you pass it a pointer (which has a particular size associated with it) and you tell it to change that to a different size and to copy the existing data to the new size, etc. I've mainly seen realloc being applied to an array of elements in order to increase the size of the array to hold more elements. What I very much doubt is whether it could be used to change the size of a struct without messing up the fields within that struct, considering that realloc has no way of knowing anything about a struct's fields.

    So, when you build a linked list, you will malloc each node that goes into that list. After that, to change the list you would either malloc new nodes or free old nodes that you want to delete. But you would not change the size of the nodes, which is the only reason I can see for using realloc to build a linked list. Therefore, I cannot see any reason to use realloc to build a linked list. Oh, I guess it might be possible to misuse realloc to behave like malloc, but that seems like a terrible waste of resources -- kind of like choosing a two-ton truck over a passenger car for the job of transporting a single letter to the post office; it can be done, but why insist on doing it that way?

    As I already said:
    Originally Posted by dwise1_aol
    The only use for it that I can imagine would be for updating a char* field within an existing node in the list (eg, you had malloc'd for a name field and then later you come back and change that name, so you'd use realloc to allocate the memory for the new name data).
    Which is why I was hoping for an actual node struct declaration.

    Let us assume something like this:
    Code:
    struct node
    {
        char *str;
        int  *nums;
        struct node *next;
    };
    Now, if all you are doing is to take whatever size string that the user inputs and add that to the list, then you would still use malloc to do that instead of realloc; using realloc would still be over-kill in this case.

    Yet again, as I've already said, you would only want to use realloc if you were to come back to an existing node in the list and want to change the string, str. That is the only use for realloc that I can see.

    In declaration, I allowed for a different kind of situation than what you appear to be presenting. In this new problem, you have a string, str, that is the name of somebody or something; that would be what you would search on to find the node that you want to change. That person or thing as a list of numbers associated with it in the nums field. As you read in the data, new numbers will be read in to be added to a particular person's list of numbers. In that situation, you would use realloc to change the size of the nums array so that you can add in more numbers.

    So to your basic question: "but i dont know how to build linked list using realloc?"

    My basic answer is: "You don't want to. You don't have any reason to ever need to."

    If you truly feel that you do indeed need to use realloc to build your linked list, then convince us of that! Explain to us exactly why you would need to use realloc. Exactly why malloc would not work instead.
  8. #5
  9. No Profile Picture
    Registered User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Sep 2013
    Posts
    22
    Rep Power
    0
    thanks for your anser

    what i need help is to build a link list that dont use dinamic like realloc or malloc

    the user have choice to enter a list by using dinamic (realloc and malloc) or basic link list that dont use dinamic like realloc and malloc.

    i build link list that use dinamic (malloc) but i dont know how to build link list that dont use dinamic

    hope now i exsplan what i need help
  10. #6
  11. Contributing User
    Devshed Supreme Being (6500+ posts)

    Join Date
    Jan 2003
    Location
    USA
    Posts
    7,156
    Rep Power
    2222
    Your requirements still do not make any sense.

    If you can't use dynamic allocation, then you must use static. Frankly, I don't see any use for a linked list without dynamic allocation, because static allocation defeats the basic purpose of a linked list, which is to accommodate practically any number of data items.

    Basically, with static allocation you just simply declare an array that is large enough to handle the maximum number of items that you expect. And if each item could contain a string, then that string would also need to be statically declared as a char array of some arbitrary maximum length. Of course, that will lead to a lot of wasted space.

    A word of warning: if you declare that arbitrarily large array locally within main or any other function, then you will blow the stack and your program will crash. Recall that C defines a few different classifications of storage, the principal ones being auto and static. auto and static variables are stored in two very different types of memory. Local variables are of the auto type and are stored on the stack, whereas global variables are static and are stored in read-write memory. The stack is much smaller than static memory, so it is unwise to store extremely large data structures there. BTW, dynamic allocation with malloc uses another type of memory called the heap, but since you are arbitrarily restricting yourself from dynamic allocation then you cannot use the heap.

    If you really need to simulate a linked list using static arrays, then instead of pointers you would use array indices -- I've seen this simulation done in an old BASIC program. You could have an index array which contains the index of the next data item. Of course, you would need to have initially set up a free_list which links up all the data array elements that haven't been used yet, so that when you need a new node you just remove its reference from the free list and append it to the simulated list that you are building.

    A variation of that would be to keep the struct with its field pointing to the next item in the list, only that next field would contain the next item's array index. If you use this variation, then you will only need one gigantic data array and can eliminate the two gigantic index arrays for the linked list and the free list. Initialize all the elements of the data array so that each one's next field refers to the next array element. Then to start off, you point the list's head "pointer" to "NULL" (indicating that it's not pointing to anything and hence the list is empty) and the free list "pointer" to the first array element and instantly the entire array is on the free list.

    Another variation would be to still use pointers instead of array indices. Though to get those pointers you would have to use the address operator (&) on each element in the data array and store that in the free list.

    But that's an awful lot of trouble to have to go through when you could just simply use a regular old linked list.
    Last edited by dwise1_aol; October 17th, 2013 at 10:50 AM.

IMN logo majestic logo threadwatch logo seochat tools logo