Exercise 16
Info

This is an in-class exercise. An exercise page like this one will contain a brief description but is intended to be supplemented by discussion during our meeting time. Complete the exercise to the best of your ability in the time given. Feel free to talk with other students as you work, and do not be afraid to ask questions if you get stuck. Aim to complete as much as possible during our meeting, and submit on Gradescope to check your solution. You are encouraged to work at home to complete what you do not get through today, and ask questions over Piazza or in office hours.

Learning Objectives

Reinforces concepts learned in today's meeting:

  • Linked lists
  • Dynamic memory allocation
  • Pointers, pointers, and more pointers
  • Implement length, add_after, and reverse_print functions

Intro

In this exercise you’ll be adding to some starter code to build functions for working with a singly linked list of character data. Get started by running git pull to update your clone of the public repository, and then copying the exercises/ex16 directory into your personal git repository. You’ll see that we have provided a Makefile for convenience, a main.c test program, and both a header file and implementation file for the linked list functions.

Part 1

Implement a length function to count and return the number of elements in the singly linked list. Add an appropriate declaration and definition in list.h and list.c, respectively. The function should be passed a pointer to the first node of a linked list (const protected), and return an integer indicating how many values are stored in the linked list. (Equivalently, it returns a count of the number of nodes in the linked list, since each node stores one element.)

Uncomment the assertion in main.c which tests length on the test linked list. Compile and test your solution, making any necessary fixes before proceeding. Remember to use gdb throughout this exercise to debug any segmentation faults.

Part 2

Implement the add_after function. This should take a pointer to a Node and a char value as parameters, and insert a new node with the corresponding char value into the list, immediately after the node passed as the parameter.

Uncomment the assertions and call to print in main.c to test add_after on the test linked list.

Part 3

Implement the reverse_print function. It is like the print function, except that it prints the values in reverse order. This one will require some thought (hint: recursion)!

Uncomment the call to reverse_print in main.c to test your implementation.

Reminder

Remember to add and commit to your local repo copy as your work. Push to your remote repo when finished. Also scp and submit to Gradescope to check your solution. Use exit to logout from your ugrad account when finished. If you continue to work on the program after class, make sure to keep your repo updated as well!