Now that we know about pointers and structs, we can make a linked list. A linked list is a dynamic data structure, meaning that it can change in size! There are several important points that we are going to go over in this post.
1. Nodes. Nodes are the individual data points in a larger structure. In our case, a struct is going to be our node.
2. Dynamic memory allocation. A dynamic data structure means that nodes will be created on destroyed on demand. Dynamic memory allocation means that memory will be allocated or released as needed, typically for the insertion and removal of nodes.
3. Insert. If you can’t create nodes in a linked list, then there is little reason to use one. Insert will create a node, allocate memory, and then place the node into our linked list in a predetermined format. In our case, insert is going to place node in order.
4. Delete. Delete goes alongside insert. We can input a node, and delete will remove it from our linked list, deallocate the selected node’s memory, and adjust the linked list accordingly.
5. Print. Print is fairly self-explanatory. We can print out the information of our linked list, with the print function going through each node, and printing out chosen information. Print isn’t an essential function of linked lists, but without it, it is hard to see what is going on in the linked list.
With these functions, our linked list will have all the basic functionality we need to show how linked lists work.
Because the size of this project is larger than the struct and pointer blog posts, we are going to divide the project into “header.h”, “main.c”, and “project.c” files. Splitting a project into multiple files is done to increase readability. Our linked list project is still fairly small, so having only 3 files is more than enough.
Main’s only purpose is to call the menu functon. The menu calls the other functions we use for the linked list: insert, delete, and print.
A header file contains definitions and declarations that are essential to the C program. We use #include in the header to get important libraries.
We can see the struct declaration in the header, for simplicity’s, we are just going to have two variables in the struct: an int, and a struct pointer. Below the struct we have “typedef Node *NodePtr;”, we’re declaring a variable that is a pointer to a Node, this may seem confusing, but will be easier down the road.
There are also function prototypes in the header file, learn more about these here.
Note: Some compilers will raise an error about gets. If that is the case, there is commented out code in the header file that needs to be uncommented.
Nodes. This is the very basis of a linked list. In our case, we are going to use a struct that has just two variables; a value (int), and next (struct ptr). Next is what allows us to create linked list, because we know about pointers and structs, we can combine the two to make a struct which points to another struct.
Dynamic memory allocation. When using linked lists in C, we must be sure allocate and deallocate memory. We need memory to persist throughout different function calls, but we don’t want to allocate a set of memory just for the linked list to use. If we do this, there is the possibility of not having enough memory, and the possibility of having allocated too much! To fix this problem, we use malloc and free! Malloc stands for memory allocate, which sets aside memory for a variable. Within the call of malloc, we must include the size of the memory we want to allocate, in this case we just use the “sizeof()” function. In our code, we call malloc like this:
Free is the opposite of malloc. We use this to remove the memory we allocated by malloc. If we don’t free our memory, eventually there are going to be memory problems. Calling free as function is much easier than using malloc, to free up a node, we just use free(delnode), with delnode being a node we selected for deleting. This can be seen later in the post.
Menu. Menu is designed for us to create a interaction between us and the linked list, allowing us to check out different cases of the linked list. All the functions in the “project.c” file will have a description and it’s code printed out, but if you just want to check out all the code at once, click here.
Menu is divided into three sections.
First, we have variable declarations. The most important is NodePtr, as this is our linked list. The other variables are used focused assigning information to the linked list and keeping the menu running.
Second, there are printf functions, this prints out the menu values, and below that, we have a prompt that asks us to “Enter a Command Val:”, which asks for a character between the values 1 and 4.
Third, the last part is a switch statement. taking the command we entered in earlier in the code, we then call insert, delete, or print. For insert and delete we ask for a value before we call these functions.
Insert. Insert is used to create and place a node in the linked list.
We create three NodePtrs, and use malloc on newNode, but leave prevNode and currNode alone. The reason behind this is prevNode (previous) and currNode (current) are going to be pre-existing nodes that have already had memory allocated for them. We then assign list (our from menu) to currNode. We then traverse through list until our value is less than the value on the next node. To insert the newNode, we will assign prevPtr’s next node to newNode, and the assign newNode’s next node to currNode.
This is much easier to show visually. Before we insert newNode into the linked list, prevNode and currNode are contiguously linked, and after insert, newNode is placed in between prevNode and currNode.
There are a few special cases, but the most important one is when the linked list is the front of a list (or empty). If this is the case, all we do is assign newNode’s next to list, and then assign list to newNode.
Delete. If you understand insert, delete is just the inverse of insert. Given an input value, we then search through the linked list and delete the node if we find it.
Delete checks if the list exists, then has 2 cases.
1. The node to be deleted is the first node in the list. If this is the case, we just assign list to be the next value of the first node, then we free first node.
2. The node to be deleted is not the first node in the list. Here, we do the opposite of insert, we assign the previous node’s next to the current nodes next, and then free current node (which has been assigned to temp).
If you understand how we traverse through the linked list in insert and delete, then print is pretty easy. While our linked list is not empty, we print out our node->value, and then move to the next node. (That’s it!)
Let’s check out what happens when we run this code!
The first section is us inserting a node into the list (with a given value of 5). The second is printing out the values of the linked list. I added the value “4” before the screenshot, to make the link list a bit larger.
Linked Lists can be scary and hard to debug. But if you understand what is going on, they become much simpler. Using a pointer to node as the structure in our list does help simplify our pointers to a more manageable level.
A linked list is just the start of a larger group of objects called “data structures”, which include “stacks”, “queues”, and “binary search trees”. All these data structures have their advantages and disadvantages, but linked lists are the basis for all of these!