Using Linked Lists In The C Programming Language - PART 1
The C Programming Language was a revolutionary programming language when it first came out in the 1970's, it made programming the new Unix systems made by AT&T simple, straightforward, and powerful. It was a leaps and bounds improvement over programming computers in Assembly Language and Basic. It was first developed by the computer scientist Dennis Ritchie, working at the time at Bell Labs. Ritchie was also instrumental in the development of the Unix Operating System with fellow computer scientist Ken Thompson. The C Programming Language became a critical component for Unix systems of the time, and even to this day. C is also a critical component of Unix-like OS's such as Linux and Android.
Ken Thompson (left) and Dennis Ritchie (right)
Another big use of the C programming language is in embedded systems and programmable logic controllers (PLC). Other computing systems widely use C as well, including Arduino and Raspberry Pi microcontrollers. Also, some PLC devices have their own proprietary programming languages and development environments, but are still loosely based upon C. An example of this is PLC devices created by Rockwell Automation, which use the RSLogix Development Environment to develop software with. PLCs are widely used in manufacturing, in particular automotive manufacturing, and are also used in the US Space Program.
Dennis Ritchie even had an impact on the massive smartphone revolution that began in 2007 with the introduction of the iPhone. iPhone apps were initially, and even today, created using the Objective-C Programming Language, which is an extension of the C Programming Language. Objective C was an obscure and little known programming language until Steve Jobs brought it to Apple from his previous role at NeXt Computers. Now, Objective-C powers hundreds of thousands of mobile devices all around the world.
C, however, has one disadvantage, data types such as arrays have to know their exact size when being declared, they cannot be dynamic in size. This has been a long time limitation of C, but a method was developed to create dynamic data types using pointers and struct types called a Linked List, which became very useful in C programming. In this blog post, we will implement a simple C program using a Linked List to emulate the animals in a Zoo.
I used Microsoft Visual Studio on Windows 10 to develop this C application, which lets you develop C and C++ software as well as Microsoft C# .NET. Also, if you are using a Linux or Mac computer, there is a version of Visual Studio for those platforms called Microsoft Visual Studio Code, which will also let you do C and C++. However, if you are not a fan of Microsoft like some open source developers, there are other options besides Microsoft. There is an excellent Eclipse C++ IDE that is written in Java and can run on both Windows and Unix/Linux systems. And also, there is the GCC compiler from GNU that will let you compile C and C++ programs from the command line. All excellent options for developing C and C++ software.
It is completely possible to develop C programs using a C++ development environment. C++ is backwardly compatible with C. However, C is not upwardly compatible with C++. You can compile a C program with a C++ compiler, but you cannot compile a C++ program with a C compiler.
When I first started working in the Space Shuttle Program, I was tasked with maintaining C programs on Hewlett Packard HP-UX Unix workstations running the Common Desktop Environment (CDE), and that had UI with XWindows and also used linked lists for data traversal. These programs would be built using Oracle Pro-C pre-compilers to embed SQL Statements in the C code. The applications would access data on the Shuttle Data Center (SDC) Oracle data warehouse used for Space Shuttle launch data. At that time, I once created a C application that had over 100 pointers in it. I was always worried the application would fail in some spectacular manner, but it never did. The aerospace engineers that used it were happy with its functionality.
In the first part of our C program, we will add include files and also two enums. One for animal type, and one for animal sex, like in the following code:
#include <stdio.h>
#include <stdlib.h>
// our animal types
enum AnimalType {
Lion,
Giraffe,
Zebra,
Pangolin
};
// our animal sex
enum AnimalSex {
Male,
Female
};
Next, we will create our STRUCT that will be data element (node) in our Linked List. In this case, our STRUCT will be used to emulate an animal in a Zoo. Note that we have a pointer called NEXT in this struct. That is what we will use to link to other Zoo animals (nodes) in the list. Pointers are what are used to create Linked Lists, and they hold the list together.
// 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;
};
Next, we will add functions for turning the enum values into readable strings. As a low level programming language, C does not by default allow you to reference enum property names in a string, only the corresponding integer value of that particular enum property So, to get the string names of the enum properties, we will have these simple functions to do that purpose for us.
// 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 start working with and building our Linked List for Zoo animals. In the first part of our main method, we will declare a pointer variable called ZOOKEEPER, which we will use to traverse the list of animals. Then after that, we will create our first animal, or node, by first allocating memory for the STRUCT, then casting that allocated memory to the type of the struct, and then creating a pointer that points to this allocated memory. This is a very low level way of declaring a variable not normally done in higher level programming languages like Java or C#. Note that for now, the NEXT value is null, because there is not yet more than one animal (node) in the list to be the next animal (node) in the list. Since this is the first animal in our list, we want to set the zooKeeper pointer variable to this animal (node). This is where we will start when we traverse the Linked List.
// we will use this zooKeeper variable to traverse the linked list of Zoo animals
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;
// the zoo keeper starts with this lion before going through the list of animals
zooKeeper = lion1;
Next, we will add the second animal (node) to our list, another Lion. We do this like in the following code. Note at the end, we are setting the NEXT pointer of the first animal, lion1, to point to this second animal (node), lion2. This is the standard method of building a Linked List.
// create a 1 year old 50 pound female lion cub then make next node 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;
We will continue to add three more Zoo animals (nodes) to the list in this manner, a Pangolin, a Giraffe, and a Zebra. When we are done, we will have 5 Zoo animals (nodes) in our list.
Once we are done with the list, we can start the important part of having our zooKeeper traverse the list, visiting each animal in the list. This is a very simple method, we just continue looping through the list as long as the NEXT pointer value is not null, meaning that there is another animal in the list. With each loop iteration we set the zooKeeper variable to point to the next animal in the list, until there are no more animals in the list, where NEXT is NULL (!=0). Also with each loop iteration, we will print out information on the current animal the zooKeeper is pointing to in the list.
// the zoo keeper will now traverse the list of zoo animals (nodes) until reaching the end
while (zooKeeper != 0) {
// print out info on the current zoo animal (node) the zoo keeper is dealing with
printf("%d year old, %d pound %s %s\n\n",
zooKeeper->age,
zooKeeper->weight,
getEnumNameAnimalSex(zooKeeper->sex),
getEnumNameAnimalType(zooKeeper->type));
// move to the next zoo animal (node) in the list
zooKeeper = zooKeeper->next;
}
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.
// deallocate memory for zoo animals free(lion1); free(lion2); free(pangolin1); free(giraffe1); free(zebra1); free(zooKeeper);
Our output from this simple C program will look like this when we run the program.
A Copy-And-Pastable Listing of our Entire C Example Application
// CLinkedList.c // // By Michael G. Workman // // A simple C program demonstrating a Linked List using a Struct for a Zoo Animal // In the first part, we demonstrate a singly linked list with zoo animals as the nodes // // 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; }; // 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"; } } int main() { // we will use this zooKeeper variable to traverse the linked list of Zoo animals 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; // the zoo keeper starts with this lion before going through the list of animals zooKeeper = lion1; // create a 1 year old 50 pound female lion cub then make next node 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; // create a 3 year old 10 pound adult male pangolin then make next node 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; // create a 5 year old 400 pound adult male giraffe then make next node 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; // 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; // the zoo keeper will now traverse the list of zoo animals (nodes) until reaching the end while (zooKeeper != 0) { // print out info on the current zoo animal (node) the zoo keeper is dealing with printf("%d year old, %d pound %s %s\n\n", zooKeeper->age, zooKeeper->weight, getEnumNameAnimalSex(zooKeeper->sex), getEnumNameAnimalType(zooKeeper->type)); // move to the next zoo animal (node) in the list zooKeeper = zooKeeper->next; } // deallocate memory for zoo animals free(lion1); free(lion2); free(pangolin1); free(giraffe1); free(zebra1); free(zooKeeper); return 0; }
So, that is just a simple example of working with a Linked List. In this example, we are using what is called a Singly Linked List, since it only contains one directional pointer to traverse the list. Other kinds of Linked Lists include the Doubly Linked List. Which includes two directional pointers in each struct element, one pointing to the previous node, and one pointing to the next node. These kinds of lists can be traversed in both directions, not just forward. In a future blog post, I will show how to traverse a linked list in both directions, and also show how to search a linked list for a particular node, and also, show how to delete a node from a linked list and at the same time keep that Linked List intact.
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 1
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
