Task 1: Linked Lists [20] The task will involve the classes Node and DynamicList
ID: 3871473 • Letter: T
Question
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 <iostream>
using namespace std;
template <class T>
class DynamicList;
template <class T>
std::ostream & operator<<(std::ostream &, const DynamicList<T> &);
template <class T>
class DynamicList
{
private:
Node<T> *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<T> &);
};
#endif
node.h:
#ifndef NODE_H
#define NODE_H
template <class T>
class Node;
template <class T>
class Node
{
public:
T* value;
Node<T> *next;
Node<T> *prev;
Node(T val)
{
}
~Node()
{
}
};
#endif
main.cpp:
#include <iostream>
#include "dynamicList.h"
using namespace std;
int main()
{
DynamicList<int> list;
DynamicList<int> 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
Explanation / Answer
#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>
struct test_struct
{
int val;
struct test_struct *next;
};
struct test_struct *head = NULL;
struct test_struct *curr = NULL;
struct test_struct* create_list(int val)
{
printf(" creating list with headnode as [%d] ",val);
struct test_struct *ptr = (struct test_struct*)malloc(sizeof(struct test_struct));
if(NULL == ptr)
{
printf(" Node creation failed ");
return NULL;
}
ptr->val = val;
ptr->next = NULL;
head = curr = ptr;
return ptr;
}
struct test_struct* add_to_list(int val, bool add_to_end)
{
if(NULL == head)
{
return (create_list(val));
}
if(add_to_end)
printf(" Adding node to end of list with value [%d] ",val);
else
printf(" Adding node to beginning of list with value [%d] ",val);
struct test_struct *ptr = (struct test_struct*)malloc(sizeof(struct test_struct));
if(NULL == ptr)
{
printf(" Node creation failed ");
return NULL;
}
ptr->val = val;
ptr->next = NULL;
if(add_to_end)
{
curr->next = ptr;
curr = ptr;
}
else
{
ptr->next = head;
head = ptr;
}
return ptr;
}
struct test_struct* search_in_list(int val, struct test_struct **prev)
{
struct test_struct *ptr = head;
struct test_struct *tmp = NULL;
bool found = false;
printf(" Searching the list for value [%d] ",val);
while(ptr != NULL)
{
if(ptr->val == val)
{
found = true;
break;
}
else
{
tmp = ptr;
ptr = ptr->next;
}
}
if(true == found)
{
if(prev)
*prev = tmp;
return ptr;
}
else
{
return NULL;
}
}
int delete_from_list(int val)
{
struct test_struct *prev = NULL;
struct test_struct *del = NULL;
printf(" Deleting value [%d] from list ",val);
del = search_in_list(val,&prev);
if(del == NULL)
{
return -1;
}
else
{
if(prev != NULL)
prev->next = del->next;
if(del == curr)
{
curr = prev;
}
else if(del == head)
{
head = del->next;
}
}
free(del);
del = NULL;
return 0;
}
void print_list(void)
{
struct test_struct *ptr = head;
printf(" -------Printing list Start------- ");
while(ptr != NULL)
{
printf(" [%d] ",ptr->val);
ptr = ptr->next;
}
printf(" -------Printing list End------- ");
return;
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.