The only file you will need for this assignment is the List.h file that we wrote in class. Our testList.cpp file might also be of use as a starting point for your test file.

Collaboration Policy

For this assignment, you must work indivicually on your program.

Please make sure you adhere to the policies on academic integrity in this regard.

Overview

Similar to our last program with vectors, we will add some functionality to our list class written during lecture. In addition, you will implement sorting algorithms for both the vector and the list classes.

Part 1

Please write the following functions described below in our List class. (Please download List.h from the course schedule webpage and insert your functions into this class, then submit the entire List.h file via email by the due date.)

NOTE: For these functions, all iterators and references to elements remain valid. Note that this means you may NOT remove elements and readd them, since this will allocate new nodes and invalidate the pointers/iterators which already exist. You'll have to get down and dirty with pointers for most of these.

Functions to code

• T& operator[](int index);

  Returns the item in the list which is at position index.

• void replace(T val1, T val2);

  Replace all instances of val1 in the current list with val2.

• void swap(List& other);

  Exchanges the content of the current list by the content of other, which is another list object containing elements of the same type. Sizes may differ.

  After the call to this member function, the elements in this container are those which were in other before the call, and the elements of other are those which were in this. All iterators, references and pointers remain valid for the swapped objects.

• void reverse();

  Reverses the order of the elements in the list container.

• You are also required to write a test file, similar to our testList.cpp in class. You our welcome to use our code from class as a starting point, but your grade will be partially based on how well you test your code. Remember to thoroughly test all possible inputs before submitting.

Part 2: Sorting

You will also be implementing a sorting algorithms for this assignment in the list class. Add your sorting function of choice to the .h file as a member function also, and clearly indicate in the name and the comments which algorithms you have chosen. Note that I don't care which algorithm you implement in particular.

You may wish to review these and try to take into account which sorting algorithms are easier to implement in lists!

Extra Credit

For extra credit, you may also implement a second sorting algorithm in the Vector.h class, which will sort the vector when called.

Files to Submit

• Source Code for List
  Submit your revised List.h file (with the sorting algorithm added).

• Test file
  Submit your revised testList.cpp file.

• Source Code for Vector
  If you do the extra credit, also submit your revised Vector.h file.

• "readme" file
  An overview and run time analysis of the functions in your class, including comments on how you tested your code, and any further comments you wish to make to the grader.

Grading Standards

The assignment is worth 10 points. One point will be based on your testList.cpp file, and one will be based on your readme and runtime analysis. The remaining 8 points will be based on the assigned functions (including commenting, indenting, and meaningful variable names).