Linked List Example in C

A linked list is a data structure that consists of a group of nodes which are linked together. These are one of the simplest and most common data structures for C programs. One of the biggest advantages that linked lists have is they are efficient at inserting and deleting elements within the sequence. The biggest drawback of linked list is you generally have to traverse the list to find particular nodes or to get the number of nodes in the list.

There are several varieties of linked lists like singly linked, doubly linked and multiply linked. We will be using singly linked lists in this blog as we create various networking tools therefore, in this first tutorial, we will build a singly linked list library that we can integrate with our networking code. While the code for this library could be optimized and compacted, I feel that it is more important to make code readable when learning therefore the code for this library and most of the code in this blog will be written with functionality and readability as the primary objectives.

In a singly linked list each node has one or more data fields and a “next” field that points to the next node in the list. The preceding image shows how this works where the “next” element contains a pointer to the next node in the list.

You will be able to see how the linked list works as we go though the code but first lets take a quick look at the header file for our linked list library:

#ifndef LinkedListTest_linkedlistlib_h

#define LinkedListTest_linkedlistlib_h

struct node

{

   int num;

   char name[16];

   struct node *next;

};

struct node *buildnode(int num, char *name);

int addnode(struct node *head, struct node *add);

int length(struct node* head);

void deletelist(struct node **head);

struct node *searchnode(struct node *head, char *name);

int removenode(struct node **head, struct node *remove);

#endif

We begin by defining the structure that will hold our data. This structure can contain whatever data elements you need but you will need to keep the struct node *next element because it points to the next node in the list.
Next we define six functions that we will be implementing for our library. These functions are:

• struct node *buildnode(int num, char *name) – This is a convenience method that will build the node given the values pass in. This function and the searchnode() function are the two functions that we will need to change when we add this library to our projects.
  
• int addnode(struct node *head, struct node *add) – This function will add a node to the end of our list. The head node is the first node in our structure while the add node is the node to add. This function will return the number of elements that are in the list after the new node is added.
  
• int length(struct node *head) – This function will return the number of nodes in the list. The head node is the first node in the list. If we passed another node, besides the first node of the list, then this function would return the number of nodes from that node to the end of the list.
  
• void deletelist(struct node **head) – Deletes the list and frees the memory being used.
  
• struct node *searchnode(struct node *head, char *name) – This function will search the list and return the first structure that has a name element equal to the name argument.
  
• int removenode(struct node **head, struct node *remove) – This function will search the list for the remove node and remove it from the list. This function will return a 0 if it was successful in finding and removing the node or a -1 if the remove node could not be found.
  

Now lets look at each of the functions and see how they work. We will start with the struct node *buildnode(int num, char *name) function. This function takes two arguments and build a new node structure with those arguments. Here is the code:

struct node *buildnode(int num, char *name) {

   struct node *new = (struct node *)malloc(sizeof(struct node));

   new->num = num;

   strncpy(new->name, name, sizeof(new->name));

   new->next = NULL;

   return new;

}

This function starts off by allocating memory needed for the new node structure with the malloc() function. We will need to manually release this memory when we are finished with this node otherwise we will have memory leaks in our application.

Next we assign the values to our structure. Notice that we use the strncpy() function to copy the name value into our structure. This is done because the char pointer that was passed to our function may get released or reused, so in order to make sure that we do not lose the value we copy it into the structure. We also set the next pointer to NULL because it is not currently part of the linked list. Remember this function just creates a node but does not put it in a linked list. To put a node into a linked list we we use the addnode() function.

Now we will look at our int addnode(struct node *head, struct node *add) function. This function will add a node to the end of the list and return the total number of nodes after the node is added.

int addnode(struct node *head, struct node *add) {

   struct node* current = head;

   int count = 0;

   while (current->next != NULL) {

      count++;

      current = current->next;

   }

   current->next = add;

   count++;

   return count;

}

The addnode() function accepts two arguments; the first argument is the first node of the list and the second argument is the node to add. In order to add a node to the end of the list, we need to loop though the list to find the end. This is a weakness of singly linked list; since we do not store the end of the list or the number of nodes in the list we need to loop though the whole list to determine the number of nodes or to find the end of the list.

Since we do not want to move the pointer that was passed into the function which points to the first node of the list, we create a new pointer that we name current that also points to the first node of the list. We then set up a while loop that loops through the list until we reach the end of the list. We know that we have found the last node when the next pointer of that node points to NULL rather than another node. If the next pointer does not point to NULL, we increment our counter and move the current point to point to the next node in our list.

Once we find the last node we set the next pointer of that node to point to the node that we are adding to the list. This will put the new node at the end of the list. This does assume that the next pointer within the node that we are adding points to NULL and not another node in the list. If the next pointer in the new node points to another node in the list then we would set up a linked list that loops around in a circle. This would create an endless loop when we attempt to find the end of the list or when we search for a specific node in the list. To be on the safe side we could put a line in the function that sets the next pointer of the new node to NULL but I left that out because this function could also be used to combine two linked lists where the next pointer may point to another node in a separate list.

Next we will look at the int length(struct node *head) function. This function will return the number of nodes in our list. This function accepts one argument which is the first node in the list. Here is the code for the length() function:

int length(struct node *head) {

   struct node* current = head;

   int count = 0;

   while (current != NULL) {

      count++;

      current = current->next;

   }

   return count;

}

The length function is a duplicate of our addnode() function described earlier except that we are not adding a new node to the list once we find the end of the list.

Now lets look at the void deletelist(struct node **head) function. This function will delete the whole list and free the memory that the list uses. This function takes one argument which is a pointer to a pointer that points the the first node of the list to remove. Here is the code for our deletelist() function.

void deletelist(struct node **head) {

    struct node *next;

    struct node *current = *head;

    while (current) {

       next = current->next;

       free(current);

       current=next;

    }

    *head = NULL;

}

In the deletelist() function we loop through the list. For each node in the list we assign the next pointer to point to the next node in the list. We then use the free() function to free the memory that is assigned to the current node. This allows your application to reuse this memory location and prevents memory leaks. We then set the current pointer to point to the next node in the list. Finally, once all of the nodes are removed, we set the pointer which pointed to the first node in the list to NULL to prevent our application from using it by mistake.

Now lets see how the struct node *searchnode(struct node *head, char *name) function works. This functions searches the linked list for the first node that has a name value that is equal to the name argument passed to the function. This function takes two arguments; the first argument is a pointer to the first node in the linked list and the second argument is a pointer to the char string that we are searching for. Lets look at the code for the searchnode() function.

struct node *searchnode(struct node *head, char *name) {

   struct node* current = head;

   while (current != NULL) {

   if (strcmp(current->name,name) == 0)

      return current;

      current = current->next;

   }

   return NULL;

}

We start off by creating a while loop that loops though our list. We then compare the name element of each node with the name argument passed into the function using the strcmp() function. If they are equal, then we found the node we are looking for and return the current node. If they are not equal, we our loop moves to the next node. If we are unable to find a node that contains the name argument we return NULL.

Finally lets look at the int removenode(struct node **head, struct node *remove) function. This function will remove a specified node from our linked list. This function takes two arguments; the first argument being a pointer to a pointer that points to the linked list to search and the second argument being a pointer to the node to remove. The removenode() function will return 0 if the node was found and removed or -1 if the node was not removed. Lets look at the code:

int removenode(struct node **head, struct node *remove) {

   struct node* current = *head;

   struct node* prev = NULL;

   while (current != NULL) {

       if (current == remove) {

          if (prev == NULL)

              *head = current->next;

          else

             prev->next = current->next;

          free(current);

          return 0;

       }

       prev=current;

      current = current->next;

   }

   return -1;

}

We begin the removenode() function by defining two pointers. We set the first pointer, current, to point to the first node of our list and set the second pointer, prev, to point to NULL. When we set up our while loop that will loop though our list, the current pointer will always point to the current node that we are checking and the prev pointer will always point to the previous node. We will need to know the previous node in our list because when we find the node to remove, well will need to change the next pointer of the previous node so it no longer points to the node we wish to remove. Lets look at a diagram that shows how we are going to remove a node from our list.

In the diagram we can see that in order to remove node2 from our list we need to change the next pointer of node1 to point to node3 rather than node2. We would then free the memory allocated to node2 so we do not have memory leaks in our application.

Once we have our two pointers defined we create a while loop that will loop though our list.
If the current node is equal to the remove node then this is the node to remove. If this is the node to remove we check to see if it is the first node in the list by seeing if the prev pointer is pointing to NULL. If this is the first node then we change the head pointer, that was passed into our function, to point to the next node in the list otherwise we set the next pointer from the previous structure to point to the node that the current node's next pointer is pointing too. Finally we free the memory that is used by the current node and return 0 signifying that we found and removed the node.

If the current node is not equal to the remove node then we set the prev pointer to point to the current node and the current pointer to point to the next node in the list. If we loop though the whole list and we do not find the remove node, then we return a -1 signifying that we could not find the node to remove.

Now lets look at some code to test our linked list library:

#include <stdio.h>

#include "linkedlistlib.h"

#include <time.h> 

void waitFor(unsigned int secs) {

    long retTime = time(0) + secs;

    while (time(0) < retTime);

   }

int main()

{

    printf("Hello world\n");

    int i;

    for (i=0; i< 500; i++) {

       struct node *first = buildnode(1,"Jon");

       struct node *second = buildnode(2, "Kim");

       struct node *three = buildnode(3, "Kailey");

       struct node *four = buildnode(4, "Kara");

       addnode(first, second);

       addnode(first, three);

       addnode(first, four); 

       printf("%d)----------\n",i);

       printf("Count %d\n", length(first));

       struct node *found = searchnode(first, "Kailey");

       if (found != NULL)

          printf("found: %d %s\n",found->num, found->name); 

       removenode(&first, first);

       printf("Count after remove %d\n", length(first));

       removenode(&first, found);

       printf("Count after second remove %d\n", length(first)); 

       deletelist(&first);

       printf("found: %d\n",length(first));

       printf("-------------------\n");

       waitFor(2);

    }

    return (0);

}

Inside the main() function, we begin by creating a for loop that will loop 500 times. This loop will allow us to see how our library performs by repeating the various tasks 500 times. If we analyze the memory usage while this runs it will also help us to detect any memory leaks.

Within the for loop we create four nodes using the buildnode() function. We then create our linked list by adding the last three nodes to our list using the addnode() function. Notice that we do not add the first node to the list with the addnode() function, that is because we use that first node as the first node for the list.
Now that we have our list built we verify that the list contains four nodes by using the length() function which returns the number of nodes in our list and print that count to the screen.

Next we use the searchnode() function to search for a node that contains the name “Kailey”. If we find a node that contains “Kailey” then we print the num and name elements of that structure to the screen.

We then try to remove the first node in our list by calling the removenode() function. We verify that the node was removed by printing out the total number of nodes in the list after we called the removenode() function. To verify that we can correctly remove multiple nodes, we then remove the “Kailey” node that we found earlier in this loop and once again print out the number of nodes in the list to the screen.

Finally we delete the list using the deletelist() function and once again print out the number of nodes in the list to verify that they were all removed.

I hope this post helps you understand linked lists a little better.