Skip to article frontmatterSkip to article content

Lab 06: More List Operations

Objectives

In this exercise, you will:

  1. Build more List operations.
  2. Practice using pointers.

Introduction

In this week’s lab you will add more functionality to the List class we built in class.

Here is the invite.

Use git clone to get your copy of the assignment, as we have been doing. You should have these files: List.cpp, List.h, tests.cpp, plus a makefile, etc.

If you are working with a partner, make sure you join the same Team when creating your repos. Also, put both your names in the README.md file now.

Step 1. Append

The append() method is easy to understand: given a new Item, add it to the end of the linked list. The tests.cpp file contains tests already for append().

Now, implement the code for append(). You might find looking at the implementation of prepend() to be helpful -- although append() is a bit more complicated. DRAW PICTURES! (Or, don’t draw pictures, if you want to make this step of the lab take much longer...)

Step 2. Searching

Let’s implement a method that searches the linked list for a given Item, and returns the index of where the item is found, or -1 if it is not found. Name the method getIndexOf(). Here is the prototype:

int getIndexOf(const Item &it) const;

First implement tests of getIndexOf() in tests.cpp, and then implement the method. You must call the TEST_CASE “lookfor”. I.e., put this in the tests.cpp file:

TEST_CASE("lookfor") {
     // add your tests here -- either inside SECTION()s or not.
}

Step 3. Copy constructor

You knew it was coming...

tests.cpp does not contain any test cases for this, so you’ll have to implement them yourself. My solution has 1 TEST_CASE with 3 SECTIONS: copying a 0-element List, copying a 1-element List, and copying a >1>1-element list. The name of the TEST_CASE must be “copy”:

TEST_CASE("copy") {
     // add your tests here -- either inside SECTION()s or not.
}

The prototype of the copy constructor will be:

List(const List & original);

Here is the algorithm to implement the copy constructor:

Step 4. Equality

Implement the equality method, so that you can test if two List objects have the same number of nodes and the items in the nodes are the same. The equality operator returns true or false.

E.g.,

if list1 contains 3 values: 11, 22, 33 and list2 contains four values: 11, 22, 33, 44, then list1 == list2 should return false.

To test this you have to use == (not !=), so your test might look like this:

REQUIRE(! (list1 == list2) );

Create your tests first in a test case called “equality”:

TEST_CASE("equality") {
     // add your tests here -- either inside SECTION()s or not.
}

Step 5. Templatize

Now, convert your List class to a List<Item> template and modify the tests in tests.cpp to test your new template. Remember to edit the makefile to remove List.cpp from the SOURCES line near the top of the file. You should also delete the List.cpp file completely from your tree.

Submit

A part of your grade will be based on the thoroughness of your tests; you may want to model your tests after those provided for you in previous projects.

Don’t forget to Commit and Push your changes to your repo.

Verify you have synced your code to github by going to your online repo webpage and looking to see that the files are correct.

Verify that the autograding tests have passed in github.com.

Grading Rubric

You will be graded this way: 19 pts total

Ways students lost points in the past:

Course Content
Week 06
Course Content
Week 07: Fall Break