#include<stdio.h>
#include<iostream>
using namespace std;
class linkedlist
{
private:
struct node
{
int key;
node* next;
}*head;
public:
linkedlist();
void insert(int key);
int remove(int key);
void swap(int k);
void print();
int count_node();
int find_key(int key);
bool isempty();
void reverse();
void selection_sort();
void bobble_sort();
void insertion_sort();
void quick_sort();
void merge_sort();
void delete_m_n(int m,int n);
int find_middle();
void reverse_k(int k);
void print_recursive();
void print_rec(node *t);
~linkedlist();
};
linkedlist::linkedlist()
{
head=NULL;
}
void linkedlist::insert(int key)
{
if(isempty())
{head=new node();
head->key=key;
head->next=NULL;
printf("Inserted :\n");
return;
}
struct node *t=new node();
t->key=key;
t->next=head;
head=t;
printf("\n Inserted At Begning \n");
return ;
}
int linkedlist::remove(int key)
{
int val;
if(isempty())
{
printf("\n lsit is empty ");
return -10000;
}
if(head->key==key)
{
struct node *t=head;
head=head->next;
val=t->key;
delete(t);
return val;
}
struct node *t=head;
while(t->next!=NULL)
{
if(t->next->key==key)
{
node *p=t->next;
t->next=t->next->next;
val=p->key;
delete(p);
return val;
}
t=t->next;
}
printf("\n key not present\n");
return -10000;
}
void linkedlist::print()
{
if(isempty())
{
printf("\n lsit is empty \n");
return ;
}
cout<<"\n *************** list is **************************\n";
node *t=head;
while(t)
{
cout<<t->key<< " ";
t=t->next;
}
cout<<"\n *********************************************************\n";
}
void linkedlist::swap(int k)
{
if(isempty())
{
printf("\n List is Empty\n");
return;
}
int n=count_node();
if(k>n)
{
printf("\n list is small to perform swap operation\n");
return ;
}
if(2*k-1==n)
return;
int r=n-k+1;
int i=1;
struct node *x=head;
struct node *x_prev=NULL;
while(i<k)
{
x_prev=x;
x=x->next;
i++;
}
i=1;
struct node *y=head;
struct node *y_prev=NULL;
while(i<r)
{
y_prev=y;
y=y->next;
i++;
}
/*if(k==r-1||k==r+1)
{
forward_node->next=backward_node->next;
backward_node->next=backward_node->next->next;
forward_node->next->next=backward_node;
}
else
{
struct node * p=forward_node->next;
struct node * q=forward_node->next->next;
forward_next->next=backward_node->next;
p->next=backward_node->next->next;
backward_node->next->next=q;
backward_node->next=p;
}
if(k==1)
*/
if(x_prev)
x_prev->next=y;
if(y_prev)
y_prev->next=x;
node *temp = x->next;
x->next = y->next;
y->next = temp;
if(k==1)
head=y;
if(k==n)
head=x;
}
int linkedlist ::count_node()
{
int count=0;
struct node *t=head;
while(t!=NULL)
{
t=t->next;
count++;
}
return count;
}
bool linkedlist::isempty()
{
if(head==NULL)
return true;
return false;
}
linkedlist::~linkedlist()
{
node *t=head;
while(head!=NULL)
{
t=head;
head=head->next;
delete(t);
}
}
void linkedlist::reverse()
{
if(isempty())
return;
if(head->next==NULL)
return ;
node *p=head;
node *q=head->next;
p->next=NULL;
while(q)
{
p=q;
q=q->next;
p->next=head;
head=p;
}
}
void linkedlist::delete_m_n(int m,int n)
{
if(n==0)
return;
node *p=head;
node *r,*s;
int i=1;
int j=1;
while(p!=NULL)
{
if(i==m&&p->next!=NULL)
{
//printf("\n ram\n");
r=p;
p=p->next;
s=p;
while(p->next!=NULL&&j<n)
{
//cout<<p->key<<endl;
p=p->next;
j++;
}
if(p->next==NULL)
{
r->next=NULL;
}
else
{
i=1;j=1;
//cout<<p->key<<endl;
r->next=p->next;
p->next=NULL;
p=r->next;
continue;
}
while(s!=NULL)
{
node *t=s;
s=s->next;
delete t;
}
//cout<<p->key<<endl<<i<<endl;
}
i++;
p=p->next;
}
}
int linkedlist::find_middle()
{
node *p,*q;
p=head;
q=head;
while(q->next!=NULL&&q->next->next!=NULL)
{
p=p->next;
q=q->next->next;
}
return p->key;
}
void linkedlist::reverse_k(int k)
{
node *p=head;
}
void linkedlist::print_rec(node *t)
{
if(t==NULL)
return;
printf("\n %d",t->key);
print_rec(t->next);
}
void linkedlist::print_recursive()
{
print_rec(head);
}
int main()
{
linkedlist l;
l.insert(10);
l.insert(20);
l.insert(30);
l.insert(100);
l.insert(2);
l.insert(4);
l.insert(50);
l.insert(-10);
l.insert(76);
l.insert(89);
l.insert(0);
l.insert(17);
cout<<l.count_node();
l.print();
//l.swap(4);
l.reverse();
l.print();
//int a,b;
//cin>>a>>b;
l.delete_m_n(1,4);
l.print();
//cout<<l.find_middle();
l.print_recursive();
return 0;
}
No comments:
Post a Comment