This lab is due by Monday, April 21, 2025, Before Class.
As with all labs you may, and are encouraged, to pair program a solution to this lab. If you choose to pair program a solution, be sure that you individually understand how to generate the correct solution.
Jump To: Rubric Submission
At long last, we are now able to create our generic List structure! Throughout the semester we have worked through list operations (insert, remove, get, set) in an abstract manner. How each of those operations and/or algorithms are performed can vary based on how the list is stored in memory. For this lab, we will create the generic List abstraction and then the two concrete implementations.
Download the Abstract List Starter Package. This contains a Makefile,
main.cpp, and test_suite.cpp to test your List.hpp, Array.hpp, and LinkedList.hpp files.
The Abstract List
The abstract list interface is already created for you:
template<typename T>
class IList {
public:
virtual ~IList() {}
virtual int size() const = 0;
virtual T get(const int POS) const = 0;
virtual void set(const int POS, const T VALUE) = 0;
virtual void insert(const int POS, const T VALUE) = 0;
virtual void remove(const T POS) = 0;
virtual T min() const = 0;
virtual T max() const = 0;
virtual int find(const T VALUE) const = 0;
};Your task is to complete the two concrete implementations for an Array and a LinkedList.
The Concrete Array
The Array class is stubbed out with comments for each operation, implementing the List interface using public inheritance. The Array class will need to implement each method using the array implementations.
The Concrete LinkedList
The LinkedList class is stubbed out with comments for each operation, implementing the List interface using public inheritance. The LinkedList class will need to implement each method using the LinkedList implementations.
Testing
Upon building and running the program, the program will test each concrete list operation against a series of test scenarios. When your implementations pass all the tests and the stress test runtimes match the expected performance, the implementations are complete.
The expected number of passed tests and an example set of stress test times is below. Your times may not match these exactly, but the relative scale of the
O(1) operations compared to the O(n) operations is the verification that implementations are correct.
/-------------------------------------------------------------------------------\
| Sanity Check |
\-------------------------------------------------------------------------------/
Tests Passed: 334 / 334 (100%)
ALL TESTS PASSED!
Running stress tests...
# List Type Insert Read Write Delete
1/6 Array Head [xxxxxxxxxx] 6.504686s O(n) [xxxxxxxxxx] 0.716215s O(1) [xxxxxxxxxx] 0.949885s O(1) [xxxxxxxxxx] 6.386469s O(n)
2/6 Array Mid [xxxxxxxxxx] 5.892625s O(n) [xxxxxxxxxx] 0.707564s O(1) [xxxxxxxxxx] 0.939781s O(1) [xxxxxxxxxx] 6.621038s O(n)
3/6 Array Tail [xxxxxxxxxx] 5.932077s O(n) [xxxxxxxxxx] 0.684827s O(1) [xxxxxxxxxx] 0.917680s O(1) [xxxxxxxxxx] 6.667506s O(n)
4/6 LinkedList Head [xxxxxxxxxx] 0.416955s O(1) [xxxxxxxxxx] 6.690104s O(n) [xxxxxxxxxx] 6.769705s O(n) [xxxxxxxxxx] 1.181900s O(1)
5/6 LinkedList Mid [xxxxxxxxxx] 6.466810s O(n) [xxxxxxxxxx] 6.458400s O(n) [xxxxxxxxxx] 6.529385s O(n) [xxxxxxxxxx] 3.896528s O(n)
6/6 LinkedList Tail [xxxxxxxxxx] 0.437422s O(1) [xxxxxxxxxx] 6.837670s O(n) [xxxxxxxxxx] 8.670466s O(n) [xxxxxxxxxx] 1.175727s O(1)
...stress tests completeGrading Rubric
Your submission will be graded according to the following rubric:
| Points | Requirement Description |
| 0.70 | Fully meets specifications |
| 0.15 | Submitted correctly by Monday, April 21, 2025, Before Class |
| 0.15 | Best Practices and Style Guide followed |
| 1.00 | Total Points |
Lab Submission
Always, always, ALWAYS update the header comments at the top of your main.cpp file. And if you ever get stuck, remember that there is LOTS of help available.
Zip together your List.hpp, Array.hpp, LinkedList.hpp file(s) and name the zip file L6A.zip. Upload this zip file to Canvas under L6A.
This lab is due by Monday, April 21, 2025, Before Class.
As with all labs you may, and are encouraged, to pair program a solution to this lab. If you choose to pair program a solution, be sure that you individually understand how to generate the correct solution.