Please compile a program written in C++ for the below exercise. Please comment y
ID: 3859653 • Letter: P
Question
Please compile a program written in C++ for the below exercise. Please comment your code so even a beginner is able to understand what is going on as they read through the lines of code. Also, any separation of files as .h and .cpp, please label with a heading for me what files are .cpp and .h . This way the program can be assembled and run properly. Last, please show sample output to confirm the program compiled and ran without error. Thanks in advance!
PROGRAM:
Design your own linked list class that works as a template class. It should provide member functions for appending, inserting and deleting nodes. The destructor should destroy the list. The class should also provide a member function that will display the contents of the list to the screen. The class should also provide a member function to search the list for an element in the list. The search should return the index (location) of the item in the list. So if it is the first element in the list then it should return 0. If the item is not in the list, it should return -1. Have main create two instances of the linked list with different data types and show that all of the functions work correctly.
Explanation / Answer
#include <iostream>
#include <string>
using namespace std;
//Represents a node in the linked list
template<class T>
class Node
{
private:
T data;
Node<T> * next;
public:
//Constructor
Node(T d, Node *nxt)
{
data = d;
next = nxt;
}
//Sets data
void setData(T d)
{
data = d;
}
//Sets address of next node
void setNext(Node *nxt)
{
next = nxt;
}
//Returns the data
T getData()
{
return data;
}
//Returns next node
Node* getNext()
{
return next;
}
};
template<class T>
class LinkedList
{
private:
//Represents starting node of the list
Node<T> * head;
public:
//Constructor
LinkedList()
{
head = NULL;
}
//Distructor
//destroys the list
~LinkedList()
{
Node<T> * curr = head;
while (head)
{
head = head->getNext();
delete curr;
curr = head;
}
}
//Inserts a new node at head or starting of the list
void insert(T val)
{
Node<T> * newNode = new Node<T>(val,NULL);
if (head == NULL)
{
head = newNode;
return;
}
else
{
newNode->setNext(head);
head = newNode;
}
}
//Adds a node at the end of the list
void append(T val)
{
Node<T> * newNode = new Node<T>(val,NULL);
if (head == NULL)
{
newNode->setNext(NULL);
head = newNode;
}
else
{
Node<T> * curr = head;
while (curr->getNext()!=NULL)
{
curr = curr->getNext();
}
curr->setNext(newNode);
}
}
//Deletes a node from the list, if it exists
void deleteNode(T val)
{
Node<T> * prev = head;
Node<T> * curr = head;
if (head->getData() == val)
{
head = head->getNext();
return;
}
while (curr)
{
if (curr->getData() == val)
break;
prev = curr;
curr = curr->getNext();
}
if (curr->getData() == val)
{
prev->setNext(curr->getNext());
}
}
//Searches a value in the list and returns the index of it,
//if it exists in the list. returns -1, otherwise
int search(T val)
{
Node<T>* pNode = head;
int index = 0;
/* traverse the list */
while (pNode != NULL) {
/* check for the target here */
if (pNode->getData() == val)
{
return index;
}
index++;
/* move to the next one */
pNode = pNode->getNext();
}
return -1;
}
//displays the contents of the list to the screen
void displayList()
{
Node<T> * curr = head;
while (curr)
{
cout << curr->getData() << " -> ";
curr = curr->getNext();
}
cout << "NULL" << endl;
}
};
int main()
{
//create two instances of the linked list
LinkedList<int> List1;
List1.append(1);
List1.append(2);
List1.append(3);
List1.append(4);
cout << "List of numbers: " << endl;
List1.displayList();
//Find 3 in the list
if (List1.search(3)!=-1)
cout << "3 exists in the list" << endl;
LinkedList<string> List2;
List2.insert("Grapes");
List2.insert("Apple");
List2.insert("Mango");
List2.insert("Cherry");
cout << "List of fruits: " << endl;
List2.displayList();
cout << "List of fruits with out Apple: " << endl;
List2.deleteNode("Apple");
List2.displayList();
return 0;
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.