The purpose of this assignment is to introduce you to dynamic memory allocation in C. You will also learn how to implement a singly-linked list data structure in C.
How do we allocate memory on the heap? How do we de-allocate it when it is no longer used?
In this assignment, you will be implementing a singly-linked list data structure. Your linked list nodes will have struct data (of type struct user*). You can find details about this struct and the fields it contains in the included list.h file. Your linked list will be able to add, remove, and mutate, and query the data stored within it.
You will be writing code in 1. list.c
The main.c file is included only for your own testing purposes.
You will be graded on your ability to implement the linked list data structure properly. Your implementation must be as described by each function’s documentation. Your code must manage memory correctly, meaning it must be free of memory leaks.
Note: A memory leak is when a block of memory is allocated for some purpose, and never de-allocated before the program loses all references to that block of memory.
2.1 Implementation Overview
You have been given one C file, list.c, in which to implement the linked list data structure. Implement all functions in this file. Each function has a block comment that describes its expected behavior.
Be sure not to modify any other files. Doing so will result in point deductions that the autograder will not reflect.
Remember that the struct data passed to certain functions (struct user *data) is malloc-ed data. However, this data is allocated separately from the node structs that contain it.
Forgetting to free this data when it is removed can cause memory leaks (memory that is no longer being used, but is never freed). Freeing memory when it should be returned to the struct user can created dangling pointers (memory that’s freed but still being referenced), causing use-after-free bugs. Keep both of these in mind when writing your code.
You are given a struct linked_list, which has a head pointer that points to the first node in the list and a size which represents the length of the linked list. You also have a struct node that has a next pointer
to the next node and also a struct user pointer that points to a struct user in memory. Refer to the following diagram for a visual representation of struct linked_list and struct node:
Once you’ve implemented the functions in the list.c file, or after implementing a few, compile your code using the provided Makefile. You may test your functions manually by writing your own test cases in the provided main.c, or run the autograder’s test suite. See the Testing section below for more information.
Please COMPILE OFTEN. The compiler will reveal many syntax errors that you would rather find early before making them over and over throughout your code. Waiting until the end to compile for the first time will cause big headaches when you are trying to debug code. We speak from experience when we say compile often. 🙂
2.2 Implementation Tips
- Helper functions: There are three helper functions defined in list.c. You should use them to your advantage. NOTE: As seen in list.c, the helper functions are static, which means they are not part of the file’s public interface and therefore will not be tested by the autograder. Improper implementations of these helpers may cause other tests to fail, so be sure to check them if your other functions fail any tests.
- Push/add functions: For these functions, make sure to read the documentation about what to do when malloc fails. In most cases, this means that you need to return 1 to indicate something went wrong.
- Pop/remove functions: As we mentioned, you should free things that are no longer used to avoid memory leak, but you also don’t want to free prematurely. Here, the potential candidates for freeing are: the nodes, the struct user data inside the node, and the pointers inside the struct user. Think carefully about what you’re doing in these functions (hint: look at return type) and figure out what should be freed.