Homework 2: Linked List

Due Monday, July 3, 2023 at 11:59pm

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

Synopsis

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

lib/src/readline.c: You will copy your implementation of readline from last homework to here. If you do not have a working implementation, you can use mine in the solution once it is published.

lib/src/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 lib/include/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

We will keep using the coursework repository, same repository where you wrote hw0. First of all, you should run git status to see if you have any uncommitted changes; if so, commit and push them before proceeding.

Run git pull upstream main. Doing this almost certainly triggers an automerge by git. When vim is launched that shows the merge commit message, press <esc> : x <enter> to save and quit the editor (look at the bottom-left corner of your screen if you don't know where you're typing).

Run ls to confirm that you have received a lib directory.

Pay attention to any error messages that you might encounter and please ask for help if you run into any problems.

What have we provided to you?

The lib directory is organized as follows:

• include/ contains all .h header files. They define the interface of the modules and it is what the user #includes when using this library.
• src/ contains all .c files implementing those .h files. They contain the implementation of the functions declared in the header files. Usually, for every .c file in src, there is a .h file in include with the same name.
• unittests/ contains all unit-testing code for the modules. They use the tests.h framework in this library. After running make test, the unit tests are turned into executables that live in bin/.
• bin/ contains the produced unit tests executable to run.
• lib/ contains the produced library.
• Makefile is the Makefile that specifies how to build this library.
• test_all.sh is a Bash script that runs all tests in bin/.

Before you start, read through unittests/linked-list-test.c and understand the interface fully before you start implementing.

Running unit tests

No more Criterion! I built a minimalist testing framework (see include/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 unittests/linked-list-test.c are testing so that when your implementation fails a test, you know where to debug.

After running make test, you should see the bin directory populated with the unit tests. Run them 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.

Specification

Your first task is to copy your implementation of readline into lib/src/readline.c.

The specification of linked-list is documented in the header file. If anything is uncleared, please let me know.

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.
6. llist_copy, which returns a newly-allocated list containing the same elements.
7. llist_remove_at, which removes an element at a given index.
8. llist_insert_at, which adds an element at a given index.

The unit tests are also ordered this way.

Written

You need to answer some questions in hw2/WRITTEN.txt.

Submission checklist

In lib/:

• src/linked-list.c contains your implementation of the linked-list module.
• src/readline.c contains your implementation of the readline function.
• make lib and make test produce no errors.

In hw2/:

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