In this program, we will implement and test a Linked List class. Recall that the Linked List is an Abstract Data Type (o

[answerhappygod]

In this program, we will implement and test a Linked List class.Recall that the Linked List is an Abstract Data Type (or datastructure, as more commonly known as) that organizes data linearly.The Linked List is designed using the concept of Nodes, where nodesrepresent a single unit of data in the list. Each Linked List hastwo primary components: the data it contains and a reference (orpointer, depending on the language) to the next node in the list.Linked Lists also have a reference to the first node, which iscalled the head, and sometimes the last node, which is the tail. Inthis lab, we will build an Unordered Linked List, which is a LinkedList where the nodes have no particular order. We will implementthe following operations for this Linked List: • getSize – returnsthe size(number of nodes) of the linked list. • prepend – adds anew node to the front of the linked list. This operation moves thecurrent head node to the second position in the linked list andcreate a new node with the passed in data as the first node.Increases the size counter as well. • append – adds a new node tothe back of the linked list. This operation creates a new node withthe passed in data and adds it to the end of the Linked List.Increases the size counter as well. • insert – adds a new node at acertain position in the Linked List. Note that if the positionspecified does not exist in the linked list, the operation shouldfail and return false to indicate failure. • clearList – removesall nodes from the Linked List. This method should be called in thedestructor so that all data is properly deallocated when the LinkedList is destroyed. • popFront – removes the first node from theLinked List AND returns a copy of the nodes containing data. Ifthere are no nodes in the linked list, the operation should failand return false to indicate failure. • popBack – removes the lastnode from the Linked List AND returns a copy of the nodescontaining data. If there are no nodes in the linked list, theoperation should fail and return false to indicate failure. •remove – removes the node at a specified position in the linedlist. If there is no node at the given position, the operationshould fail and return false to indicate failure. • getFront –returns a copy of the data in the head node. If there are no nodesin the linked list, return false. • getBack – returns a copy of thedata in the tail node. If there are no nodes in the linked list,return false. • getAt – returns a copy of the data in the node at agiven position. If there is no node at the given position, thenreturn false. Once you are finished with the operations, create aLinked List that contains data of your choosing. Then use thetoString method to get a string that contains the data in theLinked List. Note that you should choose simple data types such asints, chars, floats, etc. To help you get started, a starting classdefinition has been provided to you on Canvas, which will containsome of the operations already completed. Read and understand thecode in these operations to help complete the rest of theoperations, as well as look at online visualizations to understandhow these should be coded.
Given Code:
#include "Node.h"
#include <string>
#include <sstream>
using std::to_string;
using std::string;
using std::stringstream;
template<class T>
class UnorderedList {
private:
Node<T>* head;
Node<T>* tail;
int size;
public:
UnorderedList()
{
head = tail =nullptr;
size = 0;
}
~UnorderedList()
{
clear_list();
}
//Note: Including const at the end ofthe function
//makes this method safe to call from aconst declared
//object. For example:
// constUnorderedList<string> my_list;
//
//can call any method with "const" atthe end.
//i.e., "my_list.get_size()"
//but CANNOT call"my_list.append("blah")", for example.
//This is used to define operator= foryour PigLatinWord
//class to make it more compatable withother STLs/classes.
//Additionally, do NOT put "const" onany mutator methods,
//as all mutator methods result in achange in the object,
//which goes against the idea ofconstants.
int getSize() const
{
return size;
}
//This method is already complete foryou.
//Adds a new node to the beginning ofthe
//linked list.
void prepend(const T& new_data)
{
//Create the newnode and make head point to it.
Node<T>*temp = new Node<T>(new_data, head);
head = temp;
//If head isempty, then also set tail to point to it.
if (head ==nullptr)
tail= temp;
size++;
}
//This method is already complete foryou.
//Adds a new node to the end of thelinked
//list.
void append(const T& new_data)
{
/*Complete theinsert function here */
}
//Inserts a new node at a specificposition
//in the linked list.
bool insert(const T& new_data, intposition)
{
/*Complete theinsert function here */
}
//Removes all nodes from the linkedlist.
//Note: Make sure that all pointers
//are set to null and the size isset
//to zero.
void clearList()
{
/*Complete theclear list function here*/
}
//This method is already complete foryou.
//Removes a node from the front of thelist.
bool popFront(T& data)
{
/*Complete thepopFront function here */
}
//This method is already complete foryou.
//Removes a node from the back of thelist.
bool popBack(T& data)
{
if (tail ==nullptr)
returnfalse;
else
{
Node<T>*temp = head;
Node<T>*temp2 = tail;
while(temp->getNext() != tail)
temp= temp->getNext();
data= tail->getData();
temp->setNext(nullptr);
deletetail;
size--;
returntrue;
}
}
//Removes a node at a specific positionin the Linked List.
bool remove(T& data, intposition)
{
/* Complete theremove function here. */
}
bool getHead(T& data) const
{
if (head !=nullptr)
{
data= head->getData();
returntrue;
}
else
{
returnfalse;
}
}
bool getTail(T& data) const
{
/*Complete thegetTail function here */
}
bool getAt(T& data, int pos)const
{
/*Complete thegetAt function here */
}
string toString(string sep = "")const
{
stringstreamret_str;
for(Node<T>* temp = head; temp != nullptr; temp =temp->getNext())
{
ret_str<< temp->getData() << sep;
}
returnret_str.str();
}
};