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.
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 theProgrammingLanguages
directory. If not, you'll need to create one. Navigate to theProgrammingLanguages
directory - this is likelycd ..
if you're currently in theLinked-List-Activity
directory. Then type:mkdir .vscode
- Now, you'll need to move the file named
launch.json
invscode-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:
- This page describes the VSCode debugging interface. It's very helpful for seeing what buttons to press and where to look. I encourage you to check it out!
- Here's a helpful reference card with lots of gdb information.
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!