In this tutorial you will learn about C Programming – Linked Lists, Structure, Advantages of Linked List, and Types of linked list and Applications of linked lists.
Linked lists are a type of data structure for storing information as a list. They are a memory efficient alternative to arrays because the size of the list is only ever as large as the data. Plus they do not have to shift data and recopy when resizing as dynamic arrays do.
They do have the extra overhead of 1 or 2 pointers per data node, so they make sense only with larger records. You would not want to store a list of integers in a linked list because it would actually double your memory overhead over the same list in an array.
There are three different types of linked lists, but the other two are just variations of the basic singly linked list. If you understand this linked list then you will be able to handle other two types of lists.
Advantages of Linked Lists
A linked list is a dynamic data structure and therefore the size of the linked list can grow or shrink in size during execution of the program. A linked list does not require any extra space therefore it does not waste extra memory. It provides flexibility in rearranging the items efficiently.
The limitation of linked list is that it consumes extra space when compared to a array since each node must also contain the address of the next item in the list to search for a single item in a linked list is cumbersome and time consuming process.
Linked lists Types
There are 4 different kinds of linked lists:
- Linear singly linked list
- Circular singly linked list
- Two way or doubly linked list
- Circular doubly linked list.
Linked List Nodes
A linked list gets their name from the fact that each list node is “linked” by a pointer. A linked list node is comparable to an array element. A node contains a data portion and a pointer portion, and is declared as structs in C.
As an example, we can implement a list of high scores for a game as a linked list.
Let us now declare a node:
struct llnode {
char name[10];
int points;
struct llnode *next;
};
We have two variables that make up the data portion of the node, and then the pointer to the next node in the list.
Creating Linked Lists
A linked list always has a base node that is most commonly called a head, but some call it as a root. An empty linked list will have this node and will be set to NULL. This goes for all three types of linked lists. The last node in a linked list always points to NULL.
Let us declare our linked list for implementing high scores list.
struct llnode *head = NULL;
Here we just declared a regular pointer variable of the node struct we declared, and then set the head to NULL to indicate the list is empty.
Traversing a Linked List
Moving through a linked list and visiting all the nodes is called traversing the linked list. There is more than one way to encounter segmentation faults when traversing a linked list, but if you are careful and follow 2 basic checks you will be able to handle segmentation faults.
To traverse a singly linked list you create a pointer and set it to head. Often called the current node as a reminder that it is keeping track of the current node. Always make sure to check that head is not NULL before trying to traverse the list or you will get a segmentation fault. You may also need to check that the next pointer of the current node is not NULL, if not, you will go past the end of the list and create a segmentation fault.
Here is a failsafe way of traversing a singly linked list:
if (head != NULL) {
while (currentnode->next != NULL) {
currentnode = currentnode->next;
}}
We first check that the head is not NULL and if so, as long as the current pointer’s next is not NULL, we set current equal to the next node effectively moving through the entire list until we do encounter a next pointer that is NULL.
If you follow that formula, you will have no problems with segmentation faults during traversal.
}
Adding nodes to a linked list is relatively easy. We will need to cover the different cases of adding at the beginning, the middle or the end.
When adding a first node to a linked list, you create a temporary node pointer and allocate memory for the new node. Then set head’s next pointer so that it points to the new node.
Say the first player has just finished playing the game and we want to record their name and score in the high scores list. Here is a function that could accomplish just that.
void addfront(char name[], int score) {
struct llnode *tempnode;
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 {
tempnode->next = head;
head = tempnode;
}}
First we created a temporary node and copied our player’s name and score to it.
There are two cases you must consider when adding a node to the beginning of a linked list:
- Adding a node to the beginning of an empty list.
- Adding a node to the beginning of a nonempty list.
We handle the first case by checking for a NULL head. After we know the head is NULL, we set the head equal to the temporary node we created and set it’s next pointer to NULL to indicated it is the end of the list.
In the second case (our else control block) we set the temporary node’s next pointer to head to insert it before head’s current position. Then by setting head equal to the new temporary node, we have squeezed it in at the front of the list and the new node is at the head of the list.
Now let us add a node to the back of a linked list. It takes two node pointers to add a node at the end of an nonempty linked list. You use one to allocate memory and copy the data into, and set it as next pointer to NULL since it will be at the end of the list. The other pointer is to traverse to the end of the list. Once it reaches the end, set it as next pointer to the new node you created. Here is a function that would do just that in our high scores example:
void addend(char name[], int score) {
struct llnode *tempnode;
struct llnode *currentnode;
tempnode = (struct llnode *)malloc(sizeof(struct llnode));
strcpy(tempnode->name, name);
tempnode->score = score;
currentnode = head;
while (currentnode->next != NULL) {
currentnode = currentnode->next;
}tempnode->next = NULL;
currentnode->next = tempnode;
}
This should be relatively straightforward since you have seen all but the last two lines previously. We create and copy our data, as we have in earlier examples, then we traverse the list according to our earlier formula for traversal. The last two lines are how we accomplish the actual adding of our new node to the end of the list as was explained above.
We can also add new nodes to the middle of a list. To do this, it requires two spare pointers to keep from severing the list when the new node is inserted. It is also easier to do if the length of the list is known. You can add a simple variable to track that and just increment it whenever you add a node, if you desire this functionality from a linked list. Then as you traverse the list, make sure you have a counter that you increment to keep track of what position in the list your current pointer is currently at.
To illustrate this imagine we know the position we want to insert a new node at. It is arbitrary how this is determined or whether you decide to base your counting at 0 or at 1. In our example we started our counting at 1. Here is the snippet from our example program taken from the addNode function:
void addend(char name[], int score) {
struct llnode *tempnode;
struct llnode *currentnode;
tempnode = (struct llnode *)malloc(sizeof(struct llnode));
strcpy(tempnode->name, name);
tempnode->score = score;
currentnode = head;
while (currentnode->next != NULL) {
currentnode = currentnode->next;
}tempnode->next = NULL;
currentnode->next = tempnode;
}
Since we know our position we want to insert at, we use the variable position to mark it, and currentpos to keep track of the current node we have traversed to. The while loop takes care of traversing the list as well as incrementing currentpos each time a new node is reached. Note in this case we use a previous pointer and a current pointer for moving through the list.
Then we use the familiar allocation of memory and copying of data to the new node which we call tempnode. Now, remember that previousnode pointer we brought along? We use it to keep from losing the end of the list past the node we are inserting. We set its next pointer to the new node and then set that new node’s next pointer to the current node which is acting as a placeholder for the rest of the list.
{mospagebreak title=Singly Linked List Example Program}
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.
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.
#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 liststruct 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 toint 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
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.
Here is the output after running the program.
In the next tutorial we will be learning more about Circular Linked Lists and Doubly Linked Lists. Feel free to ask any questions you might have.
