Question

2.1 Linked Lists Linked lists are an example of an unbound data structure. Whereas the array is based around having a fixed size per array creation, there is no logical limit on the ability of a linked list to grow. Physical limitations aside, linked lists are capable of growing largely without any limitations. To achieve this, they trade easier access to their individual elements. This is because linked lists have to be traversed from their root node to any node in question, unlike arrays which are capable of supporting random access to any index without traversing the others. If a linked list uses another class, such as item, for the nodes it has, and both classes are using templates, then the linked list .cpp should have an include for the item .cpp as well to ensure proper linkages. You should compile all of your classes as you have previously done as individual classes then linked together into the main. Additionally, you will be not be provided with mains. You must create your own main to test that your code works and include it in the submission which will be overwritten during marking. 2.2 Task 1 You are going to implement a linked list with some additional features beyond that of a standard linked list. This will consist of implementing two classes: LL and item.

2.2.1 LL The class is described according to the simple UML diagram below:

LL < T >

-head: item < T > *

-size: int

-randomSeed:int

----------------------------

+LL(rS:int)

+~LL() +getHead() const: item*

+addItem(newItem:item*):void

+randomShuffleList():void

+randomShuffleList(i:int):void

+pop():item*

+getItem(i:int) const:item*

+minNode():T

+maxNode():T +getSize() const:int

+printList():void The class variables are as follows:

• head: The head pointer of the linked list. It refers to the latest node to be added into the list.

• size: The current size of the list. This starts at 0 and increases as the list grows in size by 1 each time a node is added.

• randomSeed: An int representing a random seed that is used for generating random values by the class. The class methods are as follows:

• LL(rS:int): The constructor for the class. It receives an int that represents random seed and should use that seed to set the random value generator.

• LL(): The destructor for the class. It should deallocate all of the memory of the class. Deletes should happen from the head of the list and progress from there. • getHead(): This returns the head node of the list.

• addItem(newItem:item ∗): This function adds the given new item into the linked list. If the value of the new item is lower than or equal to the smallest value in the list, it should be added at the end of the list. Otherwise it should be added in front of the current head of the list.

• randomShuffleList(): This function shuffles the current list by picking one of the nodes in the list at random. This node then becomes the new head of the list. All of the nodes that before this node, should be moved to the end of the list. For example (the values are for demonstration and not indicative of an actual list), given a list that look as 1->2->3->4->5 The current head is at 1 and the new head is 3, then the list will look like: 3 3->4->5->1->2 You should not create or delete any of the nodes; just reorder them and their links.

• randomShuffleList(i:int): This function is an overload of the randomShuffleList function. It shuffles the current list by picking one of the nodes in the list at random. However, the difference is that it receives the index of the new head in the current list. This node then becomes the new head of the list. All of the nodes that before this node, should be moved to the end of the list. If the index is invalid, do nothing. For example (the values are for demonstration and not indicative of an actual list), given a list that look as 1->2->3->4->5 The current head is at 1 and the new head is 3, then the list will look like: 3->4->5->1->2 You should not create or delete any of the nodes; just reorder them and their links.

• pop(): This removes and returns head node in the list. The head should be correspondingly updated. If the list is empty, return null.

• getItem(i:int): This returns the node specified at the index in the list. The head node is index 0 and each node after increases its index by one. If the index is out of the bounds of the list, null should be returned.

• minNode(): This returns the smallest value found in the list. If the list is empty, it should return null.

• maxNode():This returns the largest value found in the list. If the list is empty, it should return null.

• getSize(): This returns the current size of the list.

• printList(): This function prints out the values stored in all of the nodes, from the head. The format of this output should be a single comma delineated list with a newline at the end. For example (the values are for demonstration and not indicative of an actual list) 1,2,3,4,5 as an example of the output of the list. 4

2.2.2 item

The class is described according to the simple UML diagram below:

-data:T

-------------------

+item(t:T)

+~item() +next: item*

+getData():T

The class has the following variables:

• data: A template variable that stores some piece of information.

• next: A pointer of item type to the next item in the linked list.

The class has the following methods:

• item: This constructor receives an argument and instantiates the data variable with it.

• ∼item: This is the destructor for the item class. It prints out ”X Deleted” with no quotation marks and a new line at the end. X refers to the data stored in the item.

• getData: This returns the data element stored in the item.

You will be allowed to use the following libraries for each class:

• item: iostream, string

• LL: cstdlib

Answer 1

// item.h
#ifndef ITEM_H
#define ITEM_H

#include <iostream>
#include <string>

template <class T>
class item
{
private:
T data;

public:
item* next;
item(T t);
~item();
T getData();
};

// constructor
template <class T>
item<T>::item(T t)
{
data = t;
next = NULL;
}

// destructor
template <class T>
item<T>::~item()
{
std::cout<<data<<" Deleted\n";
}

// return data
template <class T>
T item<T>::getData()
{
return data;
}

#endif // ITEM_H

//end of item.h

// LL.h
#ifndef LL_H
#define LL_H

#include "Item.h"
#include <cstdlib>

template <class T>
class LL
{
private:
item<T>* head;
int size;
int randomSeed;

public:
LL(int rS);
~LL();
item<T>* getHead() const;
void addItem(item<T>* newItem);
void randomShuffleList();
void randomShuffleList(int i);
item<T>* pop();
item<T>* getItem(int i);
T minNode();
T maxNode();
int getSize() const;
void printList();
};

// constructor to create an empty list
template <class T>
LL<T>::LL(int rS)
{
head = NULL;
size = 0;
randomSeed = rS;
srand(randomSeed);
}

// destructor to release the memory allocated
template <class T>
LL<T>::~LL()
{
item<T>* temp;
while(head != NULL)
{
temp = head;
head = head->next;
temp->next = NULL;
delete(temp);
temp = NULL;
}
size = 0;
}

// return the head
template <class T>
item<T>* LL<T>:: getHead() const
{
return head;
}

// function to add newItem to the list
template <class T>
void LL<T>:: addItem(item<T>* newItem)
{
newItem->next = NULL;
if(head == NULL) // empty list, make newItem the head
head = newItem;
else
{
// newItem's data <= minimum value of the list, insert at the end
if(newItem->getData() <= minNode())
{
item<T>* curr = head;
while(curr->next != NULL)
curr = curr->next;
curr->next = newItem;
}
else // newItem's data > minimum value of the list, insert at the head
{
newItem->next = head;
head = newItem;
}
}

size++;
}

// randomly shuffle the list items
template <class T>
void LL<T>:: randomShuffleList()
{
int index = rand()%size; // generate a random index between [0, size-1]
randomShuffleList(index); // call overloaded function to shuffle making the node at index the head
}

// randomly shuffle the list items making the item at index i the new head
template <class T>
void LL<T>:: randomShuffleList(int i)
{
// validate index i
if(i > 0 && i < size)
{
int index = 0;
item<T>* curr = head;
item<T>* pre = NULL;
// loop to get the item at index i in curr and item previous to curr in pre
while(index < i)
{
index++;
pre = curr;
curr = curr->next;
}

pre->next = NULL; // set next of pre to null
item<T>* p = curr; // ste p to curr

// loop to get the last node of list
while(p->next != NULL)
p = p->next;

p->next = head; // set next of p to head
head = curr; // update head to curr
}
}

// remove and return the head node
template <class T>
item<T>* LL<T>:: pop()
{
if(size > 0) // non-empty list
{
item<T>* curr = head;
head = head->next;
size--;

return curr;
}

return NULL; // empty list
}

// return the node specified at the index in the list
template <class T>
item<T>* LL<T>:: getItem(int i)
{
// validate index
if(i >= 0 && i <size)
{
int index = 0;
item<T>* curr = head;
// loop to get the node at index i
while(index < i)
{
index++;
curr = curr->next;
}

return curr;
}

return NULL; // invalid index
}

// function to return the minimum value of the list
template <class T>
T LL<T>:: minNode()
{
T min = T(NULL);
if(size > 0) // non-empty list
{
min = head->getData();
item<T>* curr = head;
// loop to get the minimum value
while(curr != NULL)
{
if(curr->getData() < min)
min = curr->getData();
curr = curr->next;
}

}

return min;
}

// function to return the maximum value of the list
template <class T>
T LL<T>:: maxNode()
{
T max = T(NULL);
if(size > 0) // non-empty list
{
max = head->getData();
item<T>* curr = head;
// loop to get the maximum value of list
while(curr != NULL)
{
if(curr->getData() > max)
max = curr->getData();
curr = curr->next;
}

}

return max;
}

// return number of elements in list
template <class T>
int LL<T>::getSize() const
{
return size;
}

// display the list
template <class T>
void LL<T>:: printList()
{
if(head != NULL) // non-empty list
{
item<T>* curr = head;
// loop to display the elements from start to second last node with comma and a space in between
while(curr->next != NULL)
{
std::cout<<curr->getData()<<", ";
curr = curr->next;
}

std::cout<<curr->getData(); // display the last node data
}

std::cout<<std::endl; // display a new line
}

#endif // LL_H

//end of LL.h