Task 1: Linked Lists [20] The task will involve the classes Node and DynamicList, located in the given files node.h and dynamicList.h For this task you will implement the functions provided in the inside the dynamicList.cpp and node.h files given. You are not required to create your own makefile NOTE: the main.cpp provided to you is a very dumbed down version of the one used to test on FitchFork, thus a working main file that matches the provided example output does not guarantee full marks, and as such it is up to you as the student to expand it and test for corner cases. The following classes are required to be implemented: Node Node is the class to store the data for the dynamic list: Member variables T* value A pointer to the node value being stored Node* next A pointer to the next node in the list Node* prev A pointer to the previous node in the list Functions (Implement within node.h) Node(T val) The default constructor, setting all relevant member variables ~Node() Correctly destructs the given node

2

DynamicList DynamicList is a node based list which can dynamically change in size and hold any type of data:

Member variables Node* head A Node pointer to the start of the list Functions (Implement within node.h) DynamicList() The default constructor, setting all relevant member variables ~DynamicList() Correctly destructs the list void operator+=(const DynamicList &) Appends the DynamicList given as an argument to the current one, while maintaining the integrity of the list passed in. e.g current list [1,2] plus the list [4,5] changes current list to [1,2,4,5] void operator+=(const T) Appends the element given as an argument to the end of the DynamicList, only if it does not exist in the list. e.g current list [1,2] plus the element [4] changes current list to [1,2,4] void operator=(const DynamicList &) Deep copies all elements of the DynamicList given as an argument to the current one, maintaining the integrity of the copied list bool operator==(const DynamicList &) Returns true if the data of the argument list matches the data of the current list, else returns false bool operator<(const DynamicList &) Returns true if the DynamicList given as an argument is bigger in size (number of elements) than the current DynamicList bool operator>(const DynamicList &) Returns true if the DynamicList given as an argument is smaller in size (number of elements) than the current DynamicList T operator [](const int) Returns the array element at the index given as an argument, returns -1 if the array index does not exist bool insertNodeAt(const int, const T) Inserts the element passed in at the given index. All elements should then shift one up to the right. An element should not be inserted if it already exists in the array. If the element was inserted return true, else return false. The function is 0 indexed. Index

3

out of bounds should simply return false. e.g current list [5,6] plus the element [8] at index 1, changes current list to [5,8,6] bool deleteNode(T) Deletes the element given as an argument and returns true if found. If the element does not exist in the list, simply do nothing and return false ostream & operator << (ostream &, const DynamicList &) This function is a friend of this class and not a member. It outputs the contents of the list in the following format: nodeValue[previousNodeValue,nextNodeValue] ->, with the spaces as given. An endline should follow the last element printed. e.g If the array is 5,6,7 the output should be: 5[,6] -> 6[5,6] -> 7[6,] NOTE: Ensure this function is correctly working else output cannot be tested The following is an example output run for the given main:

1[,2] -> 2[1,3] -> 3[2,] 4[,5] -> 5[4,6] -> 6[5,] 1[,2] -> 2[1,3] -> 3[2,4] -> 4[3,5] -> 5[4,6] -> 6[5,] True 1[,2] -> 2[1,3] -> 3[2,4] -> 4[3,5] -> 5[4,6] -> 6[5,] 4 -1 1[,10] -> 10[1,2] -> 2[10,3] -> 3[2,4] -> 4[3,5] -> 5[4,6] -> 6[5,] 1[,10] -> 10[1,2] -> 2[10,4] -> 4[2,5] -> 5[4,6] -> 6[5,] Upon completion,

1. Upload your TAR archive containing dynamicList.cpp and node.h to the active fitch- fork assignment called Practical 8 on the CS website.

Given Code:

dynamicList.h:

#ifndef DYNAMICLIST_H #define DYNAMICLIST_H

#include "node.h"

#include

using namespace std;

template class DynamicList;

template std::ostream & operator<<(std::ostream &, const DynamicList &);

template class DynamicList { private:

Node *head;

public:

DynamicList(); ~DynamicList(); void operator+=(const DynamicList &); void operator+=(const T);

void operator=(const DynamicList &); bool operator==(const DynamicList &);

bool operator<(const DynamicList &); bool operator>(const DynamicList &);

T operator [](const int); bool insertNodeAt(const int, const T); bool deleteNode(T);

friend std::ostream & operator<< <>(std::ostream &, const DynamicList &); }; #endif

node.h:

#ifndef NODE_H #define NODE_H

template class Node;

template class Node { public:

T* value; Node *next; Node *prev;

Node(T val) { }

~Node() { } };

#endif

main.cpp:

#include

#include "dynamicList.h"

using namespace std;

int main() {

DynamicList list; DynamicList list2;

// Append elements and print // (Ensure this works before continuing with anything else)

for(int i = 1; i <= 3; i++) { list += i; }

for(int i = 4; i <= 6; i++) { list2 += i; }

cout << list; cout << list2 << endl;

// Append list and print

list += list2; cout << list << endl;

// Size comparison

if( list2 < list ) { cout << "True" << endl << endl; }

// Assignment operator check

list2 = list; cout << list2 << endl; // Subscript operator check

cout << list2[3] << endl; cout << list2[10] << endl << endl; // Insert node

list.insertNode(1,10); cout << list << endl;

// Delete node list.deleteNode(3); cout << list; }

makefile:

DynamicList: main.o dynamicList.o g++ -static main.o dynamicList.o -o DynamicList

main.o: g++ -c main.cpp -o main.o

dynamicList.o: dynamicList.h node.h g++ -c dynamicList.cpp -o dynamicList.o

run: ./DynamicList clean: rm -f dynamicList.o DynamicList