Activity: Linked Lists in C

Right now, the linked list is a pain to use: I have 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.

Unfortunately, in my experience getting the visual debugger to work with the interpreter project is very finicky. I would rather that you have a working debugger than no debugger (even if it's a little more cumbersome to use), so the instructers here are for command-line gdb. If you have experience with the VSCode plugin (or are motivated to learn) and want to try your luck with that instead, feel free.

Let's walk through linkedlist in gdb:

gdb linkedlist

Here are a couple important commands for gdb:

• run (or r): starts your program running
• break (or b): break functionName will put in a breakpoint at the function named functionName. That means when you get to that function, the program will stop executing, allowing you to print out variables or step through line by line. break lineNumber where lineNumber is a line number will put in a breakpoint at that particular line. That means that when the program reaches that line of code (and before it executes it), it will stop executing.
• print (or p): print x, where x is a variable, will print the value of x. Note that this is printing before the line that is currently shown executes.
• step (or s): execute the current line of code and stop execution when the next line of code is reached, even if this next line is in a different function.
• next (or n): execute the current line of code, including any function calls, and stop execution when the next line in the current function is reached.
• continue (or c): continue running the program until it ends, crashes, or a breakpoint occurs.
• backtrace (or bt): print out all frames in the stack (this is useful if the line an error occurs is in some library, so you can see where in your code called that library)
• quit: exit gdb.

Try out gdb as follows:

• Add a breakpoint to the main function in linkedlist.c. (Type b main once gdb is running)
• Run the program in gdb. (Type r)
• Step through line by line, and try printing out the values of different variables. (Use s and p.)

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.

If you want more detailed information on how to use gdb, this is a great resource.

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, accessing 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?