This lab is due by Thursday, May 04, 2023, 11:59 PM.
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.
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) and algorithms (sorting & searching) 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.
The Abstract List
We will create an abstract templated List class that supports a subset of the list operations we have been working with.
The class will have the following members and corresponding implementations:
-
public:- default constructor - sets the size to zero
int getSize() const- returns the size of the list- A pure virtual
T get(const int POS) constfunction that returns the ith element of the list - A pure virtual
void set(const int POS, const T VALUE)function that sets the ith element of the list - A pure virtual
void insert(const int POS, const T VALUE)function that inserts the value before the ith element of the list - A pure virtual
void remove(const int POS)function that removes the ith element of the list
-
protected:- the size of the list as an integer
Place this class in a file named List.hpp.
The Concrete Array
Now create the Array class which extends List using public inheritance. The Array class will need to implement the get, set, insert,
and remove functions using the array implementations. Therefore, the Array class will need to add the necessary private data members
to back those operations.
Place this class in a file named Array.hpp.
The Concrete LinkedList
Now create the LinkedList class which extends List using public inheritance. The LinkedList class will need to implement the get, set, insert,
and remove functions using the linked list implementations. Therefore, the LinkedList class will need to add the necessary private data members
to back those operations.
Place this class in a file named LinkedList.hpp.
Testing
Download the Abstract List Starter Package. This contains a Makefile
and main.cpp to test your List.hpp, Array.hpp, and LinkedList.hpp files. Upon building and running the program,
the program will test each concrete list operation with 100,000 values. The time to complete each task is printed, which should show the trade off between list
implementations when we perform these tasks at a larger scale.
Lab Submission
Submit your List.hpp, Array.hpp, LinkedList.hpp file(s).
You will submit your solution to this lab with the rest of Set6. Detailed instructions for doing this are posted in Assignment 6.
This lab is due by Thursday, May 04, 2023, 11:59 PM.
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.