CSCI 200 - Foundational Programming Concepts & Design - Fall 2022

This lab is due by Tuesday, December 06, 2022, 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) const function 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 Tuesday, December 06, 2022, 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.