Lab: Linked Lists (print, find, append)

An alternative way to store sets of data

Through this lab, we will introduce linked lists, discuss the basic traversal algorithm, and implement print, find and append functions. Check-out the following (empty) folder to work in.

https://cssvn.utrgv.edu/svn_etomai/201720_2380/lab02_lists/<your username>

Commit your work at the end of lab for lab credit!

Make a list

First thing we need for a linked list is a node class. It needs a data member (we'll use string for this lab) and a pointer to the same class (often called link or next). For this we will use public data members. Might as well put in a constructor that lets you set data and sets link to NULL, for convenience.

Now that you've got your node definition, create a list of three items in main, just like we did in class. Again, look it up, but don't copy/paste. The items are the strings "zildjian", "sabian" and "paiste".

Once you've got that set up, put a breakpoint at the end of your main function so that you can use the debugger's autos or locals window to check the contents of your list (like we did in class). Being able to inspect memory is key to debugging and not wasting huge amounts of your time.

Check it twice

We are going to start writing a set of functions to work with a linked list. Important Note! The node class that we just made represents one node in the list, not the whole list. Therefore, it is not appropriate to add functions that work with the whole list into that class. In this lab, we'll just use global functions. Later, we'll look at creating a List class that uses the node class.

  1. Implement a print function (not method) that takes a pointer to a list of nodes and traverses the list, printing all the values. Call it in main to verify that it works.
  2. Implement a find function that takes a pointer to a list of nodes and a string to find, and returns True if that string is in the list, False otherwise. Verify with test cases in main that it works for all relevant cases:
    • empty list
    • first item
    • last item
    • middle item
    • item that doesn't exist

Append something something nice

Remember how you created that three item list in main by doing blah->next->next...? Awesome. Now never do that again. That was fine for learning how to do it, but in reality you never write code that hardcodes a certain number of "next" links. You should be using a function that can append a new value to a list of any size.

Write another function (not method) that takes a pointer to a list and a new value to append to the end of the list. It'll follow the same generic traversal approach, you need to figure out:

  1. where to stop
  2. the right condition for stopping there
  3. what to do at each node (if anything)
  4. what to do when you stop (if anything)

Don't forget to test your append function for all the relevant cases:

  1. list with 1 item
  2. list with more than 1 item
  3. empty list

The last case is a bit tricky. See if you can figure it out.