Link Lists

• Long explanation
• Short explanation

Question, how would you write a program to meet the following requirements?

1. Read an unknown number of records from a file into memory. A typical record would look like:

   
   	Ref  Title	  Cost
   	---  -----	  ----
   	1234 Oracle_Guide 22.95
   
   

2. Perform a numeric sort based on the first field.
3. Delete duplicate records based on the first field.

One method is to define an array of records as below:

	main()
 	{
	  char array[50][80]; /* 50 records, 80 bytes long	*/
	}

The data can then be read into the array and then actions performed on the data. This is OK but has some major problems.

1. The arrary will hold all the data in character format. It would be nice to hold the integer and decimal numbers in a more appropriate form.
2. If you have more than 50 records the program has to be altered and recompiled.

The first problem could be fixed by defining an array of structures BUT both problems can be solved with linked lists.

The concept of a linked list is fairly simple. It is a group of structures linked together by pointers, here is a picture:

The "Name Age Pointer" block could be defined as below:

	struct record {char name[20]; int age; struct record *next_rec;}; 

The important bit is "struct record *next_rec" this is the pointer to the next structure (record). It will either point to the next record which will require memory reserved with the malloc function or NULL if its the last record.

Examples

Here is the first example. This program is more complicated than I would like, but its the simplest I can come up with.

This is the same program but without the heavy commenting.

This is still the same program but it is slightly simplified with the use of typedef.