Thread: Help with linked lists/ pointers

  1. #1
    Registered User
    Join Date
    May 2009
    Posts
    7

    Help with linked lists/ pointers

    I am trying to write a simple C program that creates a linked list and then prints out the values stored in the list. I am not sure what part of the code isn't correct but when it prints out the entries it will only print out one entry and it looks to be a memory location instead of the value stored in the node. Also, and this is the part that really throws me off, sometimes when i compile the code i get the error "invalid conversion from 'void*' to 'node*' " on every line that I use malloc and other times it compiles with no errors. Here is the code:

    Code:
    #include <stdio.h>
    #include <stdlib.h>
    
    typedef struct node *nodePtr;
    
    struct node {
      int value;
      nodePtr next;
    };
    
    typedef struct node node;
    
    void createNewNode(nodePtr head, nodePtr newNode);
    void printList(nodePtr head);
    
    int main(int argc, const char * argv[]) {
        nodePtr first = malloc(sizeof(node));
        nodePtr newNode = malloc(sizeof(node));
        int numberOfEntries = 0;
    
        first->next = NULL;
    
        printf("Number of Entries: ");
        scanf("%d", &numberOfEntries);
        printf("\n");
    
        if(numberOfEntries == 1) {
            printf("Enter Value: ");
            scanf("%d", first->value);
            printf("\n");
        } else {
            int i = 0;
            while(i < numberOfEntries) {
                printf("Enter Value: ");
                scanf("%d", first->value);
                printf("\n");
    
                createNewNode(first, newNode);
                i++;
            }
        }
        printList(first);
    
        return 0;
    }
    
    void createNewNode(nodePtr head, nodePtr newNode) {
        newNode->next = head;
        head = newNode;
    }
    
    void printList(nodePtr head) {
        nodePtr current = malloc(sizeof(node));
        current = head;
    
        while(current->next != NULL) {
            printf("Entry: %d\n", current->value);
            current = current->next;
        }
    
        printf("Entry: %d\n", current->value);
    
        free(current);
    }
    If someone could take a look at this and point me to where I've made a mistake I would greatly appreciate it.

  2. #2
    pwning noobs Zlatko's Avatar
    Join Date
    Jun 2009
    Location
    The Great White North
    Posts
    132
    You're passing head to createNewNode by value.

  3. #3
    spurious conceit MK27's Avatar
    Join Date
    Jul 2008
    Location
    segmentation fault
    Posts
    8,300
    You are confusing yourself with this:
    Code:
    typedef struct node *nodePtr;
    
    struct node {
      int value;
      nodePtr next;
    };
    Just use:
    Code:
    typedef struct _node {
      int value;
      struct _node *next;
    } node;
    Now you can properly refer to a node, and a *node.

    All linked list functions should be passed pointers:
    Code:
    void createNewNode(node *head, node *newNode);
    void printList(node *head);
    C programming resources:
    GNU C Function and Macro Index -- glibc reference manual
    The C Book -- nice online learner guide
    Current ISO draft standard
    CCAN -- new CPAN like open source library repository
    3 (different) GNU debugger tutorials: #1 -- #2 -- #3
    cpwiki -- our wiki on sourceforge

  4. #4
    Registered User
    Join Date
    May 2009
    Posts
    7
    I looked at createNewNode and tried changing a couple things, but that only seemed to make it worse. I am not sure that I completely understand what you mean by pass head in by value (I am pretty new to programming). Also, while that I don't doubt that the function is flawed, it still doesn't explain why the code would not work correctly if there is only one element in the list since that function would never be executed.

  5. #5
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,413
    Quote Originally Posted by MK27
    Just use:
    Alternatively, you could shift that later typedef to before the struct definition:
    Code:
    typedef struct node node;
    
    struct node {
      int value;
      node *next;
    };
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  6. #6
    spurious conceit MK27's Avatar
    Join Date
    Jul 2008
    Location
    segmentation fault
    Posts
    8,300
    Quote Originally Posted by anything25 View Post
    Also, while that I don't doubt that the function is flawed, it still doesn't explain why the code would not work correctly if there is only one element in the list since that function would never be executed.
    It is very important that you use one of the forms recommended by either me or laserlight. You need to pass pointers without obfuscating the fact; this will make debugging your program that much easier as well.

    You are not actually passing by value, it just looks that way because you have created a datatype which is a pointer. There is no need for that and it is obviously confusing you *and* the people you are looking to for help.
    C programming resources:
    GNU C Function and Macro Index -- glibc reference manual
    The C Book -- nice online learner guide
    Current ISO draft standard
    CCAN -- new CPAN like open source library repository
    3 (different) GNU debugger tutorials: #1 -- #2 -- #3
    cpwiki -- our wiki on sourceforge

  7. #7
    pwning noobs Zlatko's Avatar
    Join Date
    Jun 2009
    Location
    The Great White North
    Posts
    132
    Quote Originally Posted by anything25 View Post
    I looked at createNewNode and tried changing a couple things, but that only seemed to make it worse. I am not sure that I completely understand what you mean by pass head in by value (I am pretty new to programming). Also, while that I don't doubt that the function is flawed, it still doesn't explain why the code would not work correctly if there is only one element in the list since that function would never be executed.
    OK, there may be a number of issues here, but remember if you have a function that takes an integer
    Code:
    void foo(int i)
    {
         i = i + 1
    }
    int main()
    {
       int i  = 0;
       foo(i);
    }
    and you increment i in the function, the caller will not see the change because i is a copy of what the caller passed in.

    Now you have a pointer called first in main and you're passing it into creatNewNode as head and you want first in main to be changed to point to newNode so you must pass in the address of the variable to be changed.

    The function should be
    Code:
    void createNewNode(nodePtr* head, nodePtr newNode)
    {
       newNode->next = *head;
       *head = newNode;
    }

    May I ask, what development tools are you using?

    Best regards
    Zlatko

  8. #8
    spurious conceit MK27's Avatar
    Join Date
    Jul 2008
    Location
    segmentation fault
    Posts
    8,300
    Quote Originally Posted by Zlatko View Post
    and you increment i in the function, the caller will not see the change because i is a copy of what the caller passed in.
    This is a good explanation of the difference between pass by value/pass by reference *but* Zlatko, look, the OP is passing by reference:

    Code:
    typedef struct node *nodePtr;
    That is the first thing which needs to be fixed tho, since this is not a nice way to program at all.
    C programming resources:
    GNU C Function and Macro Index -- glibc reference manual
    The C Book -- nice online learner guide
    Current ISO draft standard
    CCAN -- new CPAN like open source library repository
    3 (different) GNU debugger tutorials: #1 -- #2 -- #3
    cpwiki -- our wiki on sourceforge

  9. #9
    Registered User
    Join Date
    May 2009
    Posts
    7
    Thanks for all of the replies. I see what you guys mean about the form it is in and have changed the code so that it shouldn't be as confusing. Here is the changed code:
    Code:
    #include <stdio.h>
    #include <stdlib.h>
    
    typedef struct node {
      int value;
      struct node *next;
    } node;
    
    void createNewNode(node *head, node *newNode);
    void printList(node *head);
    
    int main(int argc, const char * argv[]) {
        node *first;
        first = malloc(sizeof(node));
        node *newNode;
        newNode = malloc(sizeof(node));
        int numberOfEntries = 0;
    
        first->next = NULL;
    
        printf("Number of Entries: ");
        scanf("%d", &numberOfEntries);
        printf("\n");
    
        if(numberOfEntries == 1) {
            printf("Enter Value: ");
            scanf("%d", first->value);
            printf("\n");
        } else {
            int i = 0;
            while(i < numberOfEntries) {
                printf("Enter Value: ");
                scanf("%d", first->value);
                printf("\n");
    
                createNewNode(first, newNode);
                i++;
            }
        }
        printList(first);
    
        return 0;
    }
    
    void createNewNode(node *head, node *newNode) {
        newNode->next = head;
        head = newNode;
    }
    
    void printList(node *head) {
        node *current;
        current = malloc(sizeof(node));
        current = head;
    
        while(current->next != NULL) {
            printf("Entry: %d\n", current->value);
            current = current->next;
        }
    
        printf("Entry: %d\n", current->value);
    
        free(current);
    }
    I am still pretty lost with what else is wrong with the code.... Linked lists are confusing the hell out of me lol
    Last edited by anything25; 06-26-2009 at 01:05 PM.

  10. #10
    Registered User
    Join Date
    May 2009
    Posts
    7
    Also, as Ive been playing with the code I've realized that the while loop in the printList function never executes. I think I have that code right so I'm assuming that it is probably due to one of my other errors in the code.

  11. #11
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,336
    Quote Originally Posted by MK27 View Post
    This is a good explanation of the difference between pass by value/pass by reference *but* Zlatko, look, the OP is passing by reference:

    Code:
    typedef struct node *nodePtr;
    That is the first thing which needs to be fixed tho, since this is not a nice way to program at all.
    I think you've lost the plot, MK. No matter what the typedef is, this code:
    Code:
    void createNewNode(nodePtr head, nodePtr newNode) {
        newNode->next = head;
        head = newNode;
    }
    cannot possibly change head in the main function. The fact that it is a pointer is completely irrelevant.

  12. #12
    pwning noobs Zlatko's Avatar
    Join Date
    Jun 2009
    Location
    The Great White North
    Posts
    132
    Code:
    #include <stdio.h>
    #include <stdio.h>
    #include <stdlib.h>
    
    typedef struct node {
      int value;
      struct node *next;
    } node;
    
    void createNewNode(node **head, node *newNode);
    void printList(node *head);
    
    int main(int argc, const char * argv[]) {
        node *first;
        first = (node*)malloc(sizeof(node));
        first->next = NULL; //Change // ALWAYS DO THIS
        node *newNode = NULL;
        //Change newNode = (node*)malloc(sizeof(node));
        int numberOfEntries = 0;
    
        first->next = NULL;
    
        printf("Number of Entries: ");
        scanf("%d", &numberOfEntries);
        printf("\n");
    
        if(numberOfEntries == 1) {
            printf("Enter Value: ");
            scanf("%d", &(first->value));
            printf("\n");
        } else {
            int i = 0;
            while(i < numberOfEntries) {
                printf("Enter Value: ");
                
                int value;
                scanf("%d", &value); // Change 
                if (i == 0) // Change
                {
                    first->value = value;
                }
                else
                {
                    newNode = (node*)malloc(sizeof(node)); //Change
                    newNode->value = value;
                    newNode->next = NULL; // ALWAYS DO THIS
                    createNewNode(&first, newNode); // Change
                }
                printf("\n");
                i++;
            }
        }
        printList(first);
    
        return 0;
    }
    
    void createNewNode(node **head, node *newNode) {
        //newNode->next = head;
        //head = newNode;
        // Changed
        newNode->next = *head;
        *head = newNode;
    }
    
    void printList(node *head) {
        //node *current;
        //current = (node*)malloc(sizeof(node));
        //current = head;
    
        //while(current->next != NULL) {
        //    printf("Entry: %d\n", current->value);
        //    current = current->next;
        //}
    
        //printf("Entry: %d\n", current->value);
    
        //free(current);
    
    
        node* current = head;
        while(current != NULL)
        {
            printf("Entry: %d\n", current->value);
            current = current->next;
        }
    }
    OK, I don't want to be accused of corrupting the youth, but I felt I had to post the entire code to explain it.

    1. You don't need to allocate a newNode at the start of main. You need to allocate it in the while(i<numberOfEntries) loop.

    2. Always set your pointers to NULL in your structs as soon as you do the malloc, otherwise you'll forget.

    3. Scanf into an address scanf("%d", node->value) does not scan into value. It takes node->value and looks at value and treats that as an address. The syntax should be scanf("%d", &(node->value))

    4. On the first time through the loop use the node* first already allocated. This is not how I'd organize the loop, but OK.

    5. When calling createNewNode, you must pass in the address of the first pointer. If you wanted to change an integer in a function and have the change visible to the caller, you would pass in a pointer to the integer. Here you want to change a pointer and have the change visible to the caller so you must pass in a pointer to a pointer.

    6. Watch how node**head is used in createNewNode. Make sure you understand that.

    7. While printing the list, there is no need to allocate new memory. You simply walk through the existing memory.

    Best regards
    Zlatko

  13. #13
    spurious conceit MK27's Avatar
    Join Date
    Jul 2008
    Location
    segmentation fault
    Posts
    8,300
    Here's a little thing that might cause a problem:
    Code:
    scanf("%d", &first->value);
    Again, this is a value vs. reference issue; scanf expects an address reference, so use the &address of operator.

    It's not that the printList while loop isn't executing, it's that createNewNode doesn't work. Also, why do you have a malloc call in printList()? Malloc allocates memory for a node -- that is part of what is missing in createNewNode.

    You do not need to create more than one *node in main(), namely "head", and malloc it there. No matter what, for the first entry, use that one. For the subsequent ones, you pass the head to createNewNode, which malloc's a new node and set's the last node's next to that:
    Code:
    void createNewNode(node *head, int val) {
    	node *new = malloc(sizeof(node)), *cur=head;
    	new->value = val;
    	while (cur->next) cur=cur->next;
    	cur->next=new;
    }
    So now your main should look something like this:
    Code:
       node *first = malloc(sizeof(node));
        int numberOfEntries = 0, value;
    	int i = 0;
    
        printf("Number of Entries: ");
        scanf("%d", &numberOfEntries);
        printf("\n");
    
    	printf("Enter Value: ");
    	scanf("%d", &first->value);
    	printf("\n");
            while(i < numberOfEntries-1) {
                printf("Enter Value: ");
                scanf("%d", &value);
                printf("\n");
    
                createNewNode(first,value);
                i++;
            }
    Zlatko, becasue of issue #5 above, uses a pointer to a pointer (**) to accomplish the same thing, you may find my method somewhat simpler and easy to understand (or it may be the other way around).

    @tabstop: my point was the unorthodox typedef'ing is the first mistake that needs correcting. Neither I nor you nor anyone else will want to correct the OP while maintaining that.
    Last edited by MK27; 06-26-2009 at 01:38 PM.
    C programming resources:
    GNU C Function and Macro Index -- glibc reference manual
    The C Book -- nice online learner guide
    Current ISO draft standard
    CCAN -- new CPAN like open source library repository
    3 (different) GNU debugger tutorials: #1 -- #2 -- #3
    cpwiki -- our wiki on sourceforge

  14. #14
    pwning noobs Zlatko's Avatar
    Join Date
    Jun 2009
    Location
    The Great White North
    Posts
    132
    Keep at it until you understand it.
    Step through it with a debugger.
    Ask questions
    We want you to pass your course!


    EDIT:
    IMHO there was nothing wrong with your originaly typedef-ing
    Last edited by Zlatko; 06-26-2009 at 01:36 PM.

  15. #15
    Registered User
    Join Date
    May 2009
    Posts
    7
    Thank you everyone so much for the help! I've got the code working and also understand pointers a whole lot more then when I started. Thanks again!

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Doubly linked lists
    By mohanlon in forum C Programming
    Replies: 8
    Last Post: 12-08-2010, 01:01 AM
  2. Linked Lists
    By wvu2005 in forum C Programming
    Replies: 12
    Last Post: 10-06-2005, 11:36 AM
  3. Linked Lists 101
    By The Brain in forum C++ Programming
    Replies: 5
    Last Post: 07-24-2004, 04:32 PM
  4. eof in fstream & singly linked lists
    By mazo in forum C++ Programming
    Replies: 3
    Last Post: 06-03-2002, 09:50 AM
  5. Linked lists and file i/o, and some other stuff
    By ninja in forum C++ Programming
    Replies: 9
    Last Post: 05-19-2002, 07:15 PM