Activity: Linked Lists in C

Table of Contents

1. Activity structure

This is an activity not an assignment.That means it is not graded: you won't get formal feedback on it, but it is a great chance to practice with the ideas we've been talking about and it may also guide you through some new ideas. You'll work on it during class, usually with another students, or if you have to miss class, you'll complete it outside of class.

If you're working with someone, you should work in a paired programming style. At any point in time, one of you is "driving," i.e. actually using the keyboard and mouse. The other is actively engaged following along, preventing bugs, and providing ideas. You'll tradeoff who is driving about every 10 minutes, and it's important that regardless of whose computer you're using, you take turns typing and controlling it - the owner of the computer should not be the only one who drives. Before you start coding for a new part of the activity, I strongly encourage you to sketch out your strategy with your partner. You might discuss possible approaches together, and write down some ideas on paper that will then help you when you begin coding.

At the end of class, you should make sure you turn your code in (even if you're not done), as that gives you access to my solutions, and to email the code to your partner (so they can turn it in to access my solutions).

2. Setup

If both you and your partner have computers with you with the tools for our class setup on it, decide whose computer you'll be using.

Them you'll do the activity in VS Code: download the starter code (below), unzip it, move it into the ProgrammingLanguages folder for our Docker container, and then open that folder within the Docker container in VSCode.

Click here to access the starter code for this activity.

3. Tasks

In this activity, you'll be adding to the code in linkedlist.c to develop some more linked list functionality. The code that is there right now is close to where we ended with livecoding in class.

3.1. insertFront

Right now, the linked list is a pain to use: I had to make each node one by one! Write a new function insertFront:

/* Adds a new node with the given item
 * in front of head. Returns a pointer
 * to the new node.
 */
Node *insertFront(Node *head, int item) {
  //You'll fill in the body!
}

As noted in the comment, this function adds a new item to the front of the list. It returns the pointer to that new node, allowing me to do something like:

Node *head = NULL;
head = insertFront(head, 3);
head = insertFront(head, 2);
head = insertFront(head, 1);

This creates a list with the items 1, 2, and then 3.

In main, test your code by creating a list of length 3 using the code above.

Use valgrind to check if you have any memory errors or leaks. You can do so by compiling your code with the -g option, and then running valgrind:

clang -g -o linkedlist linkedlist.c
valgrind ./linkedlist

If you have memory leaks, you can see more about them by adding --leak-check=full:

valgrind --leak-check=full ./linkedlist

If you get stuck on insertFront, please raise your hand and ask for help!

3.2. printList

As you've probably noticed, printing the list is also currently rather cumbersome. Add a function printList(Node *head) that prints the items in the given list. You might want to make this pretty in some way, e.g., by adding commas between items or braces before and after the list (e.g., [1, 2, 3]). As above, test your function in main, perhaps after using insertFront to create a longer list.

3.3. Trying a debugger

Debuggers like gdb typically allow you to do things like:

  • Set a breakpoint: A breakpoint is a specific line in your code where you would like to stop execution of the program so you can take a look at what's going on. When execution is stopped, you can print out the values of variables.
  • Step line-by-line through the program: You can view each line of code as it executes, determining exactly what line a crash occurs, and print out the values of variables to understand what's happening.

These features are incredibly useful for debugging your code! This is especially true in C, where you might get errors like "Segmentation fault" with no info on where the error has occurred.

You have two options for using the debugger with C, both of which buid on a debugger named gdb: working on the command line with gdb, or using a plugin with VSCode that makes things a little easier to work with visually.

Getting the visual part requires a small amount of setup: you'll need to put a launch.json file in a particular spot:

  • First, look in the file explorer in VSCode. Do you see a folder named .vscode in the ProgrammingLanguages directory. If not, you'll need to create one. Navigate to the ProgrammingLanguages directory - this is likely cd .. if you're currently in the Linked-List-Activity directory. Then type: mkdir .vscode
  • Now, you'll need to move the file named launch.json in vscode-files (in the starter code) into the .vscode directory. You can do so via drag and drop in the VSCode file explorer, or you can do so at the comment line:
cp Linked-ListActivity/vscode-files/launch.json .vscode/

That says to copy (cp) the file at Linked-ListActivity/vscode-files/launch.json into the directory .vscode.

Now, let's try the debugger on the linkedlist program you just created.

First, compile linkedlist.c with the -g flag, just like you needed for valgrind:

clang -g -o linkedlist linkedlist.c

Then we'll set a breakpoint and then start the debugger. To set a breakpoint, you'll click slightly to the left of the line number in linkedlist.c. You should get a red circle. Set a breakpoint somewhere in your main function.

Then, you'll start the debugger. Go to the "Run and Debug" in the left panel (has a left arrow and a weird looking bug as an icon). After you click it, you should see a button near the top that is a green arrow and where the text for it begins with "(gdb)". Click on that green arrow, and your program should start running and stop when it hits the breakpoint. Try stepping through the code line by line, and take a look at the variable values that are now in the same pane as the green arrow was.

You may find some debugging resources helpful:

If you get stuck in later parts, try using the debugger to help you find the error! It allows you to compare what you think the values of the variables should be to the actual values of those variables.

3.4. destroyList

We'll now deal with the final annoying part of your current list: remembering to free everything. Create a function destroyList(Node *head) that frees all of the allocated memory associated with head. It should assume that head refers to a Node on the heap, and that each of these nodes also refer to Nodes on the heap (or NULL at the end.

In main, test with lists of several different lengths, and as above, make sure to use valgrind to check for memory leaks or errors.

3.5. deleteItem

Write a function Node *deleteItem(Node *head, int item) that deletes item from the list if it is present, and otherwise doesn't modify the list. It returns a pointer to the first node in the (possibly modified) list. If there are no items in the list, it returns NULL.

3.6. find

Write a function int find(Node *head, int item) that returns the index of the given item in the list. If the item isn't found, return -1.

3.7. Extra time?

If you have extra time, I recommend the following activities:

  • Find out what happens with bugs!: Writing the previous functions might have given you lots of practice seeing bugs, but there are some you might not have seen. Examine what errors occur (or don't occur!) with a variety of common memory mistakes: dereferencing a pointer that hasn't been initialized, access stack memory that is no longer allocated, writing to memory that hasn't been allocated, and anything else you can think of related to memory allocation. Seeing the errors that occur will help you to recognize these errors when they inevitably occur for you at some point in the future.
  • Flesh out your linked list with other useful functions that you'd expect from a linked list, such as inserting at a particular index. With your partner, brainstorm about what the pros and cons would be of directly passing our Node *s, versus creating another struct named LinkedList that has a single member, a Node * that will refer to the head of the list, and passing around a reference to the LinkedList. How would this alternative make it easier to have the same functionality as delete but to return a value indicating whether or not an item was removed?

4. Turning in activities

To turn in this activity, zip up the folder with your code, and upload that zip on Moodle. Additionally, email the zip to your partner so they can turn it in too. Even if you worked with a partner or you didn't finish, everyone should turn in the activity in order to gain access to my solutions.

Activity originally designed by Anna Rafferty - thanks for sharing!