C++ language Overview: In this project you will be using and extending a linked
ID: 3813638 • Letter: C
Question
C++ language
Overview: In this project you will be using and extending a linked list class to manipulate a set of data. In this project you will be creating a linked list class to store integers. This class should be called LinkedList and should be in files LinkedList.cpp and LinkedList.h. This should be a singly linked list with both a tail and a head pointer.
This class should implement the following methods:
A constructor to create an empty list
void reAppend(int) : that puts a new node at the start of the linked list
void appendNode(int) : puts a new node at the end of the linked list
void insertNodeInSortedOrder(int) : puts a node after the first node lower than it in the list
void deleteNodeOfValue(int) : deletes the first node of a particular value in a list
void deleteNodeAtLocation(int) : deletes a particular element
int getNodeValueAtLocation(int) : returns the value at a particular node
void mergeTwoNodes(int a, int b) : takes elements in positions a and b in the linked list and adds their values together and puts the result in node a. It then deletes node b.
void swapNodes(int a, int b) : swaps the node values in positions a and b of the list
void removeAllDuplicates() : Go through the list and check for any duplicates. If a duplicate is found, remove the duplicates. After this function the list should have all singular values.
int numberOfNodes() : returns the number of nodes in the linked list
void displayList() const : that displays the entire list to the terminal
void deleteList() : delete the entire linked list, so remove all nodes
In your main.cpp implement a program that uses this linked list. Your program should first create an empty linked list and then go into a loop that starts by displaying the elements in the list (which will be of course empty to start). Then display a menu where you let the user pick an operation to do on the linked list (one of the functions above). Do the operation, displaying any results that are appropriate so the tester can see that the operation was done. Include an option to quit when we are done. To get the full points for an operation, your menu must work for that option and not simply have the function implemented in theory.
Explanation / Answer
Below is the code for the question. Code contains comments. Sample output is shown. Please dont forget to rate teh answer if it helped. Thank you very much.
LinkedList.h
//a node in the linkedlist with int data and pointer to next node
typedef struct llnode
{
int data;
llnode * next;
}node;
class LinkedList
{
private:
node *head, *tail;
int size; //number of nodes in the list
public:
LinkedList();//constructor
void reAppend(int); // puts a new node at the start of the linked list
void appendNode(int); //puts a new node at the end of the linked list
void insertNodeInSortedOrder(int); //puts a node after the first node lower than it in the list
void deleteNodeOfValue(int);// deletes the first node of a particular value in a list
void deleteNodeAtLocation(int);// deletes a particular element
int getNodeValueAtLocation(int) ;// returns the value at a particular node
void mergeTwoNodes(int a, int b) ;// takes elements in positions a and b in the linked list and adds their values together and puts the result in node a. It then deletes node b.
void swapNodes(int a, int b);//swaps the node values in positions a and b of the list
void removeAllDuplicates();//Go through the list and check for any duplicates. If a duplicate is found, remove the duplicates. After this function the list should have all singular values.
int numberOfNodes();// returns the number of nodes in the linked list
void displayList() const ;// that displays the entire list to the terminal
void deleteList() ;//delete the entire linked list, so remove all nodes
~LinkedList();//destructor
};
LinkedList.cpp
#include "LinkedList.h"
#include <iostream>
using namespace std;
LinkedList::LinkedList()//constructor
{
head=tail=NULL;
size=0;
}
void LinkedList::reAppend(int n) // puts a new node at the start of the linked list
{
node *t=new node();
t->data=n;
t->next=head; //make new node point to previous head
head=t; //update head
if(tail==NULL) //if there were no nodes earlier
tail=head;
size++;
}
void LinkedList::appendNode(int n) //puts a new node at the end of the linked list
{
node *t=new node();
t->data=n;
t->next=NULL;
if(tail!=NULL)
tail->next=t;//make tail point to new node
tail=t; //update tail
if(head==NULL) //if there were no nodes earlier
head=tail;
size++;
}
void LinkedList::insertNodeInSortedOrder(int n) //puts a node after the first node lower than it in the list
{
node *curr=head ;
node *t=new node();
t->data=n;
t->next=NULL;
while(curr!=NULL)
{
if(curr->data < n)
{
break;
}
else
curr=curr->next;
}
if(curr==NULL) //means reached end of list
{
//did not find any lower node than this node, so put this in beginning
t->next=head;
head=t;
if(size==0) //no elements in list
tail=head;
}
else
{
t->next=curr->next;
curr->next=t;
if(curr==tail)//if we are adding after the last node, then update tail
tail=t;
}
size++;
}
void LinkedList::deleteNodeOfValue(int n)// deletes the first node of a particular value in a list
{
node *curr=head, *prev=NULL;
while(curr!=NULL)
{
if(curr->data == n)
{
break;
}
else
{
prev=curr;
curr=curr->next;
}
}
if(curr!=NULL) //found a node to be deleted
{
if(curr==head) // we are deleting head node
{
head=curr->next;
}
if(curr==tail)
{
tail=prev;
}
if(prev!=NULL)
prev->next=curr->next;
delete curr;
size--;
}
}
void LinkedList::deleteNodeAtLocation(int loc)// deletes a particular element
{
node *curr=head,*prev=NULL;
int i=1;
while(i<loc && curr!=NULL)
{
prev=curr;
curr=curr->next;
i++;
}
if(curr!=NULL) //found a node to be deleted
{
if(curr==head) // we are deleting head node
{
head=curr->next;
}
if(curr==tail)
{
tail=prev;
}
if(prev!=NULL)
prev->next=curr->next;
delete curr;
size--;
}
}
//return value of node at given location. If no such location, -1 is returned
int LinkedList::getNodeValueAtLocation(int loc) // returns the value at a particular node
{
node *curr=head ;
int i=1;
while(i<loc && curr!=NULL)
{
curr=curr->next;
i++;
}
if(curr==NULL)
return -1; //return -1 if no such location exists
else
return curr->data;
}
void LinkedList::mergeTwoNodes(int a, int b) // takes elements in positions a and b in the linked list and adds their values together and puts the result in node a. It then deletes node b.
{
node *curr=head ;
int i=1;
while(i<a && curr!=NULL)
{
curr=curr->next;
i++;
}
if(curr!=NULL)
{
int n2=getNodeValueAtLocation(b);
if(n2!=-1)
{
curr->data=curr->data+n2; //merge the data into a's location
deleteNodeAtLocation(b); //delete the node at b
}
}
}
void LinkedList::swapNodes(int a, int b)//swaps the node values in positions a and b of the list
{
node *nodeA=head,*nodeB=head;
int i=1;
while(i<a && nodeA!=NULL) //move to location a and end of list not reached
{
nodeA=nodeA->next;
i++;
}
i=1;
while(i<b && nodeB!=NULL) //move to location b and end of list not reached
{
nodeB=nodeB->next;
i++;
}
if(nodeA!=NULL && nodeB!=NULL) //both are valid nodes
{
//swap the values
int temp=nodeA->data;
nodeA->data=nodeB->data;
nodeB->data=temp;
}
}
void LinkedList::removeAllDuplicates()//Go through the list and check for any duplicates. If a duplicate is found, remove the duplicates. After this function the list should have all singular values.
{
node *currval=head,*q,*prev;
while(currval!=NULL)
{
prev=currval;
q=currval->next; //start from next node to currval
while(q!=NULL) //till end of list
{
if(q->data==currval->data) //duplicate
{
if(q==tail) //deleting the duplicate in tail
{
tail=prev;
}
prev->next=q->next; //link the previous node ot node afetr q
delete q;
size--;
q=prev->next;
}
else
{
prev=q;
q=q->next;
}
}
currval=currval->next;
}
}
int LinkedList::numberOfNodes()// returns the number of nodes in the linked list
{
return size;
}
void LinkedList::displayList() const // that displays the entire list to the terminal
{
node *p=head;
while(p!=NULL)
{
cout<<p->data<<" ";
p=p->next;
}
cout<<endl;
}
void LinkedList::deleteList() //delete the entire linked list, so remove all nodes
{
node *p=head,*q;
while(p!=NULL)
{
q=p->next;
delete p;
p=q;
}
head=tail=NULL;
size=0;
}
LinkedList::~LinkedList()//destructor
{
deleteList();
}
main.cpp
#include "LinkedList.h"
#include <iostream>
using namespace std;
int main()
{
int choice,num,loc1,loc2;
LinkedList list;
bool rep=true;
while(rep)
{
cout<<"List contains ";
list.displayList();
cout<<"________________________________________________________________________"<<endl;
cout<<"1. Add to End"<<endl;
cout<<"2. Add at Start"<<endl;
cout<<"3. Insert sorted"<<endl;
cout<<"4. Delete value"<<endl;
cout<<"5. Delete at location"<<endl;
cout<<"6. Display value at location"<<endl;
cout<<"7. Merge location values"<<endl;
cout<<"8. Swap location values"<<endl;
cout<<"9. Remove duplicates"<<endl;
cout<<"10. Display size"<<endl;
cout<<"11. Display list"<<endl;
cout<<"12. Delete List"<<endl;
cout<<"13. Exit"<<endl;
cout<<"Enter choice : "<<endl;
cin>>choice;
switch(choice)
{
case 1:
cout<<"Enter number: "<<endl;
cin>>num;
list.appendNode(num);
cout<<"Appended "<<num<<" to end of list "<<endl;
break;
case 2:
cout<<"Enter number: "<<endl;
cin>>num;
list.reAppend(num);
cout<<"Added "<<num<<" to begining of list "<<endl;
break;
case 3:
cout<<"Enter number: "<<endl;
cin>>num;
list.insertNodeInSortedOrder(num);
cout<<"Inserted "<<num<<" in sorted order after first lowest value "<<endl;
break;
case 4:
cout<<"Enter number to be deleted: "<<endl;
cin>>num;
list.deleteNodeOfValue(num);
break;
case 5:
cout<<"Enter location to be deleted: "<<endl;
cin>>loc1;
list.deleteNodeAtLocation(loc1);
break;
case 6:
cout<<"Enter location to be displayed: "<<endl;
cin>>loc1;
cout<<"Value at location "<<loc1<<" is "<<list.getNodeValueAtLocation(loc1)<<endl;
break;
case 7:
cout<<"Enter location 1 for merging : "<<endl;
cin>>loc1;
cout<<"Enter location 2 for merging : "<<endl;
cin>>loc2;
list.mergeTwoNodes(loc1,loc2);
break;
case 8:
cout<<"Enter location 1 for swaping : "<<endl;
cin>>loc1;
cout<<"Enter location 2 for swaping : "<<endl;
cin>>loc2;
list.swapNodes(loc1,loc2);
break;
case 9:
cout<<"Removing duplicates..."<<endl;
list.removeAllDuplicates();
break;
case 10:
cout<<"List size = "<<list.numberOfNodes()<<endl;
break;
case 11:
cout<<"Displaying list ";
list.displayList();
break;
case 12:
cout<<"Deleting list ...."<<endl;
list.deleteList();
break;
case 13:
rep=false;
break;
}
}
return 0;
}
sample output
List contains
________________________________________________________________________
1. Add to End
2. Add at Start
3. Insert sorted
4. Delete value
5. Delete at location
6. Display value at location
7. Merge location values
8. Swap location values
9. Remove duplicates
10. Display size
11. Display list
12. Delete List
13. Exit
Enter choice :
1
Enter number:
5
Appended 5 to end of list
List contains 5
________________________________________________________________________
1. Add to End
2. Add at Start
3. Insert sorted
4. Delete value
5. Delete at location
6. Display value at location
7. Merge location values
8. Swap location values
9. Remove duplicates
10. Display size
11. Display list
12. Delete List
13. Exit
Enter choice :
2
Enter number:
6
Added 6 to begining of list
List contains 6 5
________________________________________________________________________
1. Add to End
2. Add at Start
3. Insert sorted
4. Delete value
5. Delete at location
6. Display value at location
7. Merge location values
8. Swap location values
9. Remove duplicates
10. Display size
11. Display list
12. Delete List
13. Exit
Enter choice :
2
Enter number:
8
Added 8 to begining of list
List contains 8 6 5
________________________________________________________________________
1. Add to End
2. Add at Start
3. Insert sorted
4. Delete value
5. Delete at location
6. Display value at location
7. Merge location values
8. Swap location values
9. Remove duplicates
10. Display size
11. Display list
12. Delete List
13. Exit
Enter choice :
1
Enter number:
5
Appended 5 to end of list
List contains 8 6 5 5
________________________________________________________________________
1. Add to End
2. Add at Start
3. Insert sorted
4. Delete value
5. Delete at location
6. Display value at location
7. Merge location values
8. Swap location values
9. Remove duplicates
10. Display size
11. Display list
12. Delete List
13. Exit
Enter choice :
1
Enter number:
2
Appended 2 to end of list
List contains 8 6 5 5 2
________________________________________________________________________
1. Add to End
2. Add at Start
3. Insert sorted
4. Delete value
5. Delete at location
6. Display value at location
7. Merge location values
8. Swap location values
9. Remove duplicates
10. Display size
11. Display list
12. Delete List
13. Exit
Enter choice :
3
Enter number:
7
Inserted 7 in sorted order after first lowest value
List contains 8 6 7 5 5 2
________________________________________________________________________
1. Add to End
2. Add at Start
3. Insert sorted
4. Delete value
5. Delete at location
6. Display value at location
7. Merge location values
8. Swap location values
9. Remove duplicates
10. Display size
11. Display list
12. Delete List
13. Exit
Enter choice :
4
Enter number:
8
List contains 6 7 5 5 2
________________________________________________________________________
1. Add to End
2. Add at Start
3. Insert sorted
4. Delete value
5. Delete at location
6. Display value at location
7. Merge location values
8. Swap location values
9. Remove duplicates
10. Display size
11. Display list
12. Delete List
13. Exit
Enter choice :
10
List size = 5
List contains 6 7 5 5 2
________________________________________________________________________
1. Add to End
2. Add at Start
3. Insert sorted
4. Delete value
5. Delete at location
6. Display value at location
7. Merge location values
8. Swap location values
9. Remove duplicates
10. Display size
11. Display list
12. Delete List
13. Exit
Enter choice :
11
Displaying list 6 7 5 5 2
List contains 6 7 5 5 2
________________________________________________________________________
1. Add to End
2. Add at Start
3. Insert sorted
4. Delete value
5. Delete at location
6. Display value at location
7. Merge location values
8. Swap location values
9. Remove duplicates
10. Display size
11. Display list
12. Delete List
13. Exit
Enter choice :
9
Removing duplicates...
List contains 6 7 5 2
________________________________________________________________________
1. Add to End
2. Add at Start
3. Insert sorted
4. Delete value
5. Delete at location
6. Display value at location
7. Merge location values
8. Swap location values
9. Remove duplicates
10. Display size
11. Display list
12. Delete List
13. Exit
Enter choice :
8
Enter location 1 for swaping :
1
Enter location 2 for swaping :
4
List contains 2 7 5 6
________________________________________________________________________
1. Add to End
2. Add at Start
3. Insert sorted
4. Delete value
5. Delete at location
6. Display value at location
7. Merge location values
8. Swap location values
9. Remove duplicates
10. Display size
11. Display list
12. Delete List
13. Exit
Enter choice :
7
Enter location 1 for merging :
2
Enter location 2 for merging :
3
List contains 2 12 6
________________________________________________________________________
1. Add to End
2. Add at Start
3. Insert sorted
4. Delete value
5. Delete at location
6. Display value at location
7. Merge location values
8. Swap location values
9. Remove duplicates
10. Display size
11. Display list
12. Delete List
13. Exit
Enter choice :
3
Enter number:
3
Inserted 3 in sorted order after first lowest value
List contains 2 3 12 6
________________________________________________________________________
1. Add to End
2. Add at Start
3. Insert sorted
4. Delete value
5. Delete at location
6. Display value at location
7. Merge location values
8. Swap location values
9. Remove duplicates
10. Display size
11. Display list
12. Delete List
13. Exit
Enter choice :
13
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.