problem with pointers in linked list

[django]

Hello,

I am goofing around with pointers and structures. I want to achieve the following:
(1) define a linked list with a structure (numberRecord)
(2) write a function that fills a linked list with some sample records by going thourgh a loop (fillList)
(3) count the number of elements in the linked list
(4) print the number of elements

I am now so far that the fillList function works well, but I do not succeed in handing over the filled linked list to a pointer in the main(). If I run the code below, the countList goes into an eternal loop caused by the fact fact that the list is not terminated with a record that points to NULL.

What am I doing wrong?

-------------------------------------------------------------

#include <stdio.h>
#include <stdlib.h>

typedef struct numberRecord numberRecord;

//linked list
struct numberRecord {
   int number;
   struct numberRecord *next;
};

//count #records in linked list
int countList(struct numberRecord *record) {

   struct numberRecord *index = record;
   int i = 0;

   if (record == NULL)
      return i;

   while (index->next != NULL) {
      ++i;
      index = index->next;
   }

   return i + 1;
}

//print linked list
void printList (struct numberRecord *record) {

   struct numberRecord *index = record;

   if (index == NULL)
      printf("List is leeg \n");

   while (index != NULL) { 

      printf("%i \n", index->number);
      index = index->next;
   }
}

//fill the linked list with some sample records
void fillList(numberRecord *record) {

   numberRecord *first, *prev, *new, *buffer;

   //as soon as you add more records you get an memory error, static 
   //construction, not good
   new = (numberRecord *)malloc(100 * sizeof(numberRecord));
   new->number = 0;
   new->next = NULL;

   //new = &p;
   first = new;
   prev = new;
   buffer = new;

   int i;

   for (i = 1; i < 11; i++) {

      new++;
      new->number = i;
      new->next = NULL;
      prev->next = new;
      prev = prev->next;
   }
}


void main() {

   numberRecord *list;
   list = (numberRecord *)malloc(sizeof(numberRecord));
   fillList(list);
   printf("ListCount: %i /n", countList(list));
}

[quzah]

You can make filList return a pointer, and return the list, or you can pass a pointer to your list, and fill that way. Remember that everything is a value pass in C. If you want to change the value an int holds, you need a pointer to an int. If you want to change the value a pointer to X holds, then you need a pointer to a pointer to X.

Also - void main() should be int main( void ) and should return an int at the end of the function (typically return 0; though EXIT_SUCCESS and EXIT_FAILURE are allowed as well).


Quzah.

[grumpy]

Your main function allocates a list and passes it to fillList() That list is uninitialised, so any usage of it (unless you initialise it) gives undefined behaviour.

fillList() creates a complete new list that has no relationship to the one in main() (or the one passed to it as an argument).

So main() is attempting to count the number of elements in an uninitialised list, and giving undefined behaviour. The behaviour you are seeing is consistent with that (any other behaviour would also be valid though).


On other things:

1) main() returns int, not void. If anyone (including a text book) claims otherwise, don't believe them.

2) In C, you should not need to convert the return value from malloc(). It is only in C++ that you would need to convert the return from malloc(), but in C++, new is a keyword so your code would not compile as C++.

[django]

Ok, very helpful.
As you say, this list in my main is not initialized, however, I intended to do this by:

...
   list = (numberRecord *)malloc(sizeof(numberRecord));
...

How should I initialize this list correctly?

PS Is there a clever way to get a linecount in when posting code to this forum?

[quzah]

ptr = malloc( howmany * sizeof *ptr );

You just don't need the cast you have to the right of the equal sign.

As to line count, the forum doesn't have anything that will number lines, and if it did, it would just be irritating for when people try to copy-paste to compile stuff.


Quzah.

[grumpy]

Ok, very helpful.
How should I initialize this list correctly?

After you have malloc'ed it, set the members of the struct (or structs, if you allocate more than one in the malloc call) to meaningful values.

[django]

Ok, getting there, one to go...

...
fillList() creates a complete new list that has no relationship to the one in main() (or the one passed to it as an argument).
...

I do not succeed in this. I have tried to fix this in the function fillList by adding a line

...
record = first;
...

This does not work however. For clarity I have posted the complete program. When I run it, it prints a list with one record (the one struct added in the main()).

#include <stdio.h>
#include <stdlib.h>

typedef struct numberRecord numberRecord;

//linked list
struct numberRecord {
	int number;
	struct numberRecord *next;
};

//count #records in linked list
int countList(struct numberRecord *record) {

   	struct numberRecord *index = record;
	int i = 0;

	if (record == NULL)
		return i;

	while (index->next != NULL) {
		++i;
		index = index->next;
	}

	return i + 1;
}

//print linked list
void printList (struct numberRecord *record) {

   	struct numberRecord *index = record;

	if (index == NULL)
		printf("List is leeg \n");

	while (index != NULL) {

		printf("%i \n", index->number);
		index = index->next;
	}

}

//fill the linked list with some sample records
void fillList(numberRecord *record) {

	numberRecord *first, *prev, *new, *buffer;

//as soon as you add more records you get an memory error, static construction
	new = (numberRecord *)malloc(100 * sizeof(numberRecord));
	new->number = 0;
	new->next = NULL;

	//new = &p;
	first = new;
	prev = new;
	buffer = new;

	int i;

	for (i = 1; i < 11; i++) {

		new++;

		new->number = i;
		new->next = NULL;

		prev->next = new;
		prev = prev->next;
	}

	record = first;
}


void main() {

	numberRecord *list;
	list = malloc(sizeof(numberRecord));
	list->number = 1;
	list->next = NULL;

	fillList(list);
	printf("ListCount: %i \n", countList(list));
	printList(list);
}

[grumpy]

Any change to the value of arguments of a function are local to the function. The effect of the line "record = first" in fillList() does not change the value of list in main().

fillList() needs to accept an argument of type pointer to pointer to numberRecord. That change will trigger other error messages when you compile your code. Fix those and (assuming no other errors in your code) it should work.

Also main() returns int not void

[django]

Thanks grumpy I got it working. The signature of the main is also adapted . For those who care here is my solution:

I have one question though:

In the main I allocate memory to the pointer to a pointer. I allocate the space of a struct and assign it to p. Is this correct or does it just happen to work out right. It seems a bit illogical since p is a pointer to a pointer and not a pointer to.

    #include <stdio.h>
    #include <stdlib.h>

    typedef struct numberRecord numberRecord;

    //linked list
    struct numberRecord {
                 int number;
	        struct numberRecord *next;
    };

    //count #records in linked list
    int countList(struct numberRecord *record) {

             struct numberRecord *index = record;
	    int i = 0;

	    if (record == NULL)
		    return i;

	    while (index->next != NULL) {
		    ++i;
		    index = index->next;
	    }

	    return i + 1;
    }

    //print linked list
    void printList (struct numberRecord *record) {

   	    struct numberRecord *index = record;

	    if (index == NULL)
		    printf("List is empty \n");

	    while (index != NULL) {

		    printf("%i \n", index->number);
		    index = index->next;
	    }

    }

    //fill the linked list with some sample records
    void fillList(numberRecord **list) {

	    numberRecord *firstRec, *prevRec, *newRec;

	    int i;

	    for (i = 1; i < 110; i++) {

		    newRec = malloc(sizeof(numberRecord));
		    newRec->number = i;
		    newRec->next = NULL;

			//initialize firstRec and prevRec with newRec, firstRec remains head
			if (i == 1) {
				firstRec = newRec;
				prevRec = newRec;
			}
		    prevRec->next = newRec;
		    prevRec = prevRec->next;
	    }


		*list = firstRec;
    }


    int main(void) {

	    numberRecord *list;
	    list = malloc(sizeof(numberRecord));
		numberRecord **p = malloc(sizeof(numberRecord));
	    fillList(p);

	    printf("ListCount: %i \n", countList(*p));
	    printList(*p);
	    return 0;
    }

[quzah]

In the main I allocate memory to the pointer to a pointer. I allocate the space of a struct and assign it to p. Is this correct or does it just happen to work out right. It seems a bit illogical since p is a pointer to a pointer and not a pointer to.

	numberRecord **p = malloc(sizeof(numberRecord));

You don't actually do anything with it, so while not exactly correct, it's not actually doing anything. Malloc wants the size in bytes of a block of memory to give you. It doesn't actually care how you give it a number, just as long as the number is meaningful to you.

int x = sizeof( int ); /* let's say 4 */
int *p;

p = malloc( 4 );
free( p );
p = malloc( x );
free( p );
p = malloc( sizeof( x ) );
free( p );
p = malloc( 1 + 1 + 1 + 1 );
free( p );
p = malloc( 8 ); /* give us 2 ints worth instead */
free( p );

None of that really matters, as long as the size is equal to or bigger than (in evenly divisible chunks) the object you want to assign it to. It won't actually even matter if it's too small, other than the fact that trying to use it won't work right:

double *p;
p = malloc( 1 ); /* 1 < sizeof( double ) */
p[ 0 ] = 0.0; /* that's bad */
free( p );

But in your example, you don't really need a pointer to a pointer for anything in main. You just need:

struct foo *p;
myfun( &p );
...
void myfun( struct foo **list )
{
    ...
}

Quzah.

[whiteflags]

I'd do this:

numberRecord *list;
list = malloc(sizeof(numberRecord));
fillList(&list);

Do you see how that makes a pointer to pointer which will change list?

ETA: Ninja'd again

[django]

Thanks Quzah, good remark, helps me to understand it again a bit better. I revised my main like this (which looks exactly like what whiteflags suggested):

    int main(void) {

	    numberRecord *list;
	    fillList(&list);

	    printf("ListCount: %i \n", countList(list));
	    printList(list);
	    return 0;
    }

To close it off, a quotation from Joelonsoftware.com which came to my mind a few times the last days:

"...They are having a good ol'; time learning Pascal in college, until one day their professor introduces pointers, and suddenly, they don't get it. They just don't understand anything any more. 90% of the class goes off and becomes PoliSci majors, then they tell their friends that there weren't enough good looking members of the appropriate sex in their CompSci classes, that's why they switched. For some reason most people seem to be born without the part of the brain that understands pointers. This is an aptitude thing, not a skill thing – it requires a complex form of doubly-indirected thinking that some people just can't do. " The Guerrilla Guide to Interviewing - Joel on Software

[iMalc]

That's a very awkward implementaion of countList. Why not just...

int countList(struct numberRecord *record) {
	int count = 0;
	while (record != NULL) {
		++count;
		record = record->next;
	}
	return count;
}

You don't have to make copies of the input arguments either. The compiler already does that as the function is called.

[AndrewHunter]

Here is a good read on pointers. I would suggest perusing through that to help you solidify your knowledge.

[quzah]

	struct order order1;
	struct order order2;
	struct order order3;
	struct bookOrder book1;
	struct bookOrder book2;
	struct bookOrder book3;

All of these are local, and are destroyed when that function returns. You need to be dynamically allocating those if you want them to stick around - or, have all of your functions work from that point onward:

void foo()
{
    struct local stuff;
    editstuff( stuff );
    printstuff( stuff );
    /* stuff is destroyed now that this returns */
}

Quzah.