Question

there are files called LinkedList.h, and Array.h and all the functionality you need has already been implemented. There is also a file called TimeSupport.h that allows you to measure the running time of code segments. There is also a file called RandomSupport.h, which you can use to generate good random numbers.

In your app.cpp , create a demo illustrating a scenario where storing numbers in a linked list is more efficient than an array. Your demo should generate a sufficiently large number of random integers and insert them into both the list, and the array. Your demo should also provide the time it took to complete the operations in the array, and in the linked list. It should show that the linked list was faster.

app.cpp

#include <iostream>

#include <Array.h>

#include <LinkedList.h>

using namespace std;

int main(){

// Your code here...

return 0;

}

Support code-

Array.h

#ifndef Array_h

#define Array_h

#include <iostream>

#include <ostream>

struct ResizableArray {

// This is the poiner to the start of our array

long* data;

// Keep track of how much memory we have allocated

long size;

// Keep track of how much memory we have used

long counter;

// A default constructor

ResizableArray(){

// Start off by allocating memory for 1 int

data = new long[1];

// This means we have allocated for 1

size = 1;

// And we are currently using 0

counter = 0;

}

    // This is a copy constructor. It specifies what happens when

    // the array needs to be copied. In this case it performs

    // a deep copy, which is what we need

    ResizableArray(const ResizableArray& other){

        size = other.size;

        counter = other.counter;

        data = new long[other.size];

        for (long i = 0; i < other.size; i++){

            data[i] = other.data[i];

        }

    }

    // Overloading the == operator. Now we can compare

    // two ResizableArrays with the == operator

    bool operator==(const ResizableArray rhs) const {

        // If the sizes or counters are different, it's not a match

        if (size != rhs.size){

            return false;

        }

        if (counter != rhs.counter){

            return false;

        }

        // Assume the arrays match

        bool same = true;

        // And try to find a contradiction

        for (long i = 0; i < counter; i++){

            if (data[i] != rhs.data[i]){

                return false;

            }

        }

        

        // Colud not get a contradiction

        return true;

    }

// Print the contents we have

void print(){

for (long i = 0; i < counter; i++){

std::cout << data[i] << std::endl;

}

}

    // Get the value at a specified position

int get(long index){

return data[index];

}

    // Set the value at a specified position with a given integer

void set(long index, long value){

data[index] = value;

}

    void insert(long index, long value){

if (index < size){

for(long i = counter; i > index; i--){

data[i] = data[i-1];

}

data[index] = value;

counter++;

if (counter == size){

long oldSize = size;

size = size * 2;

long* newArr = new long[size];

for (long i = 0; i < oldSize; i++) {

newArr[i] = data[i];

}

delete[] data;

data = newArr;

}

}

else{

int oldSize = size;

while (index+1 >= size){

size *=2;

}

if (size > oldSize){

long* newArr = new long[size];

for (long i = 0; i < oldSize; i++) {

newArr[i] = data[i];

}

delete[] data;

data = newArr;

}

for (long i = counter; i < index; i++){

data[i] = 0;

}

data[index] = value;

counter = index + 1;

}

}

// Store a new value in the array

void append(long value){

// The very first time this is called

// we know we have enough storage allocated

// because we allocated space for 1 int

// so we store it

data[counter] = value;

// and increase the counter

counter++;

// If we are out of space, i.e. we have

// stored as much as we have allocated

// then we need to increase our storage space

if (counter == size){

// Just for convenience, store the old size

long oldSize = size;

// Let's double the amount of storage we have

size = size * 2;

// Allocate another chunk of memory

// twice as big as the first

long* newArr = new long[size];

// Copy all elements from the old location

// to the new location

for (long i = 0; i < oldSize; i++) {

newArr[i] = data[i];

}

// Release the old location

delete[] data;

// Make our data pointer point to the new location

data = newArr;

}

}

    

    // This is called a destructor. It simply releases the

    // memory we have been using.

    ~ResizableArray(){

        delete[] data;

    }

};

// This is an overload of the << operator, which allows us

// to print out the ResizableArray with cout <<

std::ostream& operator<<(std::ostream& os, const ResizableArray& arr) {

for (long i = 0; i < arr.counter; i++){

        os << arr.data[i] << " ";

    }

return os;

}

#endif

LinkedList.h

#ifndef LinkedList_h

#define LinkedList_h

#include <iostream>

#include <ostream>

struct Node{

    long data;

    Node* next;

    Node (){

        data = 0;

        next = NULL;

    }

    Node (long n){

        data = n;

        next = NULL;

    }

};

struct LinkedList{

    Node* head;

    Node* last;

    LinkedList(){

        head = NULL;

        last = NULL;

    }

    LinkedList(const LinkedList& other){

        head = NULL;

        if (other.head != NULL){

            Node* temp = other.head;

            while (temp != NULL){

                append(temp->data);

                temp = temp->next;

            }

        }

        last = other.last;

    }

    void append (long n){

        if (head == NULL){

            head = new Node(n);

            last = head;

        }

        else{

            Node* theNode = new Node(n);

            last->next = theNode;

            last = last->next;

        }

    }

    void prepend(long n){

        Node* temp = new Node(n);

        temp->next = head;

        head = temp;

    }

    bool operator==(const LinkedList& other) const {

        Node* ours = head;

        Node* theirs = other.head;

        while (ours != NULL){

            if (theirs == NULL){

                return false;

            }

            if (ours->data != theirs->data){

                return false;

            }

            else{

                ours = ours->next;

                theirs = theirs->next;

            }

        }

        return theirs == NULL;

    }

    ~LinkedList(){

        Node* temp = head;

        while (temp != NULL){

            head = head->next;

            delete temp;

            temp = head;

        }

    }

};

std::ostream& operator<< (std::ostream& os, const LinkedList& theList){

    Node* temp = theList.head;

    while (temp != NULL){

        os << temp->data << " ";

        temp = temp->next;

    }

    return os;

}

#endif

TimeSupport.h

//

// A small library for timing our programs

//

#ifndef TimeSupport_h

#define TimeSupport_h

#include <chrono>

typedef enum {

sec,

mill

} Unit;

typedef std::chrono::time_point<std::chrono::high_resolution_clock> timestamp;

long time_diff(timestamp start, timestamp end, Unit u = mill){

if (u == mill){

auto diff = std::chrono::duration_cast<std::chrono::milliseconds>(end-start).count();

return (long) diff;

}

else{

auto diff = std::chrono::duration_cast<std::chrono::seconds>(end-start).count();

return (long) diff;

}

}

timestamp current_time(){

return std::chrono::high_resolution_clock::now();

}

#endif

RandomSupport.h

//

// A small library for sampling random numbers from a uniform distribution

//

#ifndef RandomSupport_h

#define RandomSupport_h

#include <random>

int call_counter = 0;

typedef std::uniform_int_distribution<long> uniform_distribution;

typedef std::mt19937 randomizer;

randomizer new_randomizer(){

randomizer rng;

rng.seed(std::random_device()());

return rng;

}

uniform_distribution new_distribution(long start, long end){

uniform_distribution dist(start, end);

return dist;

}

long sample(uniform_distribution& dist, randomizer& r){

call_counter++;

return dist(r);

}

#endif

Answer 1

Hello! :)

Here is the documented code to illustrate the scenario:

app.cpp:

#include <iostream>
#include <vector>
#include <limits>

#include <Array.h>
#include <LinkedList.h>
#include <TimeSupport.h>
#include <RandomSupport.h>

using namespace std;

int main(){
    // Your code here...

    // generating the vector of random numbers for insertion
    const long start{numeric_limits<long>::min()};
    const long end{numeric_limits<long>::max()};
    const size_t size{30'000};
    randomizer r = new_randomizer();
    uniform_distribution dist = new_distribution(start, end);
    std::vector<long> dataVector(size);
    for(long& data : dataVector)
    {
        data = sample(dist, r);
    }

    // inserting the data into the ResizableArray instance and timing it
    long arrTimeTaken;
    {
        ResizableArray arr;
        const timestamp arrStartTime{current_time()};
        for(const long data : dataVector)
        {
            arr.insert(0, data); // all insertions taking place at position 0
        }
        const timestamp arrEndTime{current_time()};
        arrTimeTaken = time_diff(arrStartTime, arrEndTime);
    }

    // inserting the data into the LinkedList instance and timing it
    long llTimeTaken;
    {
        LinkedList ll;
        const timestamp llStartTime{current_time()};
        for(const long data : dataVector)
        {
            ll.prepend(data); // similarly, all insertions are taking place at the beginning of the linked list
        }
        const timestamp llEndTime{current_time()};
        llTimeTaken = time_diff(llStartTime, llEndTime);
    }

    // generating the output log
    cout << "ResizableArray: " << arrTimeTaken << " mill" << endl;
    cout << "LinkedList: " << llTimeTaken << " mill" << endl;
    if(llTimeTaken < arrTimeTaken)
    {
        cout << "Hence, the LinkedList implementation is more efficient than the ResizableArray implementation." << endl;
    }
    else
    {
        cout << "Unfortunately, the LinkedList implementation is more inefficient than the ResizableArray implementation." << endl;
    }

    return 0;
}

Here is a screenshot of a demo run:

Hope this helps! :)