Guided: Build a Linked List in C

The linked list is a foundational data structure in computer science. In this lab, you are going to implement your own linked list in C! Along the way, you’ll deepen your understanding of both C and custom data structures.

Linked lists are important to learn when it comes to programming in C for a number of reasons. Firstly, linked lists serve as the foundation for more complex, higher-level data structures that you want to create in C like stacks, queues, and even tree structures. On top of this, linked lists serve as a dynamic data structure. This is really helpful in C because it means you now have a collection that can grow or shrink dynamically unlike static arrays that have a fixed size.

So, what exactly is a linked list? A linked list is a custom data structure that contains a series of nodes – each of which is its own struct that contains a piece of data and a pointer to the next node in the list. Most linked lists have a “root” node or “head” node which is the first node in the list and a “tail” node that typically points to NULL - a null pointer.

Some linked lists are singly linked lists, meaning that each node in the list only points to the next node in the list. But some linked lists are doubly linked lists in that they have two pointers – one to the next node in the list and one to the previous node in the list. There are other types of linked lists as well, like circular linked lists, but in this lab, you are going to focus on building a singly linked list.

Overall, linked lists are great to implement in C, if only for the pure educational value. In the next step, you will begin creating your own linked list.

info> Note: The solution directory contains the final solution. Feel free to view the file in that directory should you get stuck!

To start creating a linked list in C, you must first create the structure of the linked list so that you can fully define what a linked list is and what it does. Our linked list will actually consist of two different structures – the LinkedList and the LinkedListNode struct. It is generally advised to create a linked list via two different structs with one struct acting as the high-level list struct and the other governing the key aspects of elements or nodes within the list.

In this step, you are going to be looking at the linked_list.h header file and implement the two structs, as well as couple of the methods defined therein. You'll start by implementing the LinkedList struct in your own linked_list.c file. From there, you’ll implement the LinkedListNode struct. You’ll finish this step by implementing both the list_init and list_destroy functions that act as helpers for creating your linked list and freeing up its memory when you’re done using it. When it comes to implementing the linked list data structure, there are two C structs that you will need to create. The first struct, LinkedList, serves at the primary gateway into the usage of the data structure. This struct is accompanied by the inner, LinkedListNode struct which serves as an abstraction on top of the elements contained within the linked list.

The LinkedList data structure typically contains 3 crucial fields:

• A length or size field that contains the current count of elements or nodes in the linked list.

• A head field that points to the first node in the list.

• A tail field that points to the last node in the list.

In addition, the linked list you are implementing comes pre-defined as accepting a destroy field that contains a function pointer. This function is user-defined and dictates how LinkedListNodes will have their data memory freed. It is a good practice to leave this up to the calling code or consumer of your linked list. Elements in a linked list (in this case a singly linked list) typically contain two crucial fields or properties. They include:

• A next field that points to the next node/element in the linked list

• A data field that points to the data contained within the node. The data field should usually be a void pointer so as to indicate that the nodes can point to any generic type of data. Now that you have created the basic structure of your linked list, it is time to start implementing its API surface. The first two methods you will need to implement that will work with your new linked list type are the list_init and list_destroy functions. These functions are helpers that will create a linked list and free up its memory respectively.

The list_init function should receive two arguments. Firstly, it should receive a linked list pointer and secondly it should accept a function pointer that points to the custom data destruction function that will be used to clean up a linked list node’s data. From there, the list_init function should simply initialize a given list. This linked list might be a stack-allocated list or a dynamically allocated linked list – this is up to the calling code. You have governed how a linked list will be initialized. Now it’s time to implement how a linked list will be destroyed or, essentially, have its memory freed up. This function will actually rely upon another function that you will implement in the next step – the list_remove function which is responsible for removing a node from the linked list.

Great! You can create and destroy your linked list... but no linked list would be complete without the ability to add or remove nodes to it. In this step, you’re going to make your linked list usable by allowing users to add and remove nodes. You will achieve this by first implementing the list_insert function that should insert a node to the end of the list. From there, you will implement the list_remove function which should traverse your linked list and remove a given node. The list_insert function is crucial to operating a linked list as it’s going to be the way that you add connected nodes to the list. The list_insert function accepts three arguments:

• A LinkedList pointer

• A LinkedListNode pointer that points to the node just before where your new node should exist in the linked list.

• A data pointer that should point to the data that will be contained with your new node.

The list_insert function can be complicated. Most of it is implemented for you including the allocation of memory for a new node and handling the case where the new node is the first node in the linked list. Great! You’ve implemented the list_insert function that will add a new node to your linked list after a given node. Now it’s time to add the ability to remove the next node from the list given a node. This function is even a bit more complicated than the list_insert function. But don’t worry, most of it is implemented for you as there are some edge cases to be aware of including:

• Handling the case of an empty linked list

• Handling the case where you want to remove the first node in the list.

You now have a simple, yet functioning, linked list to work with! Now it’s time to see how the linked list fits in to a real program. In this step, you will take your linked list that you have implemented and populate it with data from a file!

You’ll start by creating a linked list using the code you wrote in prior steps. From there, you will implement a loop that will consume text from a file line by and line and start populating your linked list. You’ll do this by inserting nodes using the function that you implemented in the last step. The while loop is a go-to mechanism for reading lines of text from a file in conjunction with the getline function provided by the standard library. The linked list is a nice data structure to use when it comes to storing sequential lines of text especially when used in combination with the strdup function for duplicating strings. In this task next task, the conditional portion of the while loop is already setup for you.

Now that you have a linked list that contains data, it’s time to visualize that data along with the linked list that contains it. This is one of the beautiful things about custom data structures: you can tailor make them to fit your specific use case.

In this step, you are going to add the ability to print your linked list to the terminal. You’ll start by defining a new print function within the linked_list.h header file. From there, you’ll implement the print function as well as add a new print_list_size function – demonstrating just one of the many functions you can implement on your new linked list. There are many more functions that you can add to make your linked list more robust. One of the most helpful functions you can add to the API would be the print_list function.

Nicely done! You’ve made it to the end of this guided code lab on how to build a linked list in C.

In summary, you learned:

• What linked lists are and why they are so important
• How to build the basic structure of a linked list
• How to implement the functionality of a linked list

You’ve barely scratched the surface in terms of building data structures in C. As follow on learning, I recommend that you learn some of the more advanced topics when it comes to implementing data structures in C. Here are a just a few:

• Stacks
• Queues
• Binary Trees

From here, you can be confident when it comes to using linked lists to help you implement higher-level data structures in C. I recommend that you continue your journey learning C by pursuing both video courses and more guided code labs here, at PluralSight.