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

    Join Date
    Jul 2013
    Posts
    109
    Rep Power
    2

    While loop will never be entered ???


    The question is really not long:

    I started reading about Linked Lists, and they show an example code. It includes a while loop which has a test condition, and it seems to me it will never be executed:
    Code:
    #include <stdio.h>
    #include <stdlib.h>
    
    struct node {
      int x;
      struct node *next;
    };
    
    int main()
    {
        struct node *root; 
          
        struct node *conductor;  
    
        root = malloc( sizeof(struct node) );  
        root->next = 0;   
        root->x = 12;
        conductor = root; /* Conductor now points to the same address root does ??? */
        if ( conductor != 0 ) {
            while ( conductor->next != 0)
            {
                conductor = conductor->next;
            }
        }
        
        conductor->next = malloc( sizeof(struct node) );  
    
        conductor = conductor->next; 
    
        if ( conductor == 0 )
        {
            printf( "Out of memory" );
            return 0;
        }
       
        conductor->next = 0;         
        conductor->x = 42;
    
        return 0;
    }
    The while loop:
    Code:
            while ( conductor->next != 0)
            {
                conductor = conductor->next;
            }
    But "conductor->next" is always NULL because they set "next" to be NULL THROUGH "root":
    Code:
    root->next = 0;
    How will the while loop be entered ?
  2. #2
  3. Come play with me!
    Devshed Supreme Being (6500+ posts)

    Join Date
    Mar 2007
    Location
    Washington, USA
    Posts
    13,749
    Rep Power
    9397
    Originally Posted by C learner
    How will the while loop be entered ?
    It won't, and for the reason you pointed out.

    That code is very poorly written. Where are you getting it from?
  4. #3
  5. No Profile Picture
    Contributing User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Jul 2013
    Posts
    109
    Rep Power
    2
    it's from: http://www.cprogramming.com/tutorial/c/lesson15.html

    I was just looking for further info since my book wasn't enough.

    Btw, what are List Nodes good for?? they are just structs aren't they ?
  6. #4
  7. Contributing User
    Devshed Supreme Being (6500+ posts)

    Join Date
    Jan 2003
    Location
    USA
    Posts
    7,089
    Rep Power
    2222
    You are correct that they should have used NULL instead of 0.

    And you are also correct that in this particular program you would never enter that while loop.

    Now, that kind of a loop does serve as an example of how to traverse down a linked list. You could use it in other code to do something useful. It's just not in a very good example program.

    Actually, what the program does is to find the end of the list and then add a new node at the end of the list. Please note how your traversal pointer (AKA "iterator"), conductor, is always pointing to the current node while any testing of the next node (in this case whether it exists) is done through the current node. That may not make much sense right now, but it will later. There are even times when you may want to be looking two nodes ahead (eg, conductor->next->next).

    In most linked-list programs, you will create functions that will append a new node at the end of the list, insert a new node in the middle of the list, delete a node, find a node and display it or modify its contents, display all the contents of the list, etc.

    So this was a very simple example to demonstrate code to do an append. In an actual append function, the list could already contain more than just one node, in which case that while loop would do something useful.

    Please note that a linked list is where you really have to be very careful to never drop a pointer. And when you get to the point of writing insert and delete functions, don't hestitate to use pencil and paper to sketch the linked list and how you need to handle the pointers for the operation (that "look-ahead" technique I mentioned above would come into play).
  8. #5
  9. Contributing User
    Devshed Supreme Being (6500+ posts)

    Join Date
    Jan 2003
    Location
    USA
    Posts
    7,089
    Rep Power
    2222
    Originally Posted by C_Learner
    Btw, what are List Nodes good for?? they are just structs aren't they ?
    Linked lists are a data structure. They are also a rite of passage for programmers; every one of us had to work with linked lists in school.

    Linked lists are especially useful when you are working with unknown quantities of data. You could almost think of them as being like arrays, except you can do so much more with them.

    You need to know the maximum size of an array when you write the code and because you have to create huge arrays to cover all possible situations you end up wasting a lot of memory, but with linked lists you can handle practically any amount of data without any waste, since you only allocate (ie malloc) as much memory as you need and then can free it up as soon as it's no longer needed.

    If you store the elements of an array in order, then when you insert a new element in its proper place you have to move all the elements above it over one position to do that. Similarly, when you delete an element, you have to move all the elements above it over by one position. That can become very expensive time-wise if there's a lot of data. With a linked list, you merely find where to insert the new node and change a couple pointers. Similarly, to delete a node from a list you merely assign a temporary pointer to it (to keep from dropping it), change a pointer or two to remove it from the list, and then use that temporary pointer to free it.

    There are several other forms of data structures, such as queues, stacks, trees, and graphs. Wikipedia has a list of data structures here: http://en.wikipedia.org/wiki/List_of_data_structures. At my university, we spent an entire semester on the subject and that was just an introduction.

    Originally Posted by Linus Torvalds
    I will, in fact, claim that the difference between a bad programmer and a good one is whether he considers his code or his data structures more important. Bad programmers worry about the code. Good programmers worry about data structures and their relationships.
    BTW, don't feel bad about not knowing what they're good for. When we were first taught about pointers at the end of the semester, I immediately understood what they were and what they did since I had already learned assembly, but I could not understand what they could possibly be good for. Then the next semester I was using them everywhere.
  10. #6
  11. No Profile Picture
    Contributing User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Jul 2013
    Posts
    109
    Rep Power
    2
    Wow, i think it's the best explanation i'll ever see :)
    Thank you, i caught on.

    I think if i see now its practical uses in codes i will understand it completely.

    >> lol i did feel a bit bad at first for not catching the idea, but because it's so efficient to dynamically allocate structs, i guess it's pretty intuitive !

    Although, what if i had a list of nodes in which i didn't have to start from the beginning in order to SEARCH FOR ANY member of the list? Is it possible to create pointers to nodes (from the outisde) so you can save the time of going thru all of them while searching ?

    Because that's one of the disadvantages i've read about.
  12. #7
  13. Contributing User
    Devshed Supreme Being (6500+ posts)

    Join Date
    Jan 2003
    Location
    USA
    Posts
    7,089
    Rep Power
    2222
    Oh, you can create just about any kind of data structure that you'd want to. So, yes, you can do what you describe; in fact, I've been toying with the idea myself.

    But first, you should learn the classic data structures, in part because in the algorithms class you'll learn various search algorithms and how to analyze their efficiency or lack of efficiency as measured by the O() function (orders of magnitude). This knowledge will also relate to your use of the STL (Standard Template Library) in C++, which implements lists and queues and stacks and hash tables for you.

    For example, you are right that in a classic list you have to search through serially, such that on the average you'd have to search half-way through before you find what you're looking for; hence it would be O(n/2). Linear searches are simple to implement, but they can start to become expensive when the number of items (n) becames large -- think in terms of computers being used to search through mountains of data.

    If the list is sorted, then you can do something like a binary search:
    1. Access the mid-point, bisecting the range of values into an upper and lower sub-range.
    2. if the search value is less than the mid-point value, then search the lower sub-range, else seach the upper sub-range.
    3. Etc until you find the item or are positioned where it should be (ie, the sub-range is of length zero).
    That search should be to the order of log2(n). Harder to implement, but faster than linear search for large values of n.

    But the binary method suffers from two problems: 1) you need to be able to access each item randomly and 2) the list must be sorted. You cannot access elements in a classic list randomly, nor in an STL list. And sorting an array, which you can access randomly, can get to be expensive, especially if you have to resort it every time an item is added.

    So what I've been thinking of is a variation on what was done by dBase III (http://en.wikipedia.org/wiki/Dbase), which used to be a very popular database application on CP/M and especially on MS-DOS. Your data records would be stored in a .dbf file ("data base file"?) with fixed-length records. When you added a record, it would be placed either at the end of the table or in the first deleted record's place (you deleted a record by marking it as deleted, then periodically you could use the PACK command to physically remove them and move everything else up). You could sort your data records on any of the fields, but you never actually sorted the .dbf file. Instead, your sort command would create an index file (.ndx) that provided links to each record with those links being in sorted order. Creating that index file would be much less expensive time-wise than actually sorting the dbf file, especially since the earlier systems were floppy-based (hard drives didn't start to become economical until the mid-1980's; even the first MacIntosh computers were floppy-based, only they had really cool Star Trek-like 3.5" diskettes); file operations on floppies could be quite slow.

    So then, you could have your list of data nodes and then create other lists that would point to selected data nodes. One thought I had in implementing a naval wargame (Harpoon) was for the system to maintain radar track records for all units and then each player's ship would have its own radar track record lists that point to the system's records.

    To implement binary search on a linked list, you could create a sort list much like dBase's .ndx files. Since they would still be linked lists, that would still not support a binary search, but you could create a tree structure in which the nodes contain arrays of pointers to the sorted list's nodes -- or you could eliminate the middleman and do the sorting with the arrays. Each tree node would have up to any number of child nodes and each terminal node would know what range of indices its array of pointers represent. When you'd add or delete elements in the linked list, you would then adjust your search tree accordingly.

    OK, I was just making that up as I went, but you can see the process at work. Now let's try a simpler approach: a binary tree. Each node has two children, a less-than and a greater-than. And the terminal nodes (no children, also called "leaves") would point to a data node. When you insert a new node in the data list you can also add the link to it in the sort tree without having to reorganize the tree. But after a while the tree can become unbalanced, so you could periodically rebalance it. The order of magnitude of a search through a balanced binary tree is again log2(n).

    You can create almost any data structure that you can dream of. And you will study several different search algorithms later on in class, though usually in your 3rd or 4th year of a 4-year undergraduate program.

    It can be fun playing around with some of these ideas. Sorry I got carried away there.

    And don't underestimate the value of sketching your ideas out with pencil and paper.
  14. #8
  15. No Profile Picture
    Contributing User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Jul 2013
    Posts
    109
    Rep Power
    2
    This sounds really interesting. I hope i'll be able to implement such ideas when i study software+hardware.

    Pointing out the problems each method has explains me REALLY well why we use one method over another, and what each method exists for.

    In The C programming 2nd edition, they actually wrote a small program, which searches just like you described- division by 2, searching the middle then going left/right. I should probably memorize those things, looks very useful.

    I've seen the binary tree in that book also, and they too use the term "children". Just haven't go to it yet, but i've read a few lines about it.

    Sketching the ideas really is useful. When i got to functions, i found a better way than drawing a long chart of the program. I just write the name of the function inside main (before i wrote the function), then another and another function, in the order i wish it to be. I GIVE THE FUNCTIONS NAMES THAT TELL ME EXACTLY WHAT THEY DO, and i can read 'main' as if it were a message telling what the program does. Really simplifies things up. And i save the drawing for the smaller parts of the program.
  16. #9
  17. Contributing User
    Devshed Supreme Being (6500+ posts)

    Join Date
    Jan 2003
    Location
    USA
    Posts
    7,089
    Rep Power
    2222
    While I've been spared the experience, an older co-worker a few decades ago had done some COBOL programming. He said that most COBOL programs do the same thing, open and read some files and print out a report, so once you've written your first program then you have written all your programs, just take that first program and change a few details.

    Similarly in school, since most student programs would basically have the same structure, my main routine (this was Pascal) would have three procedure calls: Init, Process, and Report.

    So then, yes, use meaningful names. Also take a big task and break it down into smaller and smaller sub-tasks, which is called "divide and conquer".

    For a practical every-day example of a tree structure, look at the file directory structure of your C: drive. \ is the root directory and it has sub-directories as its children. Each subdirectory has one and only one parent directory (which, of course, root doesn't) and that parent directory is called ".." (two periods). Each subdirectory can have any number of children, each with a unique name within that subdirectory. And each subdirectory has a name for itself, "." (one period).

    Time for hustle class.
  18. #10
  19. No Profile Picture
    Contributing User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Jul 2013
    Posts
    109
    Rep Power
    2
    I've recently wrote a program with a few functions. One of them i had to break into 2 smaller ones, but before i realised that it's better to "divide and conquer" i spent days on building this "Rome" untill it collapsed lol.

IMN logo majestic logo threadwatch logo seochat tools logo