Using Linked Lists In The C Programming Language

The C Programming Language was a revolutionary programming language when it 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, and 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, small computing devices such as programmable logic controllers (PLC), and other small computing systems widely use C. 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 and 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:



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 animals (nodes) in the list. Pointers are what are used to create Linked Lists, and they hold the list together.




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.




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. 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), since this is where we will start when we traverse the Linked List.




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 prime method of building a Linked List.




We will continue to add three more animals (nodes) to the list in this manner, a Pangolin, a Giraffe, and a Zebra, when we are done we will have 5 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.

Our code to do this will look like the following:




Note that when we are done with our animals (nodes) in our list, it is considered good form to free the allocated memory for each node so they do not create a memory leak in the computer we are using. High level programming languages like Java and C# do this automatically with a feature called 'Garbage Collection', but with C and C++, in most cases it has to be done manually. We do this task with the following code:



Our output from this simple C program will look like this when we run the program.




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.

A full listing of the source code for this C program can be found on my GitHub source repository at the following link:

https://github.com/Michael-G-Workman/CLinkedList/blob/master/CLinkedList/CLinkedList.c

If you have any questions about CC++Microsoft C# .NET, and/or Microsoft Azure Cloud, feel free to contact me by email at michael DOT g DOT workman AT gmail DOT COM.

Comments

Popular Posts