Homework 4: Linked List

Due Monday, July 15, 2024 at 11:59pm

In this assignment, you will implement a linked list in C.

Synopsis

In this homework, you will work in the hw4 directory.

hw4/linked-list.c: The majority of code you are going to write for this assignment lives in this file. This file should implementation the header file at hw4/linked-list.h.

Written: You will answer some simple questions at the end.

Learning Objectives:

• Even more pointer juggling
• Implement your first data structure
• Practice heap allocation and manual memory management

Getting started

See homework 1.

What is provided?

The hw4 directory contains the following files:

• Makefile is a Makefile that specifies how to build this homework.
• linked-list.h is the header file for the linked list module. It contains the declarations and descriptions of all functions in this module.
• linked-list.c is where you write your implementation of this linked list module.
• linked-list-test.c contains unit tests for your implementation, organized in the suggested order of implementation.
• tests.{c,h} is a unit test framework that I use for this class. You can read them if you are curious.
• Please ignore memcheck.supp.
• WRITTEN.txt

Makefile

A Makefile is a powerful tool used primarily for managing the build process of software projects. It works with the make utility, which automatically builds executable programs and libraries from source code by reading files called Makefiles.

Makefile can be very complicated and it has a lot of potentials. For this assignment, you only need to know the following three commands:

• make linked-list-test, or simply make, builds a linked-list-test executable.
• make clean cleans up all files produced by make linked-list-test.

As with all the previous assignments, all your C code needs to be built with -Wall -Wextra -pedantic -std=c11. This is also what is specified in the Makefile.

You should run make now to see if you are able to create all the executables without errors although running these executables will almost certainly not work.

Running unit tests

For this class, I built a minimalist testing framework (see tests.h for more detail).

While you are not required to write any tests for this assignment, you need to understand what the tests in linked-list-test.c are testing so that when your implementation fails a test, you know where to debug.

After running make, you should see an executable named linked-list-test. Run it as you would with any other executable, e.g. ./linked-list-test, and don't forget to run valgrind ./linked-list-test to check for memory leaks/errors.

The executables using the testing framework takes the following command-line arguments:

• --capture: without this option, if your implementation crashes, the test program also crashes. This is useful when you want to use valgrind to figure out which functions/lines in your code cause the crash. With --capture, the test program will not crash but report the test as FAILED.
• --keep-going: without this option, the test program will stop at the first failed test. --keep-going tells the program to run all tests even after some tests failed.
• -h: prints a short usage message.

Specification

The specification of linked-list is documented in the header file linked-list.h and duplicated in linked-list.c for convenience.

Linked List Review

A linked list is a dynamic data structure composed of nodes. Each node contains a piece of data and a reference to the next node. In this module, a node is defined as follows:

struct llist {
    void *elem;         // Pointer to the data
    struct llist *next; // Pointer to the next node
};

The end of a linked list is signaled by having next == NULL.

Who owns the data?

For this data structure, the client (a.k.a the user) of the data structure owns the data.

This linked list uses a boxed approach as it stores pointers to data owned externally:

• Boxed --- Nodes store pointers to client-managed data. It is the responsibility of the client to allocate and deallocate the data. The list only handles the nodes pointing to this data.
• Unboxed --- Data would be stored directly in the nodes, leading to potentially faster access. Freeing the data structure also deallocates the data. An example of this is the array-list implementation from Week 4's in-class demo.

Memory Management

Nodes are dynamically allocated and freed. To construct a node with the client's data, data (of type void *), and the rest of the list, list (of type struct llist *), the following snippet allocates a new node:

struct llist *node = malloc(sizeof(struct llist));
node->elem = data;
node->next = list;

When the node is no longer needed, its memory should be freed:

void *data = node->elem;
struct llist *rest_of_list = node->next;
free(node);

Provided Implementations

A function is provided to construct a linked list quickly, given a list of data:

struct llist *llist_list(void *x, ...);

For example,

struct llist *my_list = llist_list("hello", "world", NULL);

             +---------+  +-->+---------+
             | "hello" |  |   | "world" |
 my_list --> +---------+  |   +---------+
             | next    |--+   | next    |-->NULL
             +---------+      +---------+

You do not need to understand the implementation of this function to proceed.

llist_print, llist_copy, and llist_reverse are implemented as an example at the end of linked-list.c. You should read and understand the code because they might provide hints for how you might implement the other functions.

Suggested order of functions to implement

1. llist_free, which releases the memory taken by the linked list.
2. llist_prepend, which adds an element to the front of the list.
3. llist_len, which returns the length of the linked list.
4. llist_concat, which concatenates two linked lists.
5. llist_append, which adds an element to the back of the list. elements.
6. llist_remove_at, which removes an element at a given index.
7. llist_insert_at, which adds an element at a given index.

The unit tests in linked-list-test.c are also listed in this order. You should read how each function is tested before implementing it.

Testing

make builds all components in this assignment, and ./linked-list-test runs all tests.

For Linux users and Windows users using Windows Subsystem for Linux (WSL), you should check for memory leaks and errors using valgrind as usual.

valgrind ./linked-list-test

valgrind --leak-check=full ./linked-list-test

Running Address Sanitizer for MacOS Users (Experimental)

On MacOS, Valgrind is no longer supported. The LLVM compiler infrastructure, of which clang is a part, provides a similar tool called AddressSanitizer (ASan). Similar to Valgrind, ASan checks for memory erros and memory leaks.

Running ASan is (needlessly) complicated. However, the provided Makefile has a rule memcheck that runs your program with ASan. For MacOS users who wish to write and run code locally, you should run

make memcheck

Gradescope will continue to use Valgrind to check for memory errors and leaks. If the two tools differ, we use the results from Valgrind.

Written

You need to answer some conceptual questions in hw4/WRITTEN.txt.

Submission checklist

• linked-list.c contains your implementation of a linked list, specified in linked-list.h.
• make linked-list-test reports no errors or warnings.
• WRITTEN.md is finished.
• All changes are committed and pushed to your github repository

Submit your program to Gradescope by selecting your coursework directory and the correct branch.

Grading

Warning: If your program cannot be compiled using the commands above without error or warning, you will receive 0 points in correctness since there is no executables for us to run.