nightmare - understanding whats going on in a linked list

hi! i'm new to the board, (and to C!) and it woud be great if anone could help me out? i've got a program here, and i've been trying to work through it line by line to see what each bit does. i know that the overall gist is to read data from one file with four columns in it, display it on a screen and output it to another file. i know it uses something clled a "linked list", which i believe is a way of managing memory dynamically, but i'm not really sure. anyway, i have attempted to comment every line, and it would be great if anyone could put me right on the stuff i'm a bit hazy about!

thanks so much!

fate

Code:

	#include <stdio.h> 
	#include <string.h>
	#include <stdlib.h>
	
	int main(void) /* begins a function which most of the programm is inside */
		{
	
		double dummy = 9.0; 
	
		char line[100], inputfilename[100], outputfilename[100]; /* declares maximum length for variables? */
		char*line_ptr; /* creates a pointer to the variable "line" */
		struct node  /* this is another variable, but it contains variables within itsself? */
			{
			int id; /* these variables that are read in are in the form of a table, this reads the row number (first column)*/
			double x, y, z; /* 3 doubles to store values from the other three columns*/
			struct node *next; /* now that the four columns have been read, this tells the variable to go to the next row?*/
			};
		struct node *first_ptr=NULL, *previous_ptr=NULL, new_ptr, *current_ptr=NULL; /* don't really get this bit. these are pointers to something?*/
		int no_nodes = 0, no_values; /* setting the initial values to zero? */
	
		FILE*input_stream; /* saying that the input_stream gets its values from an external file? */
		FILE*output_stream; /* saying that the output_stream gets its values from an external file? */
	
		fprintf(stdout, "Enter file name for source data:"); /*prompts the user for the name of the data file*/
		fscanf(stdin, "%s", inputfilename); /*reads the users response*/
		fprintf(stdout, "Enter file name for data to be written to:"); /* prompts the user for an output filename*/
		fscanf(stdin, "%s", outputfilename); /* reads the users response */
	
		if ((input_stream = fopen(inputfilename, "r")) !=NULL) /* if the user has given a filename*/
			{
			output_stream = fopen(outputfilename, "a"); /* open the file*/
    
		     while(line_ptr = fgets(line, sizeof(line), input_stream) !=NULL) /* while there is information on the next line of the input file*/ 
				{
				if( no_values = sscanf(line, "%d %lf %lf %lf", &new_ptr.id, &new_ptr.x, &new_ptr.y, &new_ptr.z) ) /* save the values in the file data as an integer, double, double, and double, pointing to the next bit of free memory by the pointers??? */
					{
					current_ptr = (struct node *)malloc(sizeof(struct node)); /* allocate sufficient memory to store a row of data */
					*current_ptr = new_ptr; /* no idea whats going on here */
					current_ptr->next=NULL; /* no idea whats going on here */
					if(first_ptr==NULL) /* no idea whats going on here */
						{
						first_ptr = current_ptr; /* no idea whats going on here */
						previous_ptr = current_ptr; /* no idea whats going on here */
						}
					else
						{
						previous_ptr->next = current_ptr; /* no idea whats going on here */
						previous_ptr = current_ptr; /* no idea whats going on here */
						}
					fprintf(output_stream, "%d,%f,%f,%f\n", current_ptr->id, current_ptr->x, current_ptr->y, current_ptr->z); /*print what has just been read into the output file */
					fprintf(stdout, "%d,%f,%f,%f\n", current_ptr->id, current_ptr->x, current_ptr->y, current_ptr->z); /* and into a file */
					no_nodes++; /*increment the number of nodes by 1 and do the while loop again */
					}
				if ((line_ptr !=NULL) /* if the line_ptr returns a value not equl to NULL */
				&& /* logical AND */
				(no_values !=4)&&(no_nodes!=0)) /* number of values is not equal to 4, logical AND number of nodes is not equal to 0 */
				fprintf(stdout, "Error reading line %s\n", line); /* then the line of data is incorrect. print error reading file on screen */
				}       
			if (line_ptr==NULL) /* if the next line is contains no data */
			fprintf(stdout, "\nEnd of file found\n"); /* you've reached the end */

			current_ptr = first_ptr; /* no idea whats going on here */
			while(current_ptr!=NULL) /* while the current pointer is blank*/
				{
				previous_ptr = current_ptr->next; /* no idea whats going on here */
				free(current_ptr); /* no idea whats going on here */
				current_ptr=previous_ptr; /* no idea whats going on here */
				}
			fclose(output_stream); /*close the output file*/
			}
		return(0); /*return a value of 0*/
	}	/* fin! */

Code:

struct node  /* this is another variable, but it contains variables within itsself? */
{
	int id; /* these variables that are read in are in the form of a table, this reads the row number (first column)*/
	double x, y, z; /* 3 doubles to store values from the other three columns*/
	struct node *next; /* now that the four columns have been read, this tells the variable to go to the next row?*/
};

This is a structure. Structures are collections of variables. This structure contains an integer, three doubles, and a pointer to a structure of the same type.

The structure is declared here, but no instance of the structure is created. If you want to create an instance of this variable, you'd do:

Code:

struct node mynode;

The bolded section is the type of variable. You use this in place of 'int' or 'double' or whatever your standard data types are.

The above code declares an instance of 'struct node', with the name of 'mynode'.

To access members of 'mynode' directly, that is to say not through a pointer, you use the '.' or 'dot operator'.

Such as:

Code:

struct node mynode;

mynode.id = 10;

This assigns the value 10 to the 'id' portion of this structure. You access members of a structure as you would normally use a stand alone integer, double, or what not.

The other method for accessing structure members is through the '->' operator, otherwise called the arrow operator. You use the arrow operator when you are accessing a structure through a pointer.

Code:

struct node mynode;
struct node *ptrtomynode;

ptrtomynode = &mynode;

ptrtomynode->id = 10;

Here we declare an instance of 'struct node', called 'mynode'. We then declare a pointer to a 'struct node', which we call 'ptrtomynode'. Since pointers store addresses of variables, and since we want it to point to 'mynode', we do so with the next line of code. Finally we access 'id' through our pointer, and assign it the value of 10.

Code:

struct node *first_ptr=NULL, *previous_ptr=NULL, new_ptr, *current_ptr=NULL; /* don't really get this bit. these are pointers to something?*/

Yes. These are pointers to 'struct node' variables. These will eventually point to various nodes you allocate in the program.

Code:

		FILE*input_stream; /* saying that the input_stream gets its values from an external file? */
		FILE*output_stream; /* saying that the output_stream gets its values from an external file? */

These are FILE pointers. You use them to open files for reading and writing.

Code:

    
     while(line_ptr = fgets(line, sizeof(line), input_stream) !=NULL) /* while there is information on the next line of the input file*/

This does two tasks at once. It reads a line from a file, and at the same time checks the return value of 'fgets' to make sure the read was successful.

Code:

if( no_values = sscanf(line, "%d %lf %lf %lf", &new_ptr.id, &new_ptr.x, &new_ptr.y, &new_ptr.z) ) /* save the values in the file data as an integer, double, double, and double, pointing to the next bit of free memory by the pointers??? */

This is actually a bad piece of code. In the assignment to 'no_values', there should be parenthesis around it, and then the end result should be compared.

If you look above in the line with all the node pointers, you'll notice that 'new_ptr' is not actually a pointer. It's an instance of 'struct node'. As such, they don't need to allocate memory for it, they're using it to temporarily hold the values they've just read in.

Code:

current_ptr = (struct node *)malloc(sizeof(struct node)); /* allocate sufficient memory to store a row of data */
					*current_ptr = new_ptr; /* no idea whats going on here */

Here they malloc off a chunk of memory the size of 'struct node'. Next, they assign the contents of 'new_ptr' to the memory they've allocated. The * in front of 'current_ptr' in the assignment dereferences that block of memory. That is to say, it gives you what's being pointed at.

Remember above how pointers store addresses of other variables? Well to get what they're pointing at, rather than the address itself, you dereference the pointer.

The * in front of the pointer as it is used here makes it dereferenced. That is to say it gives you what it points at, rather than just telling you what address the variable (pointer) is storing.

Code:

current_ptr->next=NULL; /* no idea whats going on here */

Here they make the 'next' pointer in the structure they've allocated not point to anything. That is, they set it to point to NULL.

All pointers when created point to something. However, unless you implicitly set them to point to what you want them to point at, they point at some random piece of memory. Since that's usually (always) bad, you must set your pointers manually (like you should with all your variables) set them to whatever value you want.

Here, they set it to point to NULL. NULL is tested on pointers to see if it points to something valid. Consider:

Code:

if( ptrtomynode->next == NULL )
{
    printf("ptrtomynode->next doesn\'t point to anything valid.\n");
}
else
{
    printf("ptrtomynode->next is pointing to something.\n");
}

Here we check to see if 'ptrtomynode->next' is actually pointing to another node. If it isn't, it is set to NULL. Otherwise, we assume it's been set correctly. It's a common test when using pointers.

You want to be sure you set your pointers to NULL if you don't specificly have them pointing to something.

Code:

if(first_ptr==NULL) /* no idea whats going on here */
{
	first_ptr = current_ptr; /* no idea whats going on here */
	previous_ptr = current_ptr; /* no idea whats going on here */
}

Here they check to see if their 'first_ptr' is already pointing at something. If it isn't, they make this poitner point to the new node they've allocated (above where malloc is called) earlier.

Then they use another pointer 'previous_ptr', and make it also point to this same node.

Code:

else
{
	previous_ptr->next = current_ptr; /* no idea whats going on here */
	previous_ptr = current_ptr; /* no idea whats going on here */
}

Here, they know already that there is something at 'first_ptr'. It's already pointing to something. So what they do then is make 'previous_ptr''s 'next' member point to the new node they've allocated. Once that is done, they make this 'previous_ptr' point to this node also.

This is not great code here. Not how I'd have done it. They're trying to chain all of the new data together. It's a poor implementation.

Code:

while(current_ptr!=NULL) /* while the current pointer is blank*/

Actually, it's while the current pointer isn't blank. Meaning, while this pointer poitns to a valid node, do this loop.

Code:

previous_ptr = current_ptr->next; /* no idea whats going on here */
free(current_ptr); /* no idea whats going on here */
current_ptr=previous_ptr; /* no idea whats going on here */

They're snipping of links of a chain, and getting rid of them. Think of holding up a portion of chain in your hand. First you grab one link down, and remember where it's at. Then you grab some bolt cutters, and lop off the top link. Then you move down one, and do it again. Do this until all the links are gone.

That's what they're doing. 'free' frees up memory that you've allocated with 'malloc' or 'calloc'. Every time you call either 'malloc' or 'calloc', you must call 'free' on that same memory to free it when you're done.

Failure to do so causes memory leaks.

I believe the FAQ/tutorials section of the site has a portion on linked lists. You may want to give that a read.

Quzah.

thanks a lot buddy, your a star! you've explaiend that soooo much more clearly than my lecturer ever managed! i think that if you're ever in loughborough, UK that i owe you a beer or two!

cheers again

fate