Help with linked lists/ pointers

anything25 · 06-26-2009, 12:04 PM

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.

Zlatko · 06-26-2009, 12:14 PM

You're passing head to createNewNode by value.

MK27 · 06-26-2009, 12:26 PM

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);

anything25 · 06-26-2009, 12:28 PM

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.

**laserlight** · 06-26-2009, 12:28 PM

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;
};

MK27 · 06-26-2009, 12:38 PM

Quote:

Originally Posted by anything25

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.

Zlatko · 06-26-2009, 12:38 PM

Quote:

Originally Posted by anything25

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

MK27 · 06-26-2009, 12:42 PM

Quote:

Originally Posted by Zlatko

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.

anything25 · 06-26-2009, 12:49 PM

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

anything25 · 06-26-2009, 12:57 PM

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.

tabstop · 06-26-2009, 01:08 PM

Quote:

Originally Posted by MK27

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.

Zlatko · 06-26-2009, 01:29 PM

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

MK27 · 06-26-2009, 01:31 PM

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.

Zlatko · 06-26-2009, 01:32 PM

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

anything25 · 06-26-2009, 02:41 PM

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!

06-26-2009, 12:14 PM	#2
Zlatko pwning noobs Join Date: Jun 2009 Location: The Great White North Posts: 125	You're passing head to createNewNode by value. __________________ Sun Certified Java Programmer / Developer IEEE CSDP
Zlatko is offline

06-26-2009, 12:26 PM	#3
MK27 subminimalist Join Date: Jul 2008 Location: NYC Posts: 3,945	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); __________________ Accuracy and integrity mean nothing if you don't make it past the censors...PYTHAGORAS
MK27 is online now

06-26-2009, 12:28 PM	#4
anything25 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.
anything25 is offline

06-26-2009, 12:57 PM	#10
anything25 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.
anything25 is offline

06-26-2009, 01:31 PM	#13
MK27 subminimalist Join Date: Jul 2008 Location: NYC Posts: 3,945	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. __________________ Accuracy and integrity mean nothing if you don't make it past the censors...*PYTHAGORAS Last edited by MK27; 06-26-2009 at 01:38 PM.
MK27 is online now

06-26-2009, 01:32 PM	#14
Zlatko pwning noobs Join Date: Jun 2009 Location: The Great White North Posts: 125	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 __________________ Sun Certified Java Programmer / Developer IEEE CSDP Last edited by Zlatko; 06-26-2009 at 01:36 PM.
Zlatko is offline

06-26-2009, 02:41 PM	#15
anything25 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!
anything25 is offline

Thread Tools
Show Printable Version Email this Page
Display Modes
Linear Mode Switch to Hybrid Mode Switch to Threaded Mode

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
Doubly linked lists	mohanlon	C Programming	7	06-27-2009 07:45 PM
Linked Lists	wvu2005	C Programming	12	10-06-2005 11:36 AM
Linked Lists 101	The Brain	C++ Programming	5	07-24-2004 04:32 PM
eof in fstream & singly linked lists	mazo	C++ Programming	3	06-03-2002 09:50 AM
Linked lists and file i/o, and some other stuff	ninja	C++ Programming	9	05-19-2002 07:15 PM