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 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 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.



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.



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.


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.


Next, we continue to build our linked list of zoo animals by creating Pangolin, Giraffe, and Zebra animals in our list, like the following:




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 console application:


Then we can call the function like the following, searching to find all the Lions in our animal list. Since the zooKeeper pointer is pointing to the first animal (node) in our list, we use it to pass the linked list into the function:


When we run the 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 animal (node) of the list, and keep looping through the list until we encounter a NULL value for the next pointer.


When we run our 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, and then we loop through the list until we encounter a NULL value for the zooKeeper pointer, like the following:


When we run the console application, the output from this section of code will look like the following:


Next, we will see how to delete an animal out of our list, and at the same time keep the list intact after the delete operation. This is simple to do, in this example we will delete the Pangolin from the list of animals. First we must reset our directional pointer variables, for the Giraffe animal, the previous animal was the Pangolin, but since we are deleting the Pangolin, we need to make the previous animal to the Giraffe to be the same previous animal as the Pangolin, in this case the second Lion. We also need to change the next animal for the second Lion from Pangolin to Giraffe. After doing that, we can then delete the Pangolin from memory, and next we will traverse our new animal list showing that the Pangolin is no longer in the list. We do this with the following code:


When we run our 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, it is good form to make sure all of your memory allocations in your C program are freed up and no longer being used by the program. This is done automatically by high level programming languages like Java and C# using a feature called "Garbage Collection", but in most cases, memory must be freed up manually in C and C++. Failure to free up memory can result in memory leaks, while minimal in a simple program like this example C console application, in larger applications memory leaks can become a serious performance issue.


The full version of this example C console application, in copy and pastable text, is available at my GitHub source code repository at the following link:

https://github.com/Michael-G-Workman/CLinkedList2/blob/master/CLinkedList2/CLinkedList2.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