2.1 Linked Lists Linked lists are an example of an unbound datastructure. Whereas the array is based around having a fixed sizeper array creation, there is no logical limit on the ability of alinked list to grow. Physical limitations aside, linked lists arecapable of growing largely without any limitations. To achievethis, they trade easier access to their individual elements. Thisis because linked lists have to be traversed from their root nodeto any node in question, unlike arrays which are capable ofsupporting random access to any index without traversing theothers. If a linked list uses another class, such as item, for thenodes it has, and both classes are using templates, then the linkedlist .cpp should have an include for the item .cpp as well toensure proper linkages. You should compile all of your classes asyou have previously done as individual classes then linked togetherinto the main. Additionally, you will be not be provided withmains. You must create your own main to test that your code worksand include it in the submission which will be overwritten duringmarking. 2.2 Task 1 You are going to implement a linked list withsome 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 UMLdiagram 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 thelatest node to be added into the list.

• size: The current size of the list. This starts at 0 andincreases as the list grows in size by 1 each time a node isadded.

• randomSeed: An int representing a random seed that is used forgenerating random values by the class. The class methods are asfollows:

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

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

• addItem(newItem:item ∗): This function adds the given new iteminto the linked list. If the value of the new item is lower than orequal to the smallest value in the list, it should be added at theend of the list. Otherwise it should be added in front of thecurrent head of the list.

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

• randomShuffleList(i:int): This function is an overload of therandomShuffleList function. It shuffles the current list by pickingone of the nodes in the list at random. However, the difference isthat 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 nodesthat before this node, should be moved to the end of the list. Ifthe index is invalid, do nothing. For example (the values are fordemonstration and not indicative of an actual list), given a listthat look as 1->2->3->4->5 The current head is at 1 andthe new head is 3, then the list will look like:3->4->5->1->2 You should not create or delete any ofthe nodes; just reorder them and their links.

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

• getItem(i:int): This returns the node specified at the indexin the list. The head node is index 0 and each node after increasesits 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. Ifthe 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 allof the nodes, from the head. The format of this output should be asingle comma delineated list with a newline at the end. For example(the values are for demonstration and not indicative of an actuallist) 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 diagrambelow:

-data:T

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

+item(t:T)

+~item() +next: item*

+getData():T

The class has the following variables:

• data: A template variable that stores some piece ofinformation.

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

The class has the following methods:

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

• ∼item: This is the destructor for the item class. It printsout ”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 eachclass:

• item: iostream, string

• LL: cstdlib