Question

C++

Using your completed LinkedList template class, developed in homework and lab, write a program that implements and properly tests the following functions (these functions are not member functions of the class, you will write these function in mainTest.cpp )

1. Function compare that receives two LinkedList objects and compares the data in the nodes of the two lists to check if they are the same. The lists are equal only if they have the same number of nodes and corresponding nodes contain the same data. The function returns true or false to main.

2. Function mergeLists that receives two LinkedList objects. The function merges the sorted lists into a new list then returns the new list object back to main. Display the returned list.

Linkedlist.h link: https://pastebin.com/L4UUT3V8

Answer 1

Hello dude , Here I am giving your the full completed code , copy it as it is , it is running perfectly fine here so copy

paste carefully ,. And one more thing your code have many errors initially even some functions are implemeted wrong

I corrected them and also implemented main function and also written the code for compare_list and merge_two_sorted_list and one thing i want to clear that I made my own Linked List data as you have mentioned

nothing about it so you can change it depending on how you want to take input ; I just took one list odd numbers 1 to 10 and other even number between 1 to 10 to test these functions and they are woriking fine .

and one more thing whenever you call a function in main make new linkedList for it don't use previously used list;

Here is the Code copy paste it carefully and first run it, then you cna change whatever you want in input taking;

#ifndef LINKEDLIST_H
#define LINKEDLIST_H
#include <iostream>
using namespace std;

template <class T>
class LinkedList
{
private:
// Declare a structure for the list
struct ListNode
{
T value;
struct ListNode *next;
};

ListNode *head; // List head pointer

public:
LinkedList() // Constructor
{ head = nullptr; }
~LinkedList(); // Destructor
void appendNode(T);
void insertNode(T);
void deleteNode(T);
void displayList();
int search(T); // search function
T getTotal();
int numNodes();
T getAverage();
T getLargest();
int getLargestPosition();
T getSmallest();
int getSmallestPosition();
T pop_back();

void push_front(T value);
void push_back(T value);
T pop_front();
};


//**************************************************
// appendNode appends a node containing the value *
// pased into newValue, to the end of the list. *
//**************************************************

template <class T>
void LinkedList<T>::appendNode(T newValue)
{
ListNode *newNode, *nodePtr = nullptr;

// Allocate a new node & store newValue
newNode = new ListNode;
newNode->value = newValue;
newNode->next = nullptr;

// If there are no nodes in the list
// make newNode the first node
if (!head)
head = newNode;
else // Otherwise, insert newNode at end
{
// Initialize nodePtr to head of list
nodePtr = head;

// Find the last node in the list
while (nodePtr->next)
nodePtr = nodePtr->next;

// Insert newNode as the last node
nodePtr->next = newNode;
}
}

//**************************************************
// displayList shows the value *
// stored in each node of the linked list *
// pointed to by head. *
//**************************************************

template <class T>
void LinkedList<T>::displayList()
{
ListNode *nodePtr = nullptr;

nodePtr = head;
while (nodePtr)
{
cout << nodePtr->value << endl;
nodePtr = nodePtr->next;
}
}

//**************************************************
// The insertNode function inserts a node with *
// newValue copied to its value member. *
//**************************************************

template <class T>
void LinkedList<T>::insertNode(T newValue)
{
ListNode *newNode, *nodePtr, *previousNode = nullptr;

// Allocate a new node & store newValue
newNode = new ListNode;
newNode->value = newValue;

// If there are no nodes in the list
// make newNode the first node
if (!head)
{
head = newNode;
newNode->next = nullptr;
}
else // Otherwise, insert newNode
{
// Initialize nodePtr to head of list and
// previousNode to a null pointer.
nodePtr = head;
previousNode = nullptr;

// Skip all nodes whose value member is less
// than newValue.
while (nodePtr != nullptr && nodePtr->value < newValue)
{
previousNode = nodePtr;
nodePtr = nodePtr->next;
}

// If the new node is to be the 1st in the list,
// insert it before all other nodes.
if (previousNode == nullptr)
{
head = newNode;
newNode->next = nodePtr;
}
else // Otherwise, insert it after the prev. node.
{
previousNode->next = newNode;
newNode->next = nodePtr;
}
}
}

//*****************************************************
// The deleteNode function searches for a node *
// with searchValue as its value. The node, if found, *
// is deleted from the list and from memory. *
//*****************************************************

template <class T>
void LinkedList<T>::deleteNode(T searchValue)
{
ListNode *nodePtr, *previousNode = nullptr;

// If the list is empty, do nothing.
if (!head)
return;

// Determine if the first node is the one.
if (head->value == searchValue)
{
nodePtr = head->next;
delete head;
head = nodePtr;
}
else
{
// Initialize nodePtr to head of list
nodePtr = head;

// Skip all nodes whose value member is
// not equal to searchValue.
while (nodePtr != nullptr && nodePtr->value != searchValue)
{
previousNode = nodePtr;
nodePtr = nodePtr->next;
}

// If nodePtr is not at the end of the list,
// link the previous node to the node after
// nodePtr, then delete nodePtr.
if (nodePtr)
{
previousNode->next = nodePtr->next;
delete nodePtr;
}
}
}

//**************************************************
// Destructor *
// This function deletes every node in the list. *
//**************************************************

template <class T>
LinkedList<T>::~LinkedList()
{
ListNode *nodePtr, *nextNode = nullptr;

nodePtr = head;
while (nodePtr != nullptr)
{
nextNode = nodePtr->next;
delete nodePtr;
nodePtr = nextNode;
}
}

//*****************************************************
// search member function *
//This function performs a linear search of the list. *
//*****************************************************

template <class T>
int LinkedList<T>::search(T val)
{
int count = 1;
ListNode *nodePtr = nullptr;

nodePtr = head;
while (nodePtr)
{
if( nodePtr->value == val)
{
return count;
}
else
{
nodePtr = nodePtr->next;
count++;
}
}
return 0;
}

//*************************************************
// The getTotal function returns the total of *
// all the nodes in the list. *
//*************************************************
template <class T>
T LinkedList<T>::getTotal()
{
//write the function definition
T total = 0;
ListNode *nodePtr;   
nodePtr = head;
while (nodePtr != nullptr)
{
total = total + nodePtr->value;
nodePtr = nodePtr->next;
}
return total;
}

//************************************************
// The numNodes function returns the number of *
// nodes in the list. *
//************************************************
template <class T>
int LinkedList<T>::numNodes()
{
//write the function definition
int count = 0;
ListNode *nodePtr;
nodePtr = head;
while (nodePtr != nullptr)
{
count++;
nodePtr = nodePtr->next;
}
return count;
}
//*****************************************************
// The getAverage function returns the average *
// of the values in the list. *
//*****************************************************
template <class T>
T LinkedList<T>::getAverage()
{
//write the function definition
return getTotal()/numNodes();
}

//*************************************************
// The getLargest function returns the largest *
// value in the list. *
//*************************************************
template <class T>
T LinkedList<T>::getLargest()
{
//write the function definition
T largest;
ListNode *nodePtr = head;
if (nodePtr == nullptr)
{
return nullptr;
}
largest = head->value;
while (nodePtr != nullptr)
{
if (nodePtr->value > largest)
{
largest = nodePtr->value;
}
nodePtr = nodePtr->next;
}
return largest;

}

//*************************************************
// The getLargestPosition function returns the *
// position of the largest value in the list. *
//*************************************************
template <class T>
int LinkedList<T>::getLargestPosition()
{
//write the function definition
ListNode *nodePtr = head;
if (nodePtr = nullptr)
{
return -1;
}
int position = 0;
T largest = head->value;
int i = 0;
while (nodePtr != nullptr)
{
if (nodePtr->value > largest)
{
position = i;
largest = nodePtr->value;
}
i++;
nodePtr = nodePtr->next;
}
return largest;

return position;   
}

//*************************************************
// The getSmallest function returns the smallest *
// value in the list. *
//*************************************************
template <class T>
T LinkedList<T>::getSmallest()
{
//write the function definition
ListNode *nodePtr = head;
if (nodePtr == nullptr)
{
return nullptr;
}
T smallest = head->value;
while (nodePtr != nullptr)
{
if (nodePtr != nullptr)
{
smallest = nodePtr->value;
}
nodePtr = nodePtr->value;
}
return smallest;
  
}

//*************************************************
// The getSmallestPosition function returns the *
// position of the smallest value in the list. *
//*************************************************
template <class T>
int LinkedList<T>::getSmallestPosition()
{
//write the function definition
ListNode *nodePtr = head;
if(nodePtr == nullptr)
{
return -1;
}
int position = 0;
T smallest = head->value;
int i = 0;
while (nodePtr != nullptr)
{
if (nodePtr->value < smallest)
{
position = i;
smallest = nodePtr->value;
}
i++;
nodePtr = nodePtr->next;
}
return smallest;

return position;
}

//*************************************************

//Removes the last element and returns its value *

//*************************************************

template <class T>

T LinkedList<T>::pop_back()

{

ListNode *nodePtr = head;

if(nodePtr == nullptr)

return nullptr;

while(nodePtr->next)

{

nodePtr = nodePtr->next;

}

ListNode *lastPtr = nodePtr;

delete nodePtr;

return lastPtr->value;

}

//*************************************************

//Removes the first element and returns its value *

//*************************************************

template <class T>

T LinkedList<T>::pop_front()

{

ListNode *nodePtr = head;

if(nodePtr == nullptr)

return -1;

head=head->next;

ListNode *firstPtr = nodePtr;

int front= firstPtr->value;

delete firstPtr;
  
return front;

}

//*************************************************

//Inserts an element at the front of the list *

//*************************************************

template <class T>

void LinkedList<T>::push_front(T value)

{

ListNode *newNode, *nodePtr = head;

newNode = new ListNode;

newNode->value = value;

if (!nodePtr)

{

head = newNode;

newNode->next = nullptr;

}

else

{

newNode->next=head;

head=newNode;

}

}

//*************************************************

//Inserts an element at the back of the list *

//*************************************************

template <class T>

void LinkedList<T>::push_back(T value)

{

ListNode *newNode, *nodePtr = head;

newNode = new ListNode;

newNode->value = value;

newNode->next = nullptr;

if (!nodePtr)

{

head = newNode;

}

else

{

while(nodePtr->next)

{

nodePtr=nodePtr->next;

}

nodePtr->next=newNode;

}

}

#endif

void make_list(LinkedList<int> *l1, LinkedList<int> *l2)
{

for(int i =0; i<=10; i++)
{
if(i%2)
l1->push_back(i);
else l2->push_back(i);
}

cout<<"List 1 :"<<endl;
l1->displayList();
cout<<endl;
cout<<"List 2 :"<<endl;
l2->displayList();
cout<<endl;

return ;
}

bool compare_List(LinkedList<int> *l1, LinkedList<int> *l2)
{
if(l1->numNodes() != l2->numNodes())
{
return false;
}
  
int n= l1->numNodes();
while(n--)
{

if(l1->pop_front()!=l2->pop_front())
{
return false;
}
}
  
  
return true;
}

LinkedList<int> * merge_two_sorted_list(LinkedList<int> *l1, LinkedList<int> *l2)
{

LinkedList<int> *final_list= new LinkedList<int>();
  
  
  
while(l1->numNodes()>0&&l2->numNodes()>0)
{
// cout<<l1->numNodes()<<" "<<l2->numNodes()<<endl;

int a = l1->pop_front();
int b = l2->pop_front();
  
//cout<<a<<" "<<b<<endl;
if(a<b)
{
final_list->push_back(a);

l2->push_front(b);
}
else
{
final_list->push_back(b);
l1->push_front(a);
}
}

while(l1->numNodes()>0)
{
final_list->push_back(l1->pop_front());
}


while(l2->numNodes()>0)
{
final_list->push_back(l2->pop_front());
}

return final_list;
}

int main()
{

LinkedList<int> *l1=new LinkedList<int>();
LinkedList<int> *l2= new LinkedList<int>();

make_list(l1,l2);
  
cout<<"comparing list 1 with List 2"<<endl;

if(compare_List(l1,l2))
{
cout<<"True"<<endl;
}
else
cout<<"false"<<endl;

LinkedList<int> *ll1=new LinkedList<int>();
LinkedList<int> *ll2= new LinkedList<int>();

make_list(ll1,ll2);

cout<<"merging list 1 and list 2 :"<<endl;


LinkedList<int> *final_list= merge_two_sorted_list(ll1,ll2);

final_list->displayList();

return 0;

}