Homework SourseCreate a LinkedList Class in C to manipulate Node objects Th
Create a LinkedList Class in C++ to manipulate Node objects. This class must be able to handle (1) singly, (2) doubly, (3) singly-circularly, and (4) doubly-circularly linked list. When the list is created, it must be given input to which type of list it will be.
Your class must at least have the following public prototypes implemented.
bool perform_operation(int op_code, T value);
Your class must at least have the following private prototypes implemented.
void append(Node* n);
void remove_tail();
void push(Node* n);
Node* pop();
void remove_i(int i);
Node* get_i(int i);
void add_i(Node* n, int i);
void print();
void delete();
void reverse();
void rotate(int rotations);
void random_shuffle();
int size();
Solution
As the code is big, for your better understanding i seperately wrote the code, you can club the code and use
//singly
#include <iostream>
using namespace std;
// Node class
class Node {
int data;
Node* next;
public:
Node() {};
void SetData(int aData) { data = aData; };
void SetNext(Node* aNext) { next = aNext; };
int Data() { return data; };
Node* Next() { return next; };
};
// List class
class List {
Node *head;
public:
List() { head = NULL; };
void Print();
void Append(int data);
void Delete(int data);
};
void List::Print() {
Node *tmp = head;
// No nodes
if ( tmp == NULL ) {
cout << \"EMPTY\" << endl;
return;
}
if ( tmp->Next() == NULL ) {
cout << tmp->Data();
cout << \" --> \";
cout << \"NULL\" << endl;
}
else {
do {
cout << tmp->Data();
cout << \" --> \";
tmp = tmp->Next();
}
while ( tmp != NULL );
cout << \"NULL\" << endl;
}
}
void List::Append(int data) {
// Create a new node
Node* newNode = new Node();
newNode->SetData(data);
newNode->SetNext(NULL);
Node *tmp = head;
if ( tmp != NULL ) {
// Nodes already present in the list
while ( tmp->Next() != NULL ) {
tmp = tmp->Next();
}
tmp->SetNext(newNode);
}
else {
head = newNode;
}
}
/**
* Delete a node from the list
*/
void List::Delete(int data) {
Node *tmp = head;
if ( tmp == NULL )
return;
if ( tmp->Next() == NULL ) {
delete tmp;
head = NULL;
}
else {
Node *prev;
do {
if ( tmp->Data() == data ) break;
prev = tmp;
tmp = tmp->Next();
} while ( tmp != NULL );
// Adjust the pointers
prev->SetNext(tmp->Next());
// Delete the current node
delete tmp;
}
}
int main()
{
// New list
List list;
list.Append(100);
list.Print();
list.Append(200);
list.Print();
list.Append(300);
list.Print();
list.Append(400);
list.Print();
list.Append(500);
list.Print();
// Delete nodes from the list
list.Delete(400);
list.Print();
list.Delete(300);
list.Print();
list.Delete(200);
list.Print();
list.Delete(500);
list.Print();
list.Delete(100);
list.Print();
}
// doubly
#include<iostream>
usingnamespace std;
struct node
{
int data;
node *next;
node *prev;
};
void addnode();
void delnode();
void display();
void show();
void search();
node *start=NULL, *temp1, *temp2, *temp3;
int main()
{
char ch;
do
{
char i;
cout<<\"Press \'a\' to add node , \'d\' to delete\"<<endl;
cout<<\" \'s\' for search, \'v\' for display ,\'e\' for backward display\"<<endl;
cin>>i;
switch (i)
{
case\'a\':
addnode();
break;
case\'d\':
delnode();
break;
case\'v\' :
display();
break;
case\'s\':
search();
break;
case\'e\':
show();
break;
default:
cout<<\"Bad input\"<<endl;
break;
}
cout<<\"want to process more y/n\"<<endl;
cin>>ch;
}
while(ch!=\'n\');
return 0;
}
void addnode()
{
char r;
temp1=new node;
cout<<\"enter int to store\"<<endl;
cin>>temp1->data;
cout<<\"press \'s\' to add in start,\'m\' for midd , \'e\' for end\"<<endl;
cin>>r;
switch (r)
{
case\'s\': //add startif(start==NULL)
{
start=temp1;
temp1->next=NULL;
temp1->prev=NULL;
}
else
{
temp2=start;
temp1->next=temp2;
temp1->prev=NULL;
start=temp1;
temp2->prev=temp1;
}
break;
case\'e\':
{
start=temp1;
temp1->next=NULL;
temp1->prev=NULL;
}
else
{
temp2=start;
while(temp2->next!=NULL)
temp2=temp2->next;
temp2->next=temp1;
temp1->prev=temp2;
temp1->next=NULL;
}
break;
case\'m\': //add midint num;
cout<<\"enter node after which you want to enter\"<<endl;
cin>>num;
temp2=start;
for(int i=0;i<num;i++)
{
if(start==NULL)
cout<<\"given node not found\"<<endl;
else
{
temp3=temp2;
temp2=temp2->next;
}
}
temp1->next=temp2;
temp3->next=temp1;
temp1->prev=temp3;
temp2->prev=temp1;
break;
}
}
void display() //displaying
{
temp3=start;
if(start==NULL)
cout<<\"no node to display\"<<endl;
else
{
while(temp3->next!=NULL)
{
cout<<\"Data stored is \"<<temp3->data<<\" at \"<<temp3<<endl;
temp3=temp3->next;
}
cout<<\"Data stored is \"<<temp3->data<<\" at \"<<temp3<<endl;
}
}
void search() //searching
{
int p;
cout<<\"enter no to search\"<<endl;
cin>>p;
temp1=start;
while(temp1->next!=NULL)
{
if(temp1->data==p)
{
cout<<temp1->data<<\" is stored in \"<< temp1->next<<endl;
}
temp1=temp1->next;
}
}
void delnode() //deleting
{
char d;
cout<<\"press \'s\' to delete from start,\'m\' for midd , \'e\' for end\"<<endl;
cin>>d;
switch (d)
{
case\'s\': //delete startif(start==NULL)
{
cout<<\"no node to delete\"<<endl;
}
else
{
temp1=start;
start=start->next;
start->prev=NULL;
delete temp1;
}
break;
case\'e\':
{
cout<<\"no node to delete\"<<endl;
}
else
{
temp1=start;
while(temp1->next!=NULL)
{
temp2=temp1;
temp1=temp1->next;
}
delete temp1;
temp2->next=NULL;
}
break;
case\'m\':
cout<<\"enter node you want to delete\"<<endl;
cin>>num;
temp1=start;
for(int i=1;i<num;i++)
{
if(start==NULL)
cout<<\"given node does not exist\"<<endl;
else
{
temp2=temp1;
temp1=temp1->next;
}
}
temp3=temp1->next;
temp2->next=temp3;
temp3->prev=temp2;
delete temp1;
break;
}
}
void show()
{
cout<<\"backward display\"<<endl;
temp3=start;
if(start==NULL)
cout<<\"no node to display\"<<endl;
else
{
while(temp3->next!=NULL)
{
temp3=temp3->next;
}
while(temp3->prev!=NULL)
{
cout<<\"Data stored is \"<<temp3->data<<\" at \"<<temp3<<endl;
temp3=temp3->prev;
}
cout<<\"Data stored is \"<<temp3->data<<\" at \"<<temp3<<endl;
}
}
// singly-circularly
#include <iostream.h>
#include <string.h>
struct SLinkList
{
int data;
SLinkList *next;
SLinkList();
SLinkList(int value);
SLinkList* InsertNext(int value);
int DeleteNext();
void Traverse(SLinkList *node = NULL);
};
SLinkList::SLinkList() : data(0), next(NULL)
{
}
SLinkList::SLinkList(int value) : data(value), next(NULL)
{
}
SLinkList* SLinkList::InsertNext(int value)
{
SLinkList *node = new SLinkList(value);
if(this->next == NULL)
{
// Easy to handle
node->next = NULL; // already set in constructor
this->next = node;
}
else
{
// Insert in the middle
SLinkList *temp = this->next;
node->next = temp;
this->next = node;
}
return node;
}
int SLinkList::DeleteNext()
{
if(this->next == NULL)
return 0;
SLinkList *pNode = this->next;
this->next = this->next->next; // can be NULL here
delete pNode;
return 1;
}
void SLinkList::Traverse(SLinkList *node)
{
if(node == NULL)
node = this;
cout << \"\ \ Traversing in Forward Direction\ \ \";
while(node != NULL)
{
cout << node->data;
cout << \"\ \";
node = node->next;
}
}
int main()
{
SLinkList *node1 = new SLinkList(1);
SLinkList *node2 = node1->InsertNext(2);
SLinkList *node3 = node2->InsertNext(3);
SLinkList *node4 = node3->InsertNext(4);
SLinkList *node5 = node4->InsertNext(5);
node1->Traverse();
node3->DeleteNext(); // delete the node \"FOUR\"
node2->Traverse();
cout << \"\ \";
return 0;
}
//doubly- circularly
#include<iostream>
#include<stdlib.h>
using namespace std;
class Node {
public:
int data;
Node *next;
Node *prev;
}*head;
class DoublyCirc{
public: DoublyCirc();
Node *CreateNode();
void insertatfirst();
void insertatlast();
void insertatmid();
int search();
void display();
void reverse();
void deleteatfirst();
void deleteatlast();
void deleteatmid();
void edit();
};
int main() {
DoublyCirc S;
int choice;
while(1) {
cout<<\"\ \ \ \\t\\tMENU\"
<<\"\ 1. Insert As First Node\"
<<\"\ 2. Insert After a Node\"
<<\"\ 3. Insert As Last Node\"
<<\"\ 4. Search \"
<<\"\ 5. Display\"
<<\"\ 6. Delete First Node\"
<<\"\ 7. Delete Last Node\"
<<\"\ 8. Delete A Particular Node\"
<<\"\ 9. Edit Data\"
<<\"\ 10. Reverse The List\"
<<\"\ 11. Exit\"
<<\"\ Enter your choice: \";
cin>>choice;
switch(choice) {
case 1: S.insertatfirst(); break;
case 2: S.insertatmid(); break;
case 3: S.insertatlast(); break;
case 4: int posn;
posn=S.search();
if(posn==0)
cout<<\"\ Element Doesnot Exists \";
else
cout<<\"\ Element is at Location no: \"<<posn;
break;
case 5: S.display(); break;
case 6: S.deleteatfirst(); break;
case 7: S.deleteatlast(); break;
case 8: S.deleteatmid(); break;
case 9: S.edit(); break;
case 10: S.reverse(); break;
case 11: exit(0);
default: cout<<\"\ Invalid Choice Entered!!! \";
}
}
return 0;
}
DoublyCirc::DoublyCirc() {
head=NULL;
}
Node* DoublyCirc::CreateNode() {
Node *newptr;
int data;
newptr=new Node;
cout<<\"\ Enter Data: \";
cin>>data;
newptr->data=data;
newptr->next=NULL;
newptr->prev=NULL;
return newptr;
}
void DoublyCirc::insertatfirst() {
Node *newnode;
newnode=CreateNode();
if(head==NULL) {
newnode->next=newnode;
newnode->prev=newnode;
head=newnode;
}
else {
Node *temp;
temp=head;
newnode->next=temp;
newnode->prev=temp->prev;
temp->prev->next=newnode;
temp->prev=newnode;
head=newnode;
}
}
void DoublyCirc::display() {
if(head==NULL) {
cout<<\"\ Empty Linked List!!! \";
}
else {
int choice;
cout<<\"\ 1. Display From Head\"
<<\"\ 2. Display From Reverse\"
<<\"\ 3. Enter Choice: \";
cin>>choice;
Node *temp;
cout<<endl;
switch(choice) {
case 1: temp=head;
while(temp->next!=head) {
cout<<temp->data<<\"\\t\";
temp=temp->next;
}
cout<<temp->data;
break;
case 2: temp=head->prev;
while(temp->prev!=head->prev) {
cout<<temp->data<<\"\\t\";
temp=temp->prev;
}
cout<<temp->data;
break;
default: cout<<\"\ Wrong Choice\";
}
}
}
void DoublyCirc::insertatlast() {
Node *newnode;
newnode=CreateNode();
if(head==NULL) {
head=newnode;
newnode->next=newnode;
newnode->prev=newnode;
}
else {
Node *temp;
temp=head;
temp=temp->prev;
newnode->next=head;
newnode->prev=temp;
temp->next=newnode;
head->prev=newnode;
}
}
int DoublyCirc::search() {
if(head==NULL) {
cout<<\"\ Empty Linked List\";
return 0;
}
cout<<\"\ Elements of Linked List are: \"<<endl;
display();
int data,posn;
cout<<\"\ Enter the data you want to operate upon: \";
cin>>data;
Node *temp;
temp=head;
posn=1;
while(temp->next!=head) {
if(temp->data==data)
return posn;
posn++;
temp=temp->next;
}
if(temp->data==data)
return posn;
cout<<\"reached end of search\";
return 0;
}
void DoublyCirc::insertatmid() {
int no;
no=search();
cout<<\"\ Posn=\"<<no;
if(no==0) {
insertatfirst();
return;
}
Node *newnode,*p,*l;
newnode=CreateNode();
p=head;
for(int i=1;i<no;i++)
p=p->next;
l=p->next;
p->next=newnode;
newnode->next=l;
l->prev=newnode;
newnode->prev=p;
}
void DoublyCirc::deleteatfirst() {
if(head==NULL) {
cout<<\"\ Empty Linked List!!!\";
return;
}
if(head->next==head) {
head=NULL;
return;
}
Node *temp,*nhead;
temp=head;
nhead=head->next;
nhead->prev=temp->prev;
temp->prev->next=nhead;
head=nhead;
delete(temp);
}
void DoublyCirc::deleteatlast() {
if(head==NULL) {
cout<<\"\ Empty Linked List!!!\";
return;
}
if(head->next==head) {
head=NULL;
return;
}
Node *temp,*nlast;
temp=head->prev;
nlast=temp->prev;
nlast->next=head;
head->prev=nlast;
delete(temp);
}
void DoublyCirc::deleteatmid() {
if(head==NULL) {
cout<<\"\ Empty Linked List!!!\";
return;
}
int no;
no=search();
if(no==1) {
deleteatfirst();
return;
}
Node *p,*l,*temp;
p=head;
for(int i=1;i<no;i++)
p=p->next;
temp=p;
l=p->next;
p=p->prev;
p->next=l;
l->prev=p;
delete(temp);
}
void DoublyCirc::edit() {
if(head==NULL) {
cout<<\"\ Empty Linked List!!!\";
return;
}
int no,data;
no=search();
Node *temp;
temp=head;
for(int i=1; i<no; i++)
temp=temp->next;
cout<<\"\ Enter new data: \";
cin>>data;
temp->data=data;
}
void DoublyCirc::reverse() {
if(head==NULL) {
cout<<\"\ Empty List\";
return;
}
Node *temp,*p;
temp=head;
p=head->prev;
while(temp!=p) {
swap(temp->data,p->data);
temp=temp->next;
if(temp==p) return;
p=p->prev;
}
}
