Thread: Using a linked list globally and File I/O

  1. #1
    Registered User
    Join Date
    Dec 2007
    Posts
    53

    Using a linked list globally and File I/O

    I've spent the whole day reading the book given to us by the University as well as tutorials all over the internet regarding linked lists. I'm not looking for a solution to my assignment, I'm looking for a better understanding in linked lists and a methodology.

    The program we're making allows a person to edit a soldier database, by creating entries, finding and deleting one, printing them, and of course, loading that database on start-up from a file, and saving it back to it on demand. In order to be memory efficient, we need to use dynamic memory allocation, which means we need to keep the memory use down to the most essential as far as the database goes. So when we delete an entry, we must also free up the memory it used.

    It's getting late and I'm getting pretty dizzy and anxious. I still have 2 weeks to find it out, but there's lots of studying to do and I wanted to get the assignment out of the way first, since I enjoy programming.

    So here are the things I want cleared up, anyone who has some time available and could help, I'd respect it.

    1. In order to start pointing .next pointers towards the next entry in the linked list, we need to have a first entry (the "head" as many tutorials call it.) Does that mean that I have to check if it's the first entry during the load from the file or during manual creation of an entry?
    2. How will I be able to safely use the same linked list, the same data, in all the separate functions I write? I'm quite confused on this part.
    3. What's the quickest way to File I/O regarding linked lists? Fixed size arrays/structures are easy, simple fread and fwrite with size of, but how can I go on reading the data off each node? Is it simpler than I'm thinking it is? Just a simple loop?

    For a quick idea, here are the structure declarations. The rest of the code I'm reluctant to post, it's messy, it's incomplete, it's most probably wrong and does nothing right and could crash, only thing is it compiles right.
    Code:
    /* Initialize record structure for each soldier */
    struct record {
    	long int aa;
    	char firstname[20];
    	char lastname[30];
    	char datein[11];
    	char dateout[11];
    	int freedays;
    	int servicedays;
    } soldiers[1];
    
    /* Initialize nodes for linked list */
    struct node {
    	struct record	soldier;
    	struct node*	next;
    };
    I'm following tutorials letter by letter, but my head has started spinning and I'm guessing most of the code I've written will go straight to the trash, especially since I began writing some functions based on just the record structure and not a linked list, and now I'm not sure how to get the data from soldiers to soldier without much fuss.

  2. #2
    Malum in se abachler's Avatar
    Join Date
    Apr 2007
    Posts
    3,195
    You never specified what type of linked list, single or double?

  3. #3
    Registered User
    Join Date
    Dec 2007
    Posts
    53
    You're right, single linked list.

  4. #4
    Malum in se abachler's Avatar
    Join Date
    Apr 2007
    Posts
    3,195
    1. In order to start pointing .next pointers towards the next entry in the linked list, we need to have a first entry (the "head" as many tutorials call it.) Does that mean that I have to check if it's the first entry during the load from the file or during manual creation of an entry?
    When you create the HEAD, its .next entry is set to NULL.
    When you add an object to the list you do set the .next of the head to the new object, and the .next of the new object to the old .next

    2. How will I be able to safely use the same linked list, the same data, in all the separate functions I write? I'm quite confused on this part.
    Generally you write methods/functions that step through the list until they get to the last object, which will have its .next value set to NULL.

    3. What's the quickest way to File I/O regarding linked lists? Fixed size arrays/structures are easy, simple fread and fwrite with size of, but how can I go on reading the data off each node? Is it simpler than I'm thinking it is? Just a simple loop?
    The QUICKEST way is to just write out the list one object at a time until you get to the end of the list, then close the file. This wastes a lot of space on the disk though, as you are also writing out all the data in the .next pointers, which will certainly be invalid when the data is loaded, and so must be handled correctly. There are MUCH BETTER ways of doing it, but they are more involved, both in development time, and in processing time.

    To read the data on each node, just start at the head node, and itereate through each node until you get to the last one. Each iteration you can process the 'current' node.

  5. #5
    Registered User
    Join Date
    Dec 2007
    Posts
    53
    Thanks for the general guidelines. Regarding 2, I meant to ask how can I correctly pass the linked list from main() to each function and back, making sure all changes are reflected and that every function has proper access to the list.

  6. #6
    Malum in se abachler's Avatar
    Join Date
    Apr 2007
    Posts
    3,195
    just pass a pointer to the head object. Since its a single linked list, the function shoudl stop processing when it gets to the last entry, denoted by ->next == NULL

    Code:
    void foo(LINKED_LIST* pList){
     
        do {
            // something
            pList->Stuff = NewStuff;
    
            pList = pList->next;
            } while (pList != NULL);
     
        return;
        }
    if on the other hand you only want to process a single node, just pass the function a pointer to that node.

    Code:
    void foo(LINKED_LIST* pNode){
        // do somethign to pNode
        pNode->Stuff = OtherStuff && MoreStuff;
    
        return;
        }
    Last edited by abachler; 01-03-2008 at 04:09 PM.

  7. #7
    C++まいる!Cをこわせ!
    Join Date
    Oct 2007
    Location
    Inside my computer
    Posts
    24,654
    Quote Originally Posted by Leftos View Post
    Thanks for the general guidelines. Regarding 2, I meant to ask how can I correctly pass the linked list from main() to each function and back, making sure all changes are reflected and that every function has proper access to the list.
    Just pass the point to the node you want to modify. Since it's dynamically allocated, the changes will reflect in all the functions you use it in.
    If you want to create a new node and assign it to a pointer from a function, you can use a pointer-to-pointer (type**).

    Code:
    typedef my_struct
    {
    	/* Data here */
    	struct my_struct* pNext;
    } mystruct;
    
    int main()
    {
    	mystruct* pHead = /* Let's just say it's valid */;
    	AddNewNode(pHead);
    	return 0;
    }
    
    void AddNewNode(mystruct* pNextTo)
    {
    	mystruct* pNew = malloc( sizeof(mystruct) );
    	mystruct* pNext = pNextTo->pNext ? pNextTo->pNext : NULL;
    	pNextTo->pNext = pNew;
    	pNew->pNext = pNext;
    }
    The new node will be inserted into the list and will be visible from main (pHead->pNext).
    Last edited by Elysia; 01-03-2008 at 09:19 PM.
    Quote Originally Posted by Adak View Post
    io.h certainly IS included in some modern compilers. It is no longer part of the standard for C, but it is nevertheless, included in the very latest Pelles C versions.
    Quote Originally Posted by Salem View Post
    You mean it's included as a crutch to help ancient programmers limp along without them having to relearn too much.

    Outside of your DOS world, your header file is meaningless.

  8. #8
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,336
    1. If I interpret your question correctly, then yes; the first node you set up will need to also be the head of the list.

    2. All you need to do is pass around the head pointer. We can get to anywhere in the list just by chasing links from there.

    3. As far as file I/O goes, I would guess that freading and fwriting should work.

  9. #9
    Registered User
    Join Date
    Oct 2001
    Posts
    2,129
    Quote Originally Posted by Elysia View Post
    Just pass the point to the node you want to modify. Since it's dynamically allocated, the changes will reflect in all the functions you use it in.
    More correctly, it's because the variable passed is a pointer, not an actual variable value. It's called pass by reference when you pass an address of a variable (like what you want to do), and it's called pass by value when you just pass a value of whatever you want to pass.

    pass 'a' by value:
    void func1(node a);

    pass 'a' by reference:
    void func2(node *a);

    since malloc returns data with pointers, it is usually dealt with through pointers, but it's still not quite the same thing. You can pass a variable allocated on the stack to a pass-by-reference function by using the address-of operator:

    node a;
    func2(&a);

    As far as printing the linked list out, I would encourage against using fread and fwrite if you are going to be outputting the node en mass.

    You could simply count up all the nodes, output that number, and then output arrays of the data one after the other.

    It may be a little slower, but it's more portable.
    Last edited by robwhit; 01-03-2008 at 05:59 PM.

  10. #10
    C++まいる!Cをこわせ!
    Join Date
    Oct 2007
    Location
    Inside my computer
    Posts
    24,654
    I'd stay away from calling it by reference since that may be confusing. Rather it's more by pointer or address or whatever you want to call it.
    References are used in C++, not C (technically speaking).
    Quote Originally Posted by Adak View Post
    io.h certainly IS included in some modern compilers. It is no longer part of the standard for C, but it is nevertheless, included in the very latest Pelles C versions.
    Quote Originally Posted by Salem View Post
    You mean it's included as a crutch to help ancient programmers limp along without them having to relearn too much.

    Outside of your DOS world, your header file is meaningless.

  11. #11
    Registered User
    Join Date
    Dec 2007
    Posts
    53
    I've had a long night's sleep, printed out the chapter on linked lists from cslibrary.stanford.edu, and gave it a long read. My understanding on linked lists an passing them from a function to the other is now better. As long as you give head by reference from main to any other function, you can push nodes onto it and do whatever else you wish.

    On the same assignment, different question. Why doesn't the following work?

    Code:
    struct record {
    	long int aa;
    	char firstname[20];
    	char lastname[30];
    	char datein[11];
    	char dateout[11];
    	int freedays;
    	int servicedays;
    } soldiers;
    
    ...
    
    	if(fread(soldiers, sizeof soldiers, 1, fp) != 1) {
    			printf("Den htan dynath h eisagwgh twn dedomenwn apo to arxeio.\n");
    			exit(1);
    	};
    It's giving me incompatible type for argument 1 of fread. Do I have to make soldiers into an array by using [1]?

  12. #12
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    You are passing the struct record to fread, you need to pass a pointer to it.

    --
    Mats
    Compilers can produce warnings - make the compiler programmers happy: Use them!
    Please don't PM me for help - and no, I don't do help over instant messengers.

  13. #13
    C++まいる!Cをこわせ!
    Join Date
    Oct 2007
    Location
    Inside my computer
    Posts
    24,654
    Code:
    if(fread(&soldiers, sizeof soldiers, 1, fp) != 1) {
    fread and fwrite takes a pointer to the data.
    Quote Originally Posted by Adak View Post
    io.h certainly IS included in some modern compilers. It is no longer part of the standard for C, but it is nevertheless, included in the very latest Pelles C versions.
    Quote Originally Posted by Salem View Post
    You mean it's included as a crutch to help ancient programmers limp along without them having to relearn too much.

    Outside of your DOS world, your header file is meaningless.

  14. #14
    Registered User
    Join Date
    Dec 2007
    Posts
    53
    So now I know that I need to do this...
    Code:
    void printall (struct node** head)
    ...in order for the printall function to have access to the list. However, if I call printone from within printall and I want printone to have access to the same list as well, how do I declare printone, and how do I pass on head?

  15. #15
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    Code:
    printone(struct node *n)
    perhaps?

    --
    Mats
    Compilers can produce warnings - make the compiler programmers happy: Use them!
    Please don't PM me for help - and no, I don't do help over instant messengers.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. linked list versus array
    By FoodDude in forum C++ Programming
    Replies: 18
    Last Post: 08-22-2005, 10:57 AM