Lab: Linked List Variations

_Note on Drivers: Alternate drivers for each problem A, B, etc. _

The associated reading for today’s class introduced some common variations on linked lists. Today’s lab will ask you to implement some variations on lists and to reflect on what makes them useful. You will need to start with a completed linked list implementation from the previous lab, so make sure you’ve finished that lab before beginning this one.

A. Sorted Insertion

We’ll start off by changing the list interface slightly. Instead of inserting values to the list at the beginning or end, we’ll build the list in sorted order.

Start by making a directory for today’s lab, and then copying the code from your previous lab:

$ mkdir ~/csc161/labs/linked-list-variations/
$ cd ~/csc161/labs/linked-list-variations/
$ cp -R ../linked-lists/ sorted
$ cd sorted

Complete the following exercises, working in the copy of your prior lab.

Exercises

1. We’re going to change the list interface so the only way to add values is to insert them in sorted order. That means we only need one way to add values to the list, string_list_insert. Edit the main.c file to remove references to the string_list_append function, which we are going to remove soon.

2. Remove string_list_append from both the header file and source file for your linked list implementation. Compile the program and make sure it works before moving on.

3. Now update the string_list_insert function so it will insert values in sorted order. Remember that you will need to use strcmp to compare strings. Hint: It might help to consider these specific cases: when the list is empty, and when it has only one node. Test your implementation using the driver program, and make sure it behaves like this example:

   $ ./list-practice
   Enter a command. Type "help" to see available options.
   > insert xylophone
   > insert Canada
   > insert apple
   > insert zebra
   > insert zeppelin
   > insert Argentina
   > print
   Argentina
   Canada
   apple
   xylophone
   zebra
   zeppelin
   

4. Finally, write down a reason why we might choose to store a list in sorted order rather than their insertion order. Hint: you may find a good reason in one of the other functions that implements your list.

B. Tracking List Length

Next, we’ll add code to keep a record of a list’s length to the linked list implementation you completed in your previous lab. We’ll start with a fresh copy of that code, which you can make with the following terminal commands:

$ cd ~/csc161/labs/linked-list-variations/
$ cp -R ../linked-lists/ length
$ cd length

If you aren’t sure why we keep track of a list’s length along with its nodes you may want to review today’s reading. Once you’re comfortable with the motivation for this variant, please complete the following exercises.

Exercises

1. Add a length field to the string_list_t structure in string_list.h.
2. Next, change your string_list_length function so it returns lst->length instead of traversing the list to count nodes.
3. Now make a list of all the functions that will need to make updates to the length field of the list. Include a brief explanation for each function in the list interface, both for functions that you will need to update and functions that can be left as-is.
4. Update your implementation to keep the length field of the list up to date.
5. Finally, test your changes. Make sure you try combinations of different operations on the list. The length value returned by string_list_length should always be correct.

C. Doubly-Linked Lists

The last list variation we’ll explore was only introduced in the reading: doubly-linked lists. In a doubly-linked list, each node has both a next and a previous pointer. Keeping these pointers up to date requires some careful reasoning and handling of edge cases.

As before, you’ll start this variation from a clean copy of your earlier linked list code:

$ cd ~/csc161/labs/linked-list-variations/
$ cp -R ../linked-lists/ double
$ cd double

Exercises

1. Start by adding a previous pointer to your string_node_t structure.

2. You’ll need to update your linked list implementation to keep this previous pointer up to date in each node. We want to maintain the invariant that, for any node m with a non-null next pointer, m->next->previous points to m. The other invariant we want to maintain is: for any node n with a non-null previous pointer, n->previous->next points to n. To prepare for this update, make a list of the functions you’ll need to change to correctly set/update at least one node’s previous pointer.

3. Make your updates and test the new implementation before moving on. All of the list operations you implemented earlier should still work without causing segmentation faults or AddressSanitizer errors.

4. Using a doubly-linked list can help us by simplifying the string_list_remove function. Your implementation probably used two pointers to seek through the list: one that eventually points to the node to be removed, and another that points to the prior node. Update your implementation of string_list_remove to use the previous pointer contained in the node you are removing instead of keeping a separate pointer.

5. If you have time: Inserting into the middle of a list is also simpler with a doubly-linked list. Combine your changes in part A of the lab (inserting in sorted order) with this doubly-linked list implementation. Make sure your code to insert into the middle of the list takes advantage of the previous pointer stored in each node.