Create a class Node with
a. attributes data, next pointer
b. accessors and mutators
c. constructor and destructor
d. a function called display.
1. Write functions to perform the following operations
a. create a circular singly linked list to perform
i. insertion,
ii. deletion
iii. traversing
b. create a sub menu for merge operations of two circular linked list L1, L2
i. Press 1 to append L1 to L2.
ii. Press 2 to append L2 to L1.
iii. Press 3 to merge L1 and L2 in sorted order.
c. print odd nodes of a circular linked list to divide the circular linked list into two parts into odd and even list?
#include <iostream>
#include <stdlib.h>
#include <time.h>
using namespace std;
class Node{
public:
int data;
Node *next;
Node();
Node(int);
int getData(){
return data;
}
void setData(int data){
this->data = data;
}
Node* getNext(){
return this->next;
}
void setNext(Node *node){
this->next = node;
}
void display(){
cout<<this->data;
}
~Node(){}
};
Node::Node(){
next = NULL;
}
Node::Node(int data){
this->data = data;
next = NULL;
}
class CircularLinkedList{
Node *head, *tail;
int size;
public:
CircularLinkedList();
//insert at head
void insert(int);
//delete at a specified index
void remove(int);
//prints the list
void traverse();
CircularLinkedList merge(CircularLinkedList, CircularLinkedList);
CircularLinkedList connect(CircularLinkedList, CircularLinkedList);
void sort();
int length(){return size;}
};
CircularLinkedList::CircularLinkedList(){
head = NULL;
tail = NULL;
size = 0;
}
void CircularLinkedList::insert(int data){
if(head == NULL){
head = new Node(data);
head->next = tail;
tail = head;
size++;
}
else{
tail->next = new Node(data);
tail = tail->next;
tail->next = head;
size++;
}
}
void CircularLinkedList::traverse(){
Node* curr = head;
if(curr == NULL) return;
do{
curr->display();
cout<<" ";
curr = curr->next;
}while(curr != head);
cout<<endl;
}
void CircularLinkedList::remove(int pos){
if(head != NULL){
int i = 0;
Node *temp = head;
Node *prev = NULL;
while(temp != NULL && i < pos){
prev = temp;
temp = temp->next;
i++;
}
if(pos > size - 1) return;
if(pos == 0){
head = head->next;
size--;
delete temp;
return;
}
if(pos == size - 1){
tail = prev;
tail->next = head;
size--;
delete temp;
return;
}
prev->next = temp->next;
size--;
delete temp;
}
}
CircularLinkedList CircularLinkedList:: merge(CircularLinkedList L1, CircularLinkedList L2){
cout<<"Press 1 to append L1 to L2.\n";
cout<<"Press 2 to append L2 to L1.\n";
cout<<"Press 3 to merge L1 and L2 in sorted order.\n";
int choice;
cin>>choice;
CircularLinkedList res;
switch(choice){
case 1: res = connect(L1, L2); break;
case 2: res = connect(L2, L1); break;
case 3: res = connect(L1, L2); res.sort(); break;
}
return res;
}
CircularLinkedList CircularLinkedList:: connect(CircularLinkedList L1, CircularLinkedList L2){
CircularLinkedList res;
Node *curr = L1.head;
do{
res.insert(curr->data);
curr = curr->next;
}while(curr != L1.head);
curr = L2.head;
do{
res.insert(curr->data);
curr = curr->next;
}while(curr != L2.head);
return res;
}
void CircularLinkedList::sort(){
Node *curr = head;
do{
Node *temp = curr->next;
while(temp != head){
if(temp->data < curr->data){
int temp_data = temp->data;
temp->data = curr->data;
curr->data = temp_data;
}
temp = temp->next;
}
curr = curr->next;
}while(curr != head);
}
int main(){
CircularLinkedList list, list2;
for(int i = 0, j = -10; i < 10; i++, j++){
list.insert(i);
list2.insert(j);
}
cout<<"List 1 = ";
list.traverse();
cout<<"List 2 = ";
list2.traverse();
CircularLinkedList merged = list.merge(list, list2);
merged.traverse();
return 0;
}
Comments