Write C++ program for listed ADT Part - 1: Implement a CIRCULAR linked list ADT
ID: 3601768 • Letter: W
Question
Write C++ program for listed ADT
Part - 1: Implement a CIRCULAR linked list ADT to store a collection of doubles.
--- 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
#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.