Exercise 17
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 the functionality necessary to support deletion from a (singly) linked list, and insertion into a sorted version of a linked list

Part 1

In this exercise you’ll be adding to some starter code and the solution to the previous exercise 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/ex17 directory into your personal git repository. You’ll see that we have provided a Makefile for convenience, a list_test.c main program, and both a header file and implementation file for the linked list functions.

Part 2

In file list.c, implement the remove_after and remove_front functions. The first removes and frees the node immediately after the parameter node. The second removes and frees the head of the list and updates the head pointer. Each one should return the character in the node being removed. (Hint: carefully review the provided add_front function first.)

For example, if your list includes the values a b c d e, then remove_after called on a pointer to the node containing c would result in a list containing a b c e, and would return d. And a call to remove_front on that revised list would result in a list containing b c e, and would return a.

You can validate your implementation by uncommenting the supplied tests for remove_after and remove_front in list_test.c and then typing make and then running the executable ./test. Note that many tests exist in list_test.c.

Part 3

Validate that your implementation does not leak memory and does not access memory that does not belong to it by running:

valgrind --leak-check=full --show-leak-kinds=all ./test

Note that the Makefile compiles the object files with the -g flag.

Part 4

In file list.c, implement the remove_all function. This removes all nodes in the list whose value matches the argument. Hint: think recursion!

You can validate your implementation of this function by uncommenting the supplied tests for remove_all in list_test.c and then typing make and then running the executable ./test.

Part 5

Once again, validate that your implementation still does not leak memory and does not access memory that does not belong to it by running:

valgrind --leak-check=full --show-leak-kinds=all ./test

Part 6

In file list.c, implement the insert function. This function takes a pointer to the head of the list (which may point to NULL), creates a node with the prescribed value, and inserts it into the list in sorted order. This function will set the new head pointer if the head of the linked list has been updated.

  1. You can assume that when the function is called, the linked list comes in sorted.

  2. For ordering, simply use the < and > operators. (e.g. the character ‘a’ should be larger than the character 'B'.)

  3. Feel free to make use of the add_front and add_after methods we have already written.

  4. Think recursion!

You can validate your implementation by uncommenting the supplied tests for insert in list_test.c and then typing make and then running the executable ./test.

There are many other functions in the header, implementation and test file that you can work on for extra practice. Keep in mind that linked lists will be on the midterm exam.

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!