Write a C++ program for this Part - 1: Implement a Circular linked list ADT to s
ID: 3601125 • Letter: W
Question
Write a C++ program for this
Part - 1: Implement a Circular linked list ADT to store a collection of doubles.
Part - 2: Implement a Double linked List ADT to store a collection of integers.
(You are allowed to extend the demo code posted on GitHub for this homework). Make sure to provide an interactive user interface to test these new functions in the main() for grader . Your ADT will include the following member functions:
--- a default constructor
--- the "big-3": destructor, copy constructor and overloaded assignment operator
1. a member function pushFront(data) that inserts a node with data at the front of the list
2. a member function pushBack(data) that appends a node with data at the back of the list
3. a member function popFront() that removes first node of the list.
4. a member function popBack() that removes last node of the list.
5. a member function insert(index, val) that inserts a new node with value "val" at a specific position mentioned by the index argument.
6. a member function deleteDuplicates(val) that deletes a node with that number and all its copies from the list, where these copies can be located anywhere in the list.
7. a member function mtoLastElement(M) that returns Mth to the last element of a list such that when M = 0, the last element of the list is returned.
8. a member function size() that returns the size of the list.
9. an overloaded put operator (<<) to print out all the data items stored in a linked list. Note that you are recommended to overload this operator as a friend function of the LinkedList class.
10. a member function reverseList() that reverses a linked list without recreating a temporary copy of this linked list. In other words, your function CAN NOT use the 'new' operator. Here is an example, if a list contains the following data items, 3 -> 5 -> 1 -> 7; this reverse() function will change the list to 7 -> 1 -> 5 -> 3.
11. a MemberFunction mergeLists(linkedList& one, linkedList& two) which will create a new list that contains the elements of two lists in sorted order(ascending). Assume the two lists are in sorted order for this case
Ex: one: 1 -> 3 -> 7 -> 25 -> 50 (sorted)
two: 5 -> 9 -> 11 - > 12 -> 29 (sorted)
result list : 1 -> 3 -> 5 -> 7 - > 9 -> 11 -> 12 -> 25 -> 29 -> 50 (Sorted)
Explanation / Answer
Answer of PART-1:
#include<iostream>
using namespace std;
class Node {
public:
double data;
Node *next;
Node(int data):next(NULL) {
this->data = data;
}
};
class CircularLinkedList {
public:
CircularLinkedList *start;
CircularLinkedList():start(NULL) {
}
void createList(int data) //create list
{
Node *temp = new Node(data); //create a new node
Node *q=NULL;
if(start==NULL) //if list is empty
{
start = temp; //new node is first node of the list
}
else //if list is not empty
{
q = start; //pointer to traverse the list
for(;q->next!=start;q=q->next); //move to last node
q->next=temp; //set next address of last node to new node
}
temp->next=start; //set next address of new node to first node
}
void display() //display list
{
Node *q=NULL;
if(start==NULL) //if list is empty
{
cout<<endl<<"List is EMPTY...!!"<<endl;
}
else //if not empty
{
q=start;
cout<<endl<<"List is as follows : "<<endl;
for(;q->next!=start;q=q->next) //traverse the list and print data of each node
{
cout<<q->data<<" ";
}
cout<<q->data<<" ";
}
}
};
int main()
{
CircularLinkedList obj;
int choice,data,n,pos;
cout<<endl<<"-------- Circular Doubly Linked-List --------"<<endl;
while(true)
{
cout<<" 1. Create List 2. Display 3.Exit";
cout<<endl<<"Enter choice: ";
cin>>choice;
switch(choice)
{
case 1: cout<<endl<<"Enter No. of node you want to create in list : ";
cin>>n;
for(int i=1;i<=n;i++)
{
cout<<endl<<"Enter number : ";
cin>>data;
obj.createList(data);
}
break;
case 2: obj.display();
break;
default: return 0;
}
}
}
====================================
Answer of PART-2 :
#include<iostream>
using namespace std;
class Node {
public:
Node *prev;
double data;
Node *next;
Node(int data):prev(NULL),next(NULL) {
this->data = data;
}
};
class DoublyLinkedList {
public:
Node *start;
DoublyLinkedList():start(NULL) { //default constructor
}
DoublyLinkedList(const DoublyLinkedList &other) { //copy constructor
start=other.start;
}
DoublyLinkedList &operator=(const DoublyLinkedList &other) { //overloaded assignment operator
this->start=other.start;
return *this;
}
~DoublyLinkedList() { //destructor
Node *temp = start;
for(;temp!=NULL;) //traverse list and destroy each node
{
start=start->next;
delete temp;
temp=start;
}
}
void pushFront(int data) //add node at front of the list
{
Node *temp = new Node; //create a new node
temp->date=data; //set data to node
if(start==NULL) //if list is empty
{
start=temp; //new node is first node of the list
}
else //if list is not empty
{
temp->next=start; //set next node address of new node to first node in the list
start->prev=temp; //set previous node address of the first node to new node
start=temp; //set new node address to start (make it first node of list)
}
}
void pushBack(int data) //add node at back of the list
{
Node *temp = new Node; //create a new node
temp->date=data; //set data to node
if(start==NULL) //if list is empty
{
start=temp; //new node is first node of the list
}
else //if list is not empty
{
Node *q=start;
for(;q->next!=NULL;q=q->next); //go to last node
q->next=temp; //add new node at last
temp->prev=q;
}
}
void popFront()
{
if (start==NULL)
{
cout<<"List is EMPTY...!!"<<endl;
}
else //delete first node
{
Node *temp=start;
start=start->next;
delete temp;
}
}
void popBack()
{
if(start==NULL)
{
cout<<"List is EMPTY...!!"<<endl;
}
else
{
Node *q=start;
for(;q->next!=NULL;q=q->next); //go to last node
q->prev->next=NULL; //make 2nd last node as new last node
delete q;
}
}
void insert(int index,int data) //add node at specific index
{
int pos=0;
Node *q=NULL;
Node *temp=NULL;
if(start==NULL) //is list is empty
{
cout<<endl<<"List is EMPTY...!!"<<endl;
return;
}
else //if not empty
{
for(q=start;pos<index;q=q->next) //check whether index available or not
{
if(q==NULL)
{
cout<<endl<<"Index "<<position<<" is not available."<<endl;
return;
}
}
temp = new Node;
temp->data=data;
temp->next=q;
temp->prev=q->prev;
q->prev=temp;
}
}
void deleteDuplicates(int key)
{
Node *temp=NULL;
Node *q=NULL;
if(start==NULL) //if list is empty
{
cout<<endl<<"List id EMPTY...!!"<<endl;
}
else
{
for(q=start;q!=NULL;)
{
if(q->data==key)
{
temp=q;
if(q==start) //if first node
{
start=start->next;
start->prev=NULL;
}
else if(q->next==NULL) //if last node
{
q->prev->next=NULL;
}
else //if any node
{
q->prev->next=q->next;
q->next->prev=q->prev;
}
q=q->next;
delete temp;
}
else
{
q=q->next;
}
}
}
}
int size()
{
Node *q=start;
int count=0;
for(;q!=NULL;q=q->next)
{
count++;
}
return count;
}
void reverseList()
{
Node *p1=NULL;
Node *p2=NULL;
Node *p3=NULL;
if(start==NULL) //if list is empty
{
cout<<endl<<"List is EMPTY...!!"<<endl;
}
else if(start->next==NULL) //if list contains only one node
{
cout<<endl<<"List contains only one node"<<endl;
}
else //if list has more than one node
{
p1 = start; //p1 to first node
p2 = p1->next; //p2 to second node
p3 = p2->next; //p3 to third node
p1->next=NULL; //p1 becomes last node
p1->prev=p2;
p2->next=p1; //p2 becomes second last node
p2->prev=p3;
while(p3!=NULL) //traverse list
{
p1=p2;
p2=p3;
p3=p3->next;
p2->next=p1;
p2->prev=p3=;
}
start=p2; //set start node
cout<<endl<<"List got reversed...!!"<<endl;
}
}
int mtoLastElement(int m)
{
int s=size();
m=s-m;
if(m<0)
{
return -1;
}
Node *q=start;
for(int i=0;q!=NULL;q=q->next)
{
if(i==m)
{
return q->data;
}
else
{
i++;
}
}
}
friend ostream& operator<<(ostream& os, const DoublyLinkedList& dll);
DoublyLinkedList* mergeLists(DoublyLinkedList& d1, DoublyLinkedList& d2)
{
DoublyLinkedList* dll=new DoublyLinkedList;
Node* p=d1.start;
Node* q=d2.start;
while (1)
{
if (p == NULL)
{
if(q!=NULL)
{
dll.pushBack(q->data);
q=q->next;
}
else
break;
}
else if (q == NULL)
{
if(p!=NULL)
{
dll.pushBack(p->data);
p=p->next;
}
else
break;
}
if (p->data <= q->data)
{
dll.pushBack(p->data);
p=p->next;
}
else
{
dll.pushBack(q->data);
q=q->next;
}
}
return dll;
}
};
ostream& operator<<(ostream& os, const DoublyLinkedList& dll)
{
Node *q=NULL;
if(dll.start==NULL) //if list is empty
{
cout<<endl<<"List is EMPTY...!!"<<endl;
}
else //if not empty
{
q=dll.start;
cout<<endl<<"List is as follows : "<<endl;
for(;q!=NULL;q=q->next) //traverse the list and print data of each node
{
cout<<q->data<<" ";
}
}
return os;
}
int main()
{
DoublyLinkedList obj;
int choice,data,n,pos;
cout<<endl<<"-------- Doubly Linked-List --------"<<endl;
while(true)
{
cout<<" 1. pushFront 2. pushBack 3. popFront";
cout<<" 4. popBack 5. insert 6. deleteDuplicates 7. mtoLastElement 8.size";
cout<<" 9. display 10. reverse 11. Exit";
cout<<endl<<"Enter choice: ";
cin>>choice;
switch(choice)
{
case 1: cout<<endl<<"Enter number : ";
cin>>data;
obj.pushFront(data);
break;
case 2: cout<<endl<<"Enter number : ";
cin>>data;
obj.pushBack(data);
break;
case 3: obj.popFront();
break;
case 4: obj.popBack();
break;
case 5: cout<<"Enter index : ";
cin>>pos;
cout<<"Enter number: ";
cin>>data;
obj.insert(index,data);
break;
case 6: cout<<endl<<"Enter number : ";
cin>>data;
obj.deleteDuplicates(data);
break;
case 7: cout<<endl<<"Enter number : ";
cin>>data;
cout << "mtoLastElement : "<<obj.mtoLastElement(data);
break;
case 8: cout<<"Size : "<<obj.size();
break;
case 9: cout<<obj;
break;
case 10: obj.reverseList();
break;
default: return 0;
}
}
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.