Question

This is a reminder that this is not a C++ or Java course. It is a Data Structures course. This means that you are to write your own code unless otherwise specified in the assignment. The use of built in data structures types like linked lists, stacks, queues, trees, maps, graphs etc. is prohibited and will result in a 60% reduction in your grade. Furthermore, the lecture material presents code that should be used to get you started. Any data structure that is not derived from what is shown in the lecture material will not be accepted. You will receive a grade of 0 for submitting it.

Task 1 - The Linked List

The linked list is at the core of most data structures. We see it in lists, stacks, queues and trees to name a few.

From the lecture material create a linked list class. This class should be generic so that it will operate on any given type. In C++ we call this a template class. In Java it is a Generic. Of course in Java a generic will not operate on a primitive type but that should be ok for what we are doing

Your class should have the following functionality:

• void addToEnd(T data) - adds an item to the end of the list
• void insert(T search, T data) - Adds data as a new Node following the node that contains search
• deleteNode(T search) - Deletes the node that contains search.
• void printList() - Prints the entire linked list.
• bool contains(T search) - returns true if the list contains T and false if it doesn't

If you could use C++ and describe each function to help me understand I would appreciate it. Thank you!

Answer 1

Program:

#include<iostream>

using namespace std;

//node class
template<class T>
class node
{
public:
T info;
node *next;
//constructor
node(T data)
{
info = data;
next = nullptr;
}
};

//LinkedList class
template<class T>
class LinkedList
{
private:
node<T> *head;
public:
//constructor
LinkedList()
{
head = nullptr;
}

//adds an item to the end of the list
void addToEnd(T data)
{
//create a new node
node<T> *newnode = new node<T>(data);

//check is the list empty
if(head==nullptr)
{
head = newnode;
return;
}

//traverse the list
node<T> *temp = head;
while(temp->next!=nullptr)
{
temp = temp->next;
}
//add the newnode at the end of the list
temp->next = newnode;
}

//Adds data as a new Node following the node that contains search
void insert(T search, T data)
{
//create a new node
node<T> *newnode = new node<T>(data);

//traverse the list to find the search
node<T> *temp = head;
while(temp!=nullptr && temp->info != search)
{
temp = temp->next;
}
//check if search is found
if(temp!=NULL && temp->info == search)
{
node<T> *post = temp->next;
//insert following the node that contains search
temp->next = newnode;
newnode->next = post;
}
}

//Deletes the node that contains search.
void deleteNode(T search)
{
node<T> *temp, *pre;
temp = head; pre = nullptr;
//check search contains first node
if(temp->info==search)
{
head = temp->next;
temp->next = nullptr;
delete temp;
return;
}
//traverse the list
while(temp!=nullptr && temp->info!= search)
{
pre = temp;
temp = temp->next;
}
//not found
if(temp==nullptr) return;

//delete the node contains search
pre->next = temp->next;
temp->next = nullptr;
delete temp;
}

//Prints the entire linked list.
void printList()
{
//check is the list empty
if(head==nullptr)
{
cout<<"EMPTY LIST";
return;
}
node<T> *temp = head;
//traverse the list
while(temp!=nullptr){
cout<<temp->info<<" ";
temp=temp->next;
}
cout<<endl;
}

//returns true if the list contains T and false if it doesn't
bool contains(T search)
{
node<T> *temp = head;
//search the list
while(temp!=nullptr){
//check the search value with the node value
if(temp->info==search)
return true;
temp=temp->next;
}
return false;
}
};

//main function
int main()
{
//create LinkedList object
LinkedList<int> list;

//insert some integers
list.addToEnd(5);
list.addToEnd(10);
list.addToEnd(15);
list.addToEnd(20);
list.addToEnd(25);

//print the list
cout<<"List after create: ";
list.printList();
//delete 15 from the list
list.deleteNode(15);
//print the list after deletion
cout<<"List after deletion: ";
list.printList();

return 0;
}

Output:

List after create: 5 10 15 20 25
List after deletion: 5 10 20 25

N.B. Whether you face any problem or need any modification then share with me in the comment section, I'll happy to help you.