page31

Description of the program

A structure is defined at the start of the program to hold each node, which consists of a link pointer to the next node in the list as well as the data for the node, in this case, just two integer variables, one to hold a students id number, and the other to hold the students age. Not all linked lists contain student details, and as such you can have as many data fields as you like in the structure to hold whatever data you want each node to contain.

typedef struct T_STUDENT
{
struct T_STUDENT *link;
int id;
int age;
}STUDENT;

Next a variable called start is declared, which will be a pointer to the first node in the list. From there, any node in the list can be reached by passing through each nodes links. Initially there is no nodes in the list, so this is set to NULL to indicate this.

STUDENT *start=NULL;

Everything is now set up to start writing in the functions that will operate on the list, ie, add new nodes, delete nodes etc.. The implementation to each of these functions is explained below :

Adding a node ( addtolist )

The function code to add a new node to the list is shown below :

int addtolist(int id,int age)
{
STUDENT *newstudent;

newstudent=(STUDENT*)malloc(sizeof(STUDENT));
if(newstudent!=NULL)
{
newstudent->id=id;
newstudent->age=age;
newstudent->link=start;
start=newstudent;
return(1);
}
return(0);
}

The first thing to notice is that the function accepts two integer parameters ( id and age ). These values passed into the function will be used to initalise the data portion of the node. You don't have to do it this way, imagine for example, that you have a list where each node has 20 or more data portions to it, the parameter list would be pretty long for the function. There are a few ways around this, but one way is to set the data portion after the call to the add function. After the add function has successfully completed the start pointer will point to the newly created node, of which the data can then be set by the calling function. For this to happen though, it is important that the calling function checks that the node was successfully created. This is why the addtolist function returns an integer. If it successfully creates a new node, then it sets the start pointer to point to it, and returns a 1. If it fails to create a new node, then it doesn't alter the start pointer, and returns 0 indicating to the calling function the failure. This sample program doesn't need to check the success or failure of the function though, but the return values are implemented still.

After entering the function a pointer variable is allocated called newstudent, this will hold a pointer to the allocated node. The memory for the new node is then allocated in the newstudent=(STUDENT*)malloc(sizeof(STUDENT)); line. The malloc function will return a pointer to the newly allocated block of memory on success or NULL on failure. One possible reason for failure may be down to lack of available memory. What is important though, is that only enough memory is allocated to store the node. The success of the malloc call is then checked and if the memory for the node was allocated okay, it continues on, otherwise it returns 0.

On success, the data portions of the new node ( newstudent->id and newstudent->age ) are set to the values passed into the function. The link from the newly created node to the next node is set to point to the previous start node ( newstudent->link=start; ), and the start node is set to the current node just created ( start=newstudent; ). Finally a 1 is returned, indicating the success of the function.

Retrieving a node ( getfromlist )

The ability to retrieve a specific node from the linked list is a must, otherwise there isn't a lot of point using one. The code for doing this is shown below :

STUDENT *getfromlist(int id)
{
STUDENT *link;

link=start;
if(link==NULL)return(NULL);
while(1)
{
if(link->id==id)return(link);
link=link->link;
if(link==NULL)return(NULL);
}
}

The function takes a single parameter, which in the case of this linked list is the student id number, which is assumed to be unique for all the students in the list. Note, no checks have been made though when the nodes are added to see if a new node is unique ( this is the task at the bottom of the page ). If an existing node in the list contains a matching id to the one passed into the function, the function returns a pointer to the node, otherwise the function returns NULL to indicate that it wasn't found.

The function first declares a pointer variable called link to hold the current node that is being checked for an id match. This is set to the start of the linked list ( link=start; ). The list could be empty though ( ie when start is NULL ), so this is checked on the next line ( if(link==NULL)return(NULL); ). In other words, if the list is empty then the id being searched for is definately not there, because nothing is !

If the list isn't empty though, then an endless loop is entered into ( while(1) ), this forces the code below in the curly braces to loop continuously until the function meets a condition what ends up returning a value. There are two possible outcomes to this condition, the first is checked on the line if(link->id==id)return(link); This is checking to see if the id of the current node matches the id passed into the function, if it does, a pointer to the current node is returned, if it doesn't the link variable is set to point to the next node in the list ( link=link->link; ). Because of the way the linked list is initialised, with the start variable being set to NULL, and the way in which nodes are added, the last node will always have it's next link set to NULL to indicate the end of the list. The line if(link==NULL)return(NULL); checks for this point, and if found, returns NULL back to the calling function, indicating that a match hasn't been found.

Deleting a node ( deletefromlist )

This function is the most difficult of all of them, because deleting a node requires that the function "knows" the parent node of the node being deleted. It has to know this so that it can set the child link of the parent to not point to the node that's being deleted, but the child node of the node that's being deleted. There is another added complication to, in that the node being deleted might be at the head of the list and not have any parent node. In this case the start pointer will need adjusting. The code for deleting a node is shown below, it isn't a lot dis-similar to the code for retrieving a node though :

int deletefromlist(int id)
{
STUDENT *link,*parent=NULL;

link=start;
if(link==NULL)return(0);
while(1)
{
if(link->id==id)
{
if(parent==NULL)
{
start=link->link;
free(link);
return(1);
}
else
{
parent->link=link->link;
free(link);
return(1);
}
}
parent=link;
link=link->link;
if(link==NULL)return(0);
}
}

To delete a node the function first has to find the node matching the passed id, this code is virtually the same as the retreive code (above). The main difference is that this time, there is another pointer variable called parent which is initally set to NULL. After each unsuccessul check on the id match, the parent variable is set to point to the current node. This occurs before the link variable is updated to point to the next node. This way, when a successful match is found, the parent variable will hold the address of the previous node ( the parent ), or NULL if it is the first node in the list.

After finding a node that matches the passed id, the function checks to see if the parent variable is NULL. If it is, then it sets the start pointer to be the child of the current node ( the one being deleted ), this then means that the second node in the list becomes the first. This isn't the end of the story though, as the memory allocated for the node being deleted needs to be free'd up. On doing this the function returns a 1, indicating it deleted the node okay.

If the parent node isn't set to NULL, but set to point to a node in the list ( which will be the parent node ), then the function sets the parent's link pointer to be the link pointer of the node being deleted. This has the effect of making the chain skip past the current node. The memory for the node is then free'd up again as above and a success status of 1 is returned.

Displaying all the nodes in the list( displaylist )

There isn't a lot different here than the retreive function again. The main difference though is that there is no matching id checks made, instead the details of every node from the start to the end are displayed. The function code is below :

int displaylist(void)
{
STUDENT *link;
int count=0;

link=start;
if(link==NULL)
{
printf("No students in the list\n");
return(0);
}
while(1)
{
printf("Student = %d Age = %d\n",link->id,link->age);
count++;
link=link->link;
if(link==NULL)return(count);
}
}

The function returns the number of nodes in the list to the caller as well. It keeps this in the count variable, which is initialised to zero and incremented every time a node's details are displayed.

Free'ing up the whole list ( freelist )

At the end of any program that uses a linked list, all the memory allocated for the nodes in the list must be free'd up. This function does this, it's not a lot different from the display function above, however there is one extra pointer variable that is needed.

int freelist(void)
{
STUDENT *link,*temp;
int count=0;

link=start;
if(link==NULL)return(0);
while(1)
{
count++;
temp=link;
link=link->link;
free(temp);
if(link==NULL)
{
start=NULL;
return(count);
}
}
}

The main problem with removing nodes in a linked list is that information is needed after the node has been deleted to continue to move through the list. In other words, the link to the next node is contained within the node that's been deleted. To get around this a variable is declared ( called temp in this case ) to hold a pointer to the node being deleted before the link is moved on. So the function, first stores a pointer to the current node in temp ( temp=link; ), then it changes the pointer of the link variable to point to the next link in the list ( link=link->next; ) It then free's up the memory occupied by the current node, now with the pointer to it stored in temp ( free(temp); ). It does this for all the nodes in the list until the last one is reached, at that point it sets the start pointer back to equaling NULL again, because the list is now empty.

The main function

The main function is just used in the program above to test the functions actually work. The code for the main function and output from running the program is shown below, a description of the operation of the main function isn't needed :

void main(void)
{
STUDENT *temp;

printf("Adding five students\n\n");
addtolist(1,14);
addtolist(2,12);
addtolist(3,16);
addtolist(4,11);
addtolist(5,13);
displaylist();
printf("\nDeleting student 2\n\n");
deletefromlist(2);
displaylist();
printf("\nGetting student 3\n\n");
temp=getfromlist(3);
if(temp==NULL)
printf("Student not found\n");
else
printf("Student = %d Age = %d\n",temp->id,temp->age);
printf("\nDeleting all students\n\n");
freelist();
displaylist();
getch();
}

Adding five students

Student = 5 Age = 13
Student = 4 Age = 11
Student = 3 Age = 16
Student = 2 Age = 12
Student = 1 Age = 14

Deleting student 2

Student = 5 Age = 13
Student = 4 Age = 11
Student = 3 Age = 16
Student = 1 Age = 14

Getting student 3

Student = 3 Age = 16

Deleting all students

No students in the list