Lab: Linked Lists

Today’s lab will guide you through a complete linked list implementation. You’ll have two days to complete this work, but you may also need time to work on this lab outside of class depending on how comfortable you are working with pointers and malloc.

To get started, download a copy of the starter code archive: linked-lists.tar.gz. Then, run the following commands:

$ cd csc161/labs
$ tar xvzf ~/Downloads/linked-lists.tar.gz
$ cd linked-lists

Note on Drivers: Alternate drivers for each problem A, B, etc.

A. Getting our Bearings

Review the provided starter code to get a sense of what you’re implementing. You’ll want to look at all three files. Here is a high-level summary of what you’ll find in each:

main.c

The program’s main function and some general utilities. The provided code includes a simple command interface to interact with a linked list.

string_list.h

The interface for a linked list that holds strings. The provided code includes definitions of two important struct types and declarations of all the functions that operate on string lists.

string_list.c

The implementation of a string list, which you will fill in for this lab. Only one function, string_list_init, is completed for you.

You’ll want to pay close attention to the two struct types defined in string_list.h: string_node_t and string_list_t. The string_node_t type holds a single node of a linked list that stores strings, while the string_list_t type encapsulates an entire list. It may seem odd to create a struct with a single field, but doing this for string_list_t helps avoid an otherwise confusing double pointer you’d have to deal with for all of the list functions you’ll implement.

You can compile the project with make and run the list-practice program to see what the program will eventually be able to do, although many functions are just placeholders for now. The provided Makefile also creates a list-practice-asan program that’s built with AddressSanitizer to make it easy for you to test your code with more thorough memory error detection. The AddressSanitizer version will fail with errors until you’ve completed part D of the lab, but after that, you should be able to run the AddressSanitizer version with no reported errors.

Spend as much time as you need to review the provided code, and ask questions if you’re unsure about any of the functions or types before moving on. Focus on the functions and types declared in string_list.h; it isn’t critical that you are entirely comfortable with the command processing loop in main, although there should be enough comments for you to make sense of it.

B. Inserting at the Front of a List

One of the basic operations we’ll perform on linked lists is to add elements to the list, and it’s easiest to do this by adding a value to the front of the list. You’ll implement this functionality in the string_list_insert function in string_list.c.

To add an element to the front of a list you will need to do several things:

1. Allocate space to hold a string_node_t that will become part of the list.
2. Put the inserted value in the new node
3. Set the new node’s next field so it points to the old head of the list.
4. Set the list’s head to be the new node you just filled in

Complete the two exercises below.

Exercises

1. Consider how you will handle inserting at the beginning of an empty list. Does this case need to be handled differently from inserting at the front of a non-empty list? Explain your thinking in comments within the string_list_insert function.

2. Complete an implementation of the string_list_insert function. Test it to make sure it doesn’t crash, although you won’t be able to see its effect until you can print the list in the next part of the lab.

C. Printing and Getting the Length of a List

Next, you’ll implement two functions to look at the contents of a list. The string_list_print function prints each string in the list and then returns. The string_list_length function counts the number of nodes in the list and returns that value.

In both cases, you’ll need to traverse the linked list. To do this, you’ll need to create a string_node_t* “cursor” that points to the first node in the list. Then loop over the whole list, advancing the cursor to the next node on each iteration. You’ll know you’ve reached the end of the list when the cursor is NULL.

Exercises

1. Implement the string_list_length function.
2. Implement the string_list_print function.
3. Test both functions using your string_list_insert function. Here is an example of what you should see if everything is working correctly:

   $ ./list-practice
   Enter a command. Type "help" to see available options.
   > insert first
   > insert second
   > insert third
   > print
   third
   second
   first
   > length
   length = 3
   

D. Destroying a List

At this point, you have a program that calls malloc quite a few times, but it never frees any memory (except one call to free in main). The provided code calls string_list_destroy just before the program exits, though. You’ll fill this function in with code to free all allocated memory in the list.

There are a few details you need to keep track of:

1. You will need to free the space that stores each node of the list. That means you’ll need to traverse the list, much like you did in the previous part of the lab.
2. Additionally, each string held in the list is an owning pointer of that memory, so you need to free each string. We can tell this is an owning pointer because it is written in the documentation comments in string_list.c. You can also see that the string passed to string_list_insert is the result of a strdup call in main.
3. Once you free a node you cannot access it. If you need values of any fields within the node you’ll need to copy them to local variables before you free the node.

Exercises

1. Implement string_list_destroy. Don’t forget to set lst->head to NULL when you’re done, just in case someone who uses this code later forgets the list has been destroyed.
2. Try running tests on the program, but use the list-practice-asan version. You should be able to run from start to finish with no AddressSanitizer errors. Be prepared to deal with memory leaks (things you forgot to free) and use-after-free errors.
3. Write down at least one interaction with the program that shows how you tested your code.

E. Appending to the End of a List

Sometimes we want to add values to the end of a list instead of the beginning. For linked lists, this takes a little more work. You’ll need to travel to the end of the list and attach a new node there.

You still need to request space for the new node using malloc, just as you did in string_list_insert, but the actual connection into the list will look different. Instead of changing the head of the list, you have to find the last node in the list and change its next pointer. This will change the loop you write to traverse the list, although you’ll likely want to start with a loop like the ones you wrote in string_list_length and string_list_print.

Exercises

1. Implement string_list_append.
2. Test your implementation and make sure it works correctly. You should test with the list-practice-asan version of the program from now on, just in case you’ve accidentally introduced any memory errors. Write down at least one interaction with the program that shows how you tested your code.

F. Counting Occurrences in a List

We’d like to be able to count how many times a particular value appears in the list. That’s what the string_list_count function is supposed to do. This function will look very similar to your string_list_length function, but you won’t increment your count on every iteration.

Hint: remember to use strcmp for string comparisons. The == operator doesn’t compare strings character by character; it looks to see if two strings live at the same memory address.

Exercises

1. Implement string_list_count.
2. Test your implementation. Here is an example of the expected behavior:

   $ ./list-practice-asan
   Enter a command. Type "help" to see available options.
   > insert a
   > append b
   > insert c
   > insert b
   > append a
   > print
   b
   c
   a
   b
   a
   > count a
   Found 2 occurrence(s)
   > count b
   Found 2 occurrence(s)
   > count c
   Found 1 occurrence(s)
   > count d
   Found 0 occurrence(s)
   

G. Removing from a List

Finally, we’d like to be able to remove values from the list. There are different ways you could remove values, but for this lab, you’ll look for the first matching value and remove that node from the list. If a value appears in the list more than once, only the first occurrence is removed. Here is an example interaction using the remove command:

$ ./list-practice-asan
Enter a command. Type "help" to see available options.
> insert a
> append b
> insert c
> insert b
> append a
> print
b
c
a
b
a
> remove a
> print
b
c
b
a
> remove b
> remove d
Value was not found in the list.
> print
c
b
a
> count a
Found 1 occurrence(s)

Remember that the memory that holds nodes came from malloc and must be freed. Only the nodes in the list are freed by string_list_destroy, so your last opportunity to free this memory is in string_list_remove. The same is true of the strings stored in the node you’re removing.

Exercises

1. Consider the different cases for removing values from the list. You will need to be able to remove the first node, the last node, or any node in the middle. You also need to return the appropriate result when no matching value is found in the list. Write out your plan for dealing with each edge case in a comment near the string_list_remove function. Hint: not all edge cases will require a special case in your code, although some do. Explain your logic for each case whether you have to handle it specially or not.
2. Implement the string_list_remove function.
3. Test your implementation thoroughly. Write down at least one interaction with the program that shows how you tested your code.