## Question

In this assignment you will design a templated ADT class to specification, test it, and validate it's performance with big oh timing tests.

LAB 10a: Write And Test The ListedList Class Template [ LinkedList.h and LinkedListDriver.cpp ]

Purpose. In this lab you will test an operator[] function for a linked list, that allows the linked list object to act as if it's an array. This is to demonstrate the difference between "average case" big oh and "best case", and how that can be used to our advantage in program design. It also shows how big oh considerations can drive design considerations -- e.g., the size() getter.

Requirements. Write LinkedList.h

Design the operator[] to have a O(n), with a best-case O(1), by tracking the "last node" per the lecture notes. This is a good opportunity to use assertions in your template. The "last index" should be -1 whenever the "last pointer" is zero, and it should be zero or greater when the "last pointer" is not zero.

Fully test the template with your own LinkedListDriver.cpp, following our rules for test drivers. It should work exactly like your StaticArray and DynamicArray templates.

Program I/O. Input: All hard-coded as per a driver CPP only. Output: From the driver CPP only, console (cout) output only

________________________________________

LAB 10b: Write And Test The ListedList Class Template [ MyLinkedList.cpp ]

Purpose. In this lab you will write an app with the same user interface used in lab 5a's app, using a linked list instead of StaticArray.

Requirements. Write MyLinkedList.cpp, matching the operation from your lab 5a app, and using your LinkedList class from lab 10a.

Submit the CPP file to the class website for credit.

Program I/O. Same as lab 5a.

________________________________________

LAB 10c: Perform Performance Confirmation On The ListedList Class Template [ LinkedListBigOh.cpp ]

Purpose. In this lab you will determine and confirm the big oh performance of all functions in the interface.

Requirements. Write LinkedListBigOh.cpp, applying the "4-cycle timing code" from the lecture notes, to the following functions, based on a list of doubles:

1. operator[] assignment at zeroth index, O(1)

2. operator[] assignment at 100th index, O(1)

3. iteration from first to last using operator[], O(n) -- using a for-loop

4. size(), O(1)

Note that if you write your size() function to iterate the linked list and count the nodes, instead of tracking size as a data member, #4 above will be O(n) -- if that happens, fix it. And if you don't manage the "last node" correctly, test #3 will be O(n-squared) or worse -- if that happens, fix it.

This will require four sets of "4-cycle timing code", each with their own starting n values. In each cycle, create the array and fill it with random values (using srand and rand). Then start the timer, perform the operation, and stop the timer.

Refer to lecture topic 9's notes for timing of fast operations, because these O(1)'s are very fast! You may have to use very large numbers of "reps" to get measurable results. Since these operations do not change the value of n, the number of reps not restricted to 1% of n. Each timing test can have it's own number of reps.

Here's what to time for iteration, to make sure that operator[] gets called for each index from 0 to size-1:

// create and list and fill with values

// start timer

for (int i = 0; i < list.size(); list[i], i++);

// stop timer

Submit the CPP file to the class website for credit. But in the version you submit, don't make your n's so large that it takes more than a few seconds to run during grading!

Program I/O. No input. Console output reporting timing results per the provided code, WITH headings for each of the four test results. In testing iteration, don't include cout output.

Example.

operator[] assignment at zeroth index, O(1)

1436 (expected O(1)) for n=5000

1500 (expected 1436) for n=10000

1482 (expected 1436) for n=20000

1421 (expected 1436) for n=40000

operator[] assignment at 100th index, O(1)

1436 (expected O(1)) for n=5000

1521 (expected 1436) for n=10000

1452 (expected 1436) for n=20000

1511 (expected 1436) for n=40000

iteration from first to last using operator[], O(n)

1436 (expected O(n)) for n=500

2742 (expected 2872) for n=1000

5442 (expected 5744) for n=2000

10828 (expected 11488) for n=4000

size(), O(1)

1436 (expected O(1)) for n=50000

1511 (expected 1436) for n=100000

1399 (expected 1436) for n=200000

1400 (expected 1436) for n=400000

## Solution Preview

This material may consist of step-by-step explanations on how to solve a problem or examples of proper writing, including the use of citations, references, bibliographies, and formatting. This material is made available for the sole purpose of studying and learning - misuse is strictly forbidden.

#ifndef LINKEDLIST_H#define LINKEDLIST_H

#include <cstdlib>

using namespace std;

template<class T>

class LinkedList{

private:

struct Node{

T data;

bool isUse;

Node * next;

};

void changeCapacity(int i){

Node * s = start;

if (s != 0) {

while (s->next != 0) {

s = s->next;

}

}else{

start = new Node;

start->next = 0;

s = start;

}

for (int j = 0; j < i - cap ; j++) {

s->next = new Node;

s = s->next;

s->isUse = false;

s->next = 0;

}

cap = i;

}...