Linked Lists (Structures)

	struct person {
		char name[30];
		int age;
		struct person *nextPtr;
	}

We'll keep it simple. So when a variable is declared of type struct person, room in memory is set aside large enough to hold a string of thirty characters and an integer. There is also a small amount of space which will be used to store the address of another variable of type struct person.
So we'll create a new variable of type struct person. Now person1 has been allocated in memory. Now lets create another. So now there are two variables of type struct person, which we'll name person1 and person2. Each memory location (person1 or person2) can hold a string of 30 chars, an int and a pointer to another structure somewhere.
Now to make a simple linked list. To create this, we simply assign the location of where person2 resides in memory to person1->nextPtr. This means, that the pointer *nextPtr inside person1 will contain the address of person2. Now the *nextPtr in person2 will be NULL (point to nothing) until another structure is added to our linked list. And to complete the linked list, it is always good practise to declare another variable of type struct person (we'll call this variable start_of_list). Then you have the *nextPtr inside of start_of_list to point to person1. This way whenever you want to goto the beginning of the list, you simply move to the address stored in start_of_list->nextPtr.
Is this making sense so far? Here is my hand drawing of what you should be imaging when you think of our two structure linked list.

So the arrow going from one structure to another just indicates that *nextPtr inside person1 is referencing (storing the address) of person2. And the line with the E like symbol (---E ) going from person2 just shows that currently person2 is pointing or referencing nothing or NULL.
Now if we ever want to add another member onto the end of the list we just simply allocate memory for it by declaring it and then we have person2->nextPtr reference it, that is store its location in memory. Also, we want to have the nextPtr in this new structure to be NULL (point to nothing).
If we want to add one to the beginning of the list, we have to do 3 things. Declare the new variable (say person3), then have person3->nextPtr store the address of the current first element in the list which is person1. Then we must change start_of_list to reference person3. It would look like this:

To add one in the middle we simply find where we want to place it. We then have the *nextPtr of the structure to come before it reference this new structure and the *nextPtr of this new structure to reference the structure in the list that is to come after it.
Try drawing a list like I have above. Then create a new structure find a place in the list, and redraw the list with it added. See what has changed in the list. See what structures have been changed so that the nextPtr inside them is pointing to a new structure.
Once you understand this, you've pretty much got it.

Here is a simple program:
--------------------------------------------------------------

/*
Programmed by: Randy Rieger ferris@windsor.igs.net

This program is a simple example of one which generates a linked list
and which uses the functions malloc() and free().

This program has commented areas to explain what is happening throughout the
program, but if you need more information, check out the LINKED LIST tutorial
on the tutorial page!!!
*/


#include "stdio.h"   /*replace quotes with angle brackets */
#include "stdlib.h"  /*replace quotes with angle brackets */


struct list
{
  int value;
  struct list *next;
};

typedef struct list LIST;

typedef LIST *LISTLINK;

void list_build() {
	/* 3 pointers of type structure are declared below. */
	LISTLINK temp, current, beginning;
	/* We'll use the array a[] for our input into the linked list */
	int a[]={5,4,3,2,1}, i=0, j=0;

	/* We will allocate memory for current to point to using the function
	malloc.  Malloc takes one parameter which is the amount of bytes to set
	aside in memory.  In this case, we used sizeof(LIST) which will return
	the amount of bytes that struct list (which we'll refer to as a 'node')
	would take up in memory.  Malloc then returns a pointer to this memory
	and assigns it to current.
		We could have instead used a integer instead of sizeof(LIST) but our
	way is better.  Because if we ever changed our original struct list
	definition, which would change it's size, we don't have to worry about
	changing it in our call to malloc() since the sizeof() function will do
	it automatically. */

	current = malloc( sizeof(LIST) );
	/* assign the address pointed to by 'current' to the pointer 'beginning */
	beginning=current;
	printf("\n\nPrint the character values...\n");

	/* We use this while loop to assign values in the linked list and to build
	the list from the first node up */
	while (i<5) {
		temp=current;
		temp->value=a[i];

		/* this will create room in memory for a node of size LIST (or struct
		list) and have temp->next point to it */
		temp->next = malloc( sizeof(LIST) );
		
		/* this prints the value of the integer in temp */
		printf("%d -> ", temp->value );
		
		/* using the statement below will reassign current to point to temp->next.
		This way, current will move from the first node in our list, to the second,
		and so on until it reaches the last node.  This is how your make a function
		move throughout a linked list.*/
		current=temp->next;
		i++;
	}

  /* free loop */
  /* this loop here moves through the list and frees the memory allocated
  by each structure in the linked list.  This is important to conserve
  memory on your system.  Whenever memory is allocated using malloc or other
  such functions, the memory should be freed when it is done with */
  
	while (j<5) {
		free(beginning);
		beginning=beginning->next;
      j++;
  }
}

int main( void )
{
  
  list_build();


  return(0);
}

/*
Rewrite this program but change it so:

1. The user enters 10 integers and you print out these integers in a linked
list
2. The user enters 10 characters and you print out these in a linked list
3. Try adding a function to delete a node from the list
4. Try your luck with double linked lists.  In such a list, a node points to
the node after it in the list and the one before it aswell.  See info on
double linked lists in the source or tutorial sections of C Source Warehouse.

email your answers to me at my email above and I'll check it over for ya!
*/
-----------------------------------------------------------------

Make sure you play around with this program and try to find some uses for this type of data structure in your own programs. Comments? write me at ferris@windsor.igs.net