Activity: Linked Lists in C

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!

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.

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, 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:

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

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.

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.

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.

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?