Singly Linked List Example Program

Home

Technical Training

C Tutorials

Table of Contents

C Programming - Linked Lists

Adding Nodes to Linked Lists

Singly Linked List Example Program

Page 3 of 3

Author: Exforsys Inc. Published on: 29th May 2006 | Last Updated on: 24th Jun 2011

C Programming - Linked Lists

For demonstration of singly linked lists, we have high scores for a game example. This is quite contrived as an array would clearly be better for this but it works well for illustrating linked list implementation.

Ads

What features do we need for this high scores list? We need to be able to create a list of players' names, the associated score; we want the results sorted from greatest score to least score.

Sample Code

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
// sample_game.c Exforsys tutorial. This is one way
// to fix the order problem, and also, the program isn't
// working as advertised. The function 'findposition()' isn't
// working as intended in the version supplied in Exforsys
// tutorials : It was returning position==1 each time, such
// that addend() could never be called. I added explanations
// and diagnostics such that you can see how the process
// works when it operates correctly. There are many ways to
// accomplish this and many stylistic points that could have
// been addressed, but I didn't want to get carried away.
// Besides, those exercises likely should be left to the student
// who might also like to try other dataset test cases to produce
// a more exhaustive test scenario. [Ernie Cordell 10November2011]
//The node for a linked list
struct llnode
{
char name[10];
int score;
struct llnode *next;
};
//Linked list for high scores and number of nodes for inserting in middle.
struct llnode *head = NULL;
int listlen = 0;
//Function that adds a new node to the beginning of a linked list.
void addfront(char name[], int score)
{
printf("Calling addfront for %s.\n", name);
struct llnode *tempnode;
//Create the new node and copy data.
tempnode = (struct llnode *)malloc(sizeof(struct llnode));
strcpy(tempnode->name, name);
tempnode->score = score;
//2 cases: beginning of empty list or beginning of unempty list.
if (head == NULL)
{
head = tempnode;
head->next = NULL;
}
else
{
//Insert the new node before current head, then make the new node the head.
tempnode->next = head;
head = tempnode;
}
}
//Function that adds a new node to the end of a linked list.
void addend(char name[], int score)
{
printf("Calling addend for %s.\n", name);
struct llnode *tempnode = (struct llnode *)malloc(sizeof(struct llnode));
struct llnode *currentnode = tempnode;
//Create the new node and copy data.
strcpy(tempnode->name, name);
tempnode->score = score;
//Traverse the list to the last node.
if (head == NULL)
{
head = tempnode;
tempnode->next = NULL;
}
else
{
currentnode = head;
while (currentnode->next != NULL)
{
currentnode = currentnode->next;
}
//Set the new node's pointer to NULL.
tempnode->next = NULL;
//Set the last node pointer's next to the new node.
currentnode->next = tempnode;
}
}
//determines which position in the list a node should be placed. Not related to
int findposition(int score)
{
printf("Calling findposition . . . \n");
struct llnode *currentnode;
int position = 1;
//If the list is not empty, traverse it.
printf("The address of head is %p.\n", head);
currentnode = head;
if (head != NULL)
{
do
{
//If the new score is greater than the saved score at the node, then we
//want to insert here.
printf("Temp score: %d, Node score: %d.\n",
score, currentnode->score);
if (score >= currentnode->score)
return position;
//Otherwise traverse and track position.
currentnode = currentnode->next;
position++;
}
while (currentnode/*->next */ != NULL);
}
return position;
}
//Adds a new node by determining where in the list it should go.
void addNode(char name[], int score)
{
printf("\ntCalling addNode . . . \n");
int currentpos = 1;
int position = findposition(score);
printf("Position is %d, listlen is %d.\n", position, listlen);
struct llnode *tempnode = (struct llnode *)malloc(sizeof(struct llnode));
struct llnode *previousnode = tempnode;
struct llnode *currentnode;
currentnode = head;
if (position == 1)
{
//Add to beginning of list.
addfront(name, score);
listlen++;
}
else if (position > listlen)
{
//Add to end of list.
addend(name, score);
listlen++;
}
else
{
//Add somewhere in the middle of the list.
while (currentpos < position)
{
//traverse the list until we find the location for the new node.
currentpos++;
previousnode = currentnode;
currentnode = currentnode->next;
}
strcpy(tempnode->name, name);
tempnode->score = score;
previousnode->next = tempnode;
printf("Adding %s after %s and before %s.\n", tempnode->name,
previousnode->name, currentnode->name);
tempnode->next = currentnode;
listlen++;
}
}
//Prints entire list.
void printList()
{
printf("tCalling printList . . . \n");
struct llnode *currentnode;
currentnode = head;
while (currentnode != NULL)
{
printf("%s:", currentnode->name);
printf("%d", currentnode->score);
printf("\n");
currentnode = currentnode->next;
}
}
int main(void)
{
char player1[] = {"Jon B."};
char player2[] = {"Tom D."};
char player3[] = {"Jesse M."};
char player4[] = {"Todd"};
char player5[] = {"Matt"};
int scores[] = {150, 100, 1000, 400, 275};
addNode(player1, scores[0]);
addNode(player2, scores[1]);
addNode(player3, scores[2]);
addNode(player4, scores[3]);
addNode(player5, scores[4]);
printList();
struct llnode* current = NULL;
while (head != NULL) // clear list (seal memory leak?)
{
current = head;
head = current->next;
free(current);
}
printList();
return(EXIT_SUCCESS);
}

Here is the complete source code of the above example
Download Sample Game Zip file

This example models 5 people having played a game with their scores added to a list of high scores, then it prints the list. The scores are not entered in any particular order as would happen in real life so the findposition function takes care of sorting the new nodes according to the scores before they are put into the list.

Ads

Here is the output after running the program.