In: Computer Science
In your app.cpp file, 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
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
The main code can show the some error
please check