Using Linked Lists In The C Programming Language - PART 2
In a previous blog post I made, HERE, I detailed how to use Linked Lists in the C Programming Language. In the years before C++ and the STL came out for C++, there were no simple to use data types like Lists, Queues, and Vectors. There were also no dynamic data types. Arrays in C had to know the specific size of the array before being declared. The solution to this problem was to use Linked Lists composed of a STRUCT containing pointers to other data elements in the Linked List.
In my previous blog post, I detailed how to implement a Singly Linked List with only one directional pointer, to emulate animals in a Zoo. This kind of linked list can only be traversed in one direction, forward. To be able to traverse a linked list in both the forward and backward directions, a Doubly Linked List has to be created with two directional pointers in the STRUCT type. Normally one pointing to the previous node in the list, and another pointer pointing to the next node in the list. In this blog post, we will make a simple C console program that will use a Doubly Linked List emulating the animals in a Zoo. Show how to search the linked list, and also show how to delete a node from the list while keeping the Linked List intact after the delete operation.
The C Programming Language was created by the computer scientist Dennis Ritchie working at Bell Labs in the 1970s. He was also instrumental in creating a thorough technical book about his creation called The C Programming Language, still published even today. This book is an excellent resource and can provide answers to any questions you may have about the C Programming Language.
To create this example C console program, I used the Microsoft Visual Studio Development Environment running on Windows 10. If you are using a Mac or Linux computer for your software development, Microsoft also makes the excellent Visual Studio Code Development Environment which allows for the development of C and C++ software. If you are not a fan of Microsoft like some open source developers, there is the excellent Eclipse CDT Development Environment which is written in Java and will run equally well on both Windows and Linux and BSD Unix. If you are a diehard Unix or Linux user and like to do everything from the command line, there is the GCC compiler available from GNU which will let you compile a wide range of programs from the command line.
To begin with our sample C console application using a Doubly Linked List, we will first declare some enum types to make our code more intuitive, and also we will define our STRUCT type for our zoo animal linked list. Note that our STRUCT has two pointer variables, one called NEXT, which will point to the next animal (node) in the list, and one called PREVIOUS which will point to the previous animal (node) in the list.
#include <stdio.h>
#include <stdlib.h>
// our animal types
enum AnimalType {
Lion,
Giraffe,
Zebra,
Pangolin
};
// our animal sex
enum AnimalSex {
Male,
Female
};
// data type to be used for each animal (node) in the linked list
struct zooAnimal {
enum AnimalType type;
int weight;
int age;
enum AnimalSex sex;
struct zooAnimal* next;
struct zooAnimal* previous;
};
Now, since C is a low level programming language, there is no simple way to reference the name of an enum property. C treats enum properties as having integer values. So, for us to create strings with the name of the enum property, we have to create some simple functions like the following to return us a string with the name of the enum property.
// function to return the string name of Animal Type Enum
const char* getEnumNameAnimalType(enum AnimalType animalType) {
switch (animalType)
{
case Lion: return "Lion";
case Giraffe: return "Giraffe";
case Zebra: return "Zebra";
case Pangolin: return "Pangolin";
}
}
// function to return the string name of Animal Sex Enum
const char* getEnumNameAnimalSex(enum AnimalSex animalSex) {
switch (animalSex)
{
case Male: return "Male";
case Female: return "Female";
}
}
Next, we will create the first node in our zoo animal linked list, a Lion, like the following. Since C is a low level programming language, we have to allocate the memory for our linked list node, and then cast that memory to the data type of the struct we are using for our list nodes. Normally you do not have to do this in high level programming languages like Java or C#. Note that initially our pointers to next and previous are NULL since there is only one animal (node) in the list, and no other animals in the list to serve as next or previous animals (nodes). We will also create a pointer called zooKeeper which we will use to traverse our list once it is finished.
// we will have a zoo keeper var to point at specific animals in the list
// starting with the first animal in the list
struct zooAnimal* zooKeeper = NULL;
// create a 3 year old 300 pound male lion, make start node of list
struct zooAnimal* lion1 = (struct zooAnimal*)malloc(sizeof(struct zooAnimal));
if (NULL == lion1)
{
printf("\n Lion creation failed \n");
return 1;
}
lion1->type = Lion;
lion1->sex = Male;
lion1->age = 3;
lion1->weight = 300;
lion1->next = NULL;
// since this is the first animal (node) in the list, there is no previous animal
lion1->previous = NULL;
// have the zoo keeper point to this first animal (node) in the list
zooKeeper = lion1;
Next, we will create the second animal (node) in our list, another Lion. Now that we have two animals (nodes) in the list, we can set the values of the next and previous pointers, like in the following.
// create a 1 year old 50 pound female lion cub then make next node in the list
// make the first lion the previous animal in the list
struct zooAnimal* lion2 = (struct zooAnimal*)malloc(sizeof(struct zooAnimal));
if (NULL == lion2)
{
printf("\n Lion creation failed \n");
return 1;
}
lion2->type = Lion;
lion2->sex = Female;
lion2->age = 1;
lion2->weight = 50;
lion2->next = NULL;
// add this lion to be the next animal (node) in the list
lion1->next = lion2;
// make the first lion the previous animal in the list
lion2->previous = lion1;
Next, we continue to build our linked list of zoo animals by creating Pangolin, Giraffe, and Zebra animals in our list, like the following:
// create a 3 year old 10 pound adult male pangolin then make next node in the list
// make the second lion the previous animal in the list
struct zooAnimal* pangolin1 = (struct zooAnimal*)malloc(sizeof(struct zooAnimal));
if (NULL == pangolin1)
{
printf("\n Pangolin creation failed \n");
return 1;
}
pangolin1->type = Pangolin;
pangolin1->sex = Male;
pangolin1->age = 3;
pangolin1->weight = 10;
pangolin1->next = NULL;
// add this pangolin to be the next animal (node) in the list
lion2->next = pangolin1;
// make the second lion the previous animal in the list
pangolin1->previous = lion2;
// create a 5 year old 400 pound adult male giraffe then make next node in the list
// make the pangolin the previous animal in the list
struct zooAnimal* giraffe1 = (struct zooAnimal*)malloc(sizeof(struct zooAnimal));
if (NULL == giraffe1)
{
printf("\n Giraffe creation failed \n");
return 1;
}
giraffe1->type = Giraffe;
giraffe1->sex = Male;
giraffe1->age = 5;
giraffe1->weight = 400;
giraffe1->next = NULL;
// add this giraffe to be the next animal (node) in the list
pangolin1->next = giraffe1;
// make the pangolin the previous animal in the list
giraffe1->previous = pangolin1;
// create a 2 year old 250 pound adult female zebra then make next node in the list
struct zooAnimal* zebra1 = (struct zooAnimal*)malloc(sizeof(struct zooAnimal));
if (NULL == zebra1)
{
printf("\n Zebra creation failed \n");
return 1;
}
zebra1->type = Zebra;
zebra1->sex = Female;
zebra1->age = 2;
zebra1->weight = 250;
zebra1->next = NULL;
// add this zebra to be the next animal (node) in the list
giraffe1->next = zebra1;
// make the giraffe the previous animal in the list
zebra1->previous = giraffe1;
Now that we have built our linked list of Zoo animals (nodes), we can start doing interesting things with the list. If we want to search the list for a specific animal, and print out the results of what we find, we would create a function like the following. Be sure to put the function outside of the MAIN function in our example C console application:
// function to search the list of animals to find a specific animal
// print out matching animals
void searchAnimals(enum AnimalType animalType, struct zooAnimal* animalList)
{
// loop through list, finding matching animals
while (animalList != NULL)
{
if (animalList->type == animalType) {
printf("%d year old, %d pound %s %s\n\n",
animalList->age,
animalList->weight,
getEnumNameAnimalSex(animalList->sex),
getEnumNameAnimalType(animalList->type));
}
animalList = animalList->next;
}
}
Then we can call the function like the following, searching to find all the Lions in our Zoo animal list. Since the zooKeeper pointer is pointing to the first Zoo animal (node) in our list, we use it to pass the linked list into the function:
printf("Search Results\n=================\n\n");
// search for specific animal type
searchAnimals(Lion, zooKeeper);
When we run the example C console application, this is what the output of this function will look like:
Next, we will show how to traverse the linked list moving forward through the list. We do this by referencing the NEXT pointer in each Zoo animal (node) of the list, and keep looping through the list until we encounter a NULL value for the next pointer.
printf("Traversing Animal List Forward!!\n=================================\n\n");
// traverse the linked list moving forward
while (zooKeeper != NULL) {
printf("%d year old, %d pound %s %s\n\n",
zooKeeper->age,
zooKeeper->weight,
getEnumNameAnimalSex(zooKeeper->sex),
getEnumNameAnimalType(zooKeeper->type));
zooKeeper = zooKeeper->next;
}
When we run our C console application, the output from this section of code will look like the following, showing all the animals on our Zoo animal linked list:
To traverse our Zoo animal list backwards, that is simple to do using our PREVIOUS pointer in each animal (node) in our list. First, we set the zooKeeper pointer to point to the last animal in the list, the Zebra. Then, we loop through the list until we encounter a NULL value for the zooKeeper pointer, like the following:
// set the zookeeper to the last animal (node) in the list, the Zebra
zooKeeper = zebra1;
printf("Traversing Animal List Backwards!!\n==================================\n\n");
// traverse the linked list moving backwards
while (zooKeeper != NULL) {
printf("%d year old, %d pound %s %s\n\n",
zooKeeper->age,
zooKeeper->weight,
getEnumNameAnimalSex(zooKeeper->sex),
getEnumNameAnimalType(zooKeeper->type));
zooKeeper = zooKeeper->previous;
}
When we run the C console application, the output from this section of code will look like the following:
// delete the pangolin from the list, and keep the list intact after delete
// set the previous animal (node) to pangolin next field to the pangolin next field
pangolin1->previous->next = pangolin1->next;
// set the next animal (node) to pangolin previous field to the pangolin previous field
pangolin1->next->previous = pangolin1->previous;
// delete the pangolin from the list
free(pangolin1);
// display the list after the delete operation
printf("List After Deletion of Pangolin!!\n=================================\n\n");
// reset zooKeeper to first element in the list, the first lion
zooKeeper = lion1;
// traverse the linked list moving forward after delete operation
while (zooKeeper != NULL) {
printf("%d year old, %d pound %s %s\n\n",
zooKeeper->age,
zooKeeper->weight,
getEnumNameAnimalSex(zooKeeper->sex),
getEnumNameAnimalType(zooKeeper->type));
zooKeeper = zooKeeper->next;
}
When we run our C console application, the output of this section of code will be the following, clearly showing that the Pangolin is no longer a part of the animal list.
Finally, at the end of the program, it is good form to make sure all of your memory allocations in your C program are freed up and no longer being used. This is done automatically by high level programming languages like Java and C# using a feature called "Garbage Collection". In most cases, however, memory must be freed up manually in C and C++ applications. Failure to free up memory can result in memory leaks. While minimal in a simple program like this example C console application, in larger C and C++ applications, memory leaks can become a serious performance issue.
// free the allocated memory for the zoo animals (nodes) free(lion1); free(lion2); free(giraffe1); free(zebra1); free(zooKeeper);
A Copy-And-Pastable Listing of our Entire C Example Application
// CLinkedList2.c // // By Michael G. Workman // // A simple C program demonstrating a Linked List using a Struct for a Zoo Animal // In this second version of this console app, we use a doubly linked list to emulate // animals in a zoo, and we create a function to search the list for certain animal types, // and also a delete operation that will delete a specific node, but keep the list intact // // This example freely distributable under terms of MIT open source license // https://opensource.org/licenses/MIT #include <stdio.h> #include <stdlib.h> // our animal types enum AnimalType { Lion, Giraffe, Zebra, Pangolin }; // our animal sex enum AnimalSex { Male, Female }; // data type to be used for each animal (node) in the linked list struct zooAnimal { enum AnimalType type; int weight; int age; enum AnimalSex sex; struct zooAnimal* next; struct zooAnimal* previous; }; // function to return the string name of Animal Type Enum const char* getEnumNameAnimalType(enum AnimalType animalType) { switch (animalType) { case Lion: return "Lion"; case Giraffe: return "Giraffe"; case Zebra: return "Zebra"; case Pangolin: return "Pangolin"; } } // function to return the string name of Animal Sex Enum const char* getEnumNameAnimalSex(enum AnimalSex animalSex) { switch (animalSex) { case Male: return "Male"; case Female: return "Female"; } } // function to search the list of animals to find a specific animal // print out matching animals void searchAnimals(enum AnimalType animalType, struct zooAnimal* animalList) { // loop through list, finding matching animals while (animalList != NULL) { if (animalList->type == animalType) { printf("%d year old, %d pound %s %s\n\n", animalList->age, animalList->weight, getEnumNameAnimalSex(animalList->sex), getEnumNameAnimalType(animalList->type)); } animalList = animalList->next; } } int main() { // we will have a zoo keeper var to point at specific animals in the list // starting with the first animal in the list struct zooAnimal* zooKeeper = NULL; // create a 3 year old 300 pound male lion, make start node of list struct zooAnimal* lion1 = (struct zooAnimal*)malloc(sizeof(struct zooAnimal)); if (NULL == lion1) { printf("\n Lion creation failed \n"); return 1; } lion1->type = Lion; lion1->sex = Male; lion1->age = 3; lion1->weight = 300; lion1->next = NULL; // since this is the first animal (node) in the list, there is no previous animal lion1->previous = NULL; // have the zoo keeper point to this first animal (node) in the list zooKeeper = lion1; // create a 1 year old 50 pound female lion cub then make next node in the list // make the first lion the previous animal in the list struct zooAnimal* lion2 = (struct zooAnimal*)malloc(sizeof(struct zooAnimal)); if (NULL == lion2) { printf("\n Lion creation failed \n"); return 1; } lion2->type = Lion; lion2->sex = Female; lion2->age = 1; lion2->weight = 50; lion2->next = NULL; // add this lion to be the next animal (node) in the list lion1->next = lion2; // make the first lion the previous animal in the list lion2->previous = lion1; // create a 3 year old 10 pound adult male pangolin then make next node in the list // make the second lion the previous animal in the list struct zooAnimal* pangolin1 = (struct zooAnimal*)malloc(sizeof(struct zooAnimal)); if (NULL == pangolin1) { printf("\n Pangolin creation failed \n"); return 1; } pangolin1->type = Pangolin; pangolin1->sex = Male; pangolin1->age = 3; pangolin1->weight = 10; pangolin1->next = NULL; // add this pangolin to be the next animal (node) in the list lion2->next = pangolin1; // make the second lion the previous animal in the list pangolin1->previous = lion2; // create a 5 year old 400 pound adult male giraffe then make next node in the list // make the pangolin the previous animal in the list struct zooAnimal* giraffe1 = (struct zooAnimal*)malloc(sizeof(struct zooAnimal)); if (NULL == giraffe1) { printf("\n Giraffe creation failed \n"); return 1; } giraffe1->type = Giraffe; giraffe1->sex = Male; giraffe1->age = 5; giraffe1->weight = 400; giraffe1->next = NULL; // add this giraffe to be the next animal (node) in the list pangolin1->next = giraffe1; // make the pangolin the previous animal in the list giraffe1->previous = pangolin1; // create a 2 year old 250 pound adult female zebra then make next node in the list struct zooAnimal* zebra1 = (struct zooAnimal*)malloc(sizeof(struct zooAnimal)); if (NULL == zebra1) { printf("\n Zebra creation failed \n"); return 1; } zebra1->type = Zebra; zebra1->sex = Female; zebra1->age = 2; zebra1->weight = 250; zebra1->next = NULL; // add this zebra to be the next animal (node) in the list giraffe1->next = zebra1; // make the giraffe the previous animal in the list zebra1->previous = giraffe1; printf("Search Results\n=================\n\n"); // search for specific animal type searchAnimals(Lion, zooKeeper); printf("Traversing Animal List Forward!!\n=================================\n\n"); // traverse the linked list moving forward while (zooKeeper != NULL) { printf("%d year old, %d pound %s %s\n\n", zooKeeper->age, zooKeeper->weight, getEnumNameAnimalSex(zooKeeper->sex), getEnumNameAnimalType(zooKeeper->type)); zooKeeper = zooKeeper->next; } // set the zookeeper to the last animal (node) in the list, the Zebra zooKeeper = zebra1; printf("Traversing Animal List Backwards!!\n==================================\n\n"); // traverse the linked list moving backwards while (zooKeeper != NULL) { printf("%d year old, %d pound %s %s\n\n", zooKeeper->age, zooKeeper->weight, getEnumNameAnimalSex(zooKeeper->sex), getEnumNameAnimalType(zooKeeper->type)); zooKeeper = zooKeeper->previous; } // delete the pangolin from the list, and keep the list intact after delete // set the previous animal (node) to pangolin next field to the pangolin next field pangolin1->previous->next = pangolin1->next; // set the next animal (node) to pangolin previous field to the pangolin previous field pangolin1->next->previous = pangolin1->previous; // delete the pangolin from the list free(pangolin1); // display the list after the delete operation printf("List After Deletion of Pangolin!!\n=================================\n\n"); // reset zooKeeper to first element in the list, the first lion zooKeeper = lion1; // traverse the linked list moving forward after delete operation while (zooKeeper != NULL) { printf("%d year old, %d pound %s %s\n\n", zooKeeper->age, zooKeeper->weight, getEnumNameAnimalSex(zooKeeper->sex), getEnumNameAnimalType(zooKeeper->type)); zooKeeper = zooKeeper->next; } // free the allocated memory for the zoo animals (nodes) free(lion1); free(lion2); free(giraffe1); free(zebra1); free(zooKeeper); return 0; }
This example C program was created on Microsoft Visual Studio IDE running on Windows 10. Microsoft Visual Studio Community Edition is a free download, while the Professional and Enterprise versions can be purchased. This example C program will run equally well on Unix and Linux with either the gcc compiler or the CLANG compiler.
For those who wish to try out and learn Unix, there is a NetBSD Unix shell account available from SDF at http://sdf.org for $9 every 3 months. Also, a free OpenBSD Unix shell account is available on https://tilde.institute. There is free Linux offerings on the internet as well. A free Ubuntu Linux shell account is available at https://tilde.team. Many Linux versions are available as free downloads on the internet as well.
I hope these examples have been very helpful for you to understand linked lists in the C Programming Language.To see my Curriculum Vitae, go to Michael G Workman CV
To see this project in Azure DevOps version control, go to C Linked List Example 2
To see all my projects on Azure DevOps, go to https://dev.azure.com/AbionTechnology/
To see my Posts and Answers on Stack Overflow,go to Michael G. Workman on Stack Overflow
If you have any questions about C, C++, Microsoft C# .NET, Microsoft Azure Cloud, Unix, Linux, and/or Mobile Apps, please feel free to contact me by email at:
michael.g.workman@outlook.com
