Showing posts with label Linked list. Show all posts
Sorted Doubly Linked List with Insertion and Deletion
Tuesday, 29 April 2014
Posted by Naveen's Blogs
Tag :
Data Structures,
Linked list
#include < iostream >
#include < cstdlib >
#include < string >
using namespace std;
class Dllist
{
private:
typedef struct Node
{
string name;
Node* next;
Node* prev;
};
Node* head;
Node* last;
public:
Dllist()
{
head = NULL;
last = NULL;
}
bool empty() const { return head==NULL; }
friend ostream& operator <<(ostream& ,const Dllist& );
void Insert(const string& );
void Remove(const string& );
};
void Dllist::Insert(const string& s)
{
// Insertion into an Empty List.
if(empty())
{
Node* temp = new Node;
head = temp;
last = temp;
temp->prev = NULL;
temp->next = NULL;
temp->name = s;
}
else
{
Node* curr;
curr = head;
while( s>curr->name && curr->next != last->next) curr = curr->next;
if(curr == head)
{
Node* temp = new Node;
temp->name = s;
temp->prev = curr;
temp->next = NULL;
head->next = temp;
last = temp;
// cout<<" Inserted "<< s <<" After "<< curr->name << endl;
}
else
{
if(curr == last && s>last->name)
{
last->next = new Node;
(last->next)->prev = last;
last = last->next;
last->next = NULL;
last->name = s;
// cout<<" Added "<< s <<" at the end "<< endl;
}
else
{
Node* temp = new Node;
temp->name = s;
temp->next = curr;
(curr->prev)->next = temp;
temp->prev = curr->prev;
curr->prev = temp;
// cout<<" Inserted "<< s <<" Before "<< curr->name<< endl;
}
}
}
}
ostream& operator<<(ostream& ostr, const Dllist& dl )
{
if(dl.empty()) ostr << " The list is empty. "<< endl;
else
{
Dllist::Node* curr;
for(curr = dl.head; curr != dl.last->next; curr=curr->next)
ostr << curr->name <<" ";
ostr << endl;
ostr << endl;
return ostr;
}
}
void Dllist::Remove(const string& s)
{
bool found = false;
if(empty())
{
cout<<" This is an empty list! "<< endl;
return;
}
else
{
Node* curr;
for(curr = head; curr != last->next; curr = curr->next)
{
if(curr->name == s)
{
found = true;
break;
}
}
if(found == false)
{
cout<<" The list does not contain specified Node"< return;
}
else
{
// Curr points to the node to be removed.
if (curr == head && found)
{
if(curr->next != NULL)
{
head = curr->next;
delete curr;
return;
}
else
{
delete curr;
head = NULL;
last = NULL;
return;
}
}
if (curr == last && found)
{
last = curr->prev;
delete curr;
return;
}
(curr->prev)->next = curr->next;
(curr->next)->prev = curr->prev;
delete curr;
}
}
}
int main()
{
Dllist d1;
int ch;
string temp;
while(1)
{
cout<< endl;
cout<<" Doubly Linked List Operations "<< endl;
cout<<" ------------------------------"<< endl;
cout<<" 1. Insertion "<< endl;
cout<<" 2. Deletion "<< endl;
cout<<" 3. Display "<< endl;
cout<<" 4. Exit "<< endl;
cout<<" Enter your choice : ";
cin>>ch;
switch(ch)
{
case 1: cout<<" Enter Name to be inserted : ";
cin>>temp;
d1.Insert(temp);
break;
case 2: cout<<" Enter Name to be deleted : ";
cin>>temp;
d1.Remove(temp);
break;
case 3: cout<<" The List contains : ";
cout<< d1;
break;
case 4: system("pause");
return 0;
break;
}
}
}
#include< iostream.h >
#include< conio.h >
#include< stdlib.h >
class list
{
struct node
{
int data;
node *link;
}*p;
public:
void inslast(int);
void insbeg(int);
void insnext(int,int);
void delelement(int);
void delbeg();
void dellast();
void disp();
int seek(int);
list(){p=NULL;}
~list();
};
void list::inslast(int x)
{
node *q,*t;
if(p==NULL)
{
p=new node;
p->data=x;
p->link=NULL;
}
else
{
q=p;
while(q->link!=NULL)
q=q->link;
t=new node;
t->data=x;
t->link=NULL;
q->link=t;
}
cout<<"Inserted successfully at the end..";
disp();
}
void list:: insbeg(int x)
{
node *q;
q=p;
p=new node;
p->data=x;
p->link=q;
cout<<"Inserted successfully at the begining..";
disp();
}
void list::delelement(int x)
{
node *q,*r;
q=p;
if(q->data==x)
{
p=q->link;
delete q;
return;
}
r=q;
while(q!=NULL)
{
if(q->data==x)
{
r->link=q->link;
delete q;
return;
}
r=q;
q=q->link;
}
cout<<"Element u entered "<< x <<" is not found..";
}
void list:: delbeg()
{
cout<<"The list before deletion:";
disp();
node *q;
q=p;
if(q==NULL)
{
cout<<"No data is present..";
return;
}
p=q->link;
delete q;
return;
}
void list:: dellast()
{
cout<<"The list before deletion:";
disp();
node *q,*t;
q=p;
if(q==NULL)
{
cout<<"There is no data in the list..";
return;
}
if(q->link==NULL)
{
p=q->link;
delete q;
return;
}
while(q->link->link!=NULL)
q=q->link;
q->link=NULL;
return;
}
list::~list()
{
node *q;
if(p==NULL) return;
while(p!=NULL)
{
q=p->link;
delete p;
p=q;
}
}
void list::disp()
{
node *q;
q=p;
if(q==NULL)
{
cout<<" No data is in the list..";
return;
}
cout<<"The items present in the list are :";
while(q!=NULL)
{
cout<<" "<< q->data;
q=q->link;
}
}
void list :: insnext(int value,int position)
{
node *temp,*temp1;
temp=p;
if(temp1==NULL)
{
temp1= new node;
temp1->data=value;
temp1->link=NULL;
p=temp1;
return;
}
for(int i=0;((i< position) && (temp->link!=NULL)) ;i++)
{
if(i==(position-1))
{
temp1= new node;
temp1->data= value;
temp1->link=temp->link;
temp->link=temp1;
}
temp=temp->link;
}
//cout<<"Inserted successfully at the position.."<< position;
disp();
}
int list::seek(int value)
{
node *temp;
temp=p;
int position=0;
while(temp!=NULL)
{
if(temp->data==value)
return position+1;
else
{
temp=temp->link;
position=position+1;
}
}
cout<<"Element "<< value <<" not found";
return 0;
}
void main()
{
list l;
int ch,v,p,ps;
do
{
clrscr();
cout<<"Operations on List..";
cout<<"
1.Insertion
2.Deletion
3.Display
4.Seek
5.Exit";
cout<<" Enter ur choice:";
cin>>ch;
switch(ch)
{
case 1:
cout<<"1.Insertion at begining
2.Insertion at the end";
cout<<"3.Insertion after the mentioned position";
cout<<"Enter ur choice:";
cin>>ps;
cout<<" Enter the value to insert:";
cin>>v;
switch(ps)
{
case 1:
l.insbeg(v);
break;
case 2:
l.inslast(v);
break;
case 3:
cout << "Enter the position to insert the value:";
cin>>p;
l.insnext(v,p);
break;
default:
cout<<"The choice is invalid";
return;
}
break;
case 2:
cout<<"1.Delete the first element
2.Delete the last element";
cout<<"3.Enter the element to delete from the list";
cout<<"Enter ur choice:";
cin>>ps;
switch(ps)
{
case 1:
l.delbeg();
cout<<"The list after deletion:";
l.disp();
break;
case 2:
l.dellast();
cout<<"The list after deletion:";
l.disp();
break;
case 3:
l.disp();
cout<<"Enter the element to delete : ";
cin>>v;
l.delelement(v);
cout<<"The list after deletion:";
l.disp();
break;
default:
cout<<"The option is invalid...";
break;
}
break;
case 3:
l.disp();
break;
case 4:
l.disp();
cout<<"Enter the element to search:";
cin>>v;
cout<<" The position of the element "<< v <<" is "<< l.seek(v);
getch();
break;
case 5:
exit(1);
default:
cout<<"The option is invalid...";
return;
}
getch();
}while(ch!=5);
getch();
return;
}
Merge Two Sorted Linked List To Form A Third Linked List
Posted by Naveen's Blogs
Tag :
Data Structures,
Linked list
#include< iostream.h >
#include< conio.h >
#include< process.h >
// Creating a NODE Structure
struct node
{
int data; // data
struct node *next; // link to next node and previous node
};
// Creating a class LIST
class list
{
struct node *start;
public:
void create(); // to create a list
void show(); // show
void merge(list,list); // Merge two list's
};
// Main function
int main()
{
clrscr();
list l1,l2,l3;
cout<<"Enter the First List in ascending order.";
l1.create(); // to create a first list
cout<<"Enter the Second List in ascending order.";
l2.create(); // to create a second list
cout<<"The first list is";
l1.show();
cout<<"The second list is";
l2.show();
l3.merge(l1,l2);
l3.show();
getch();
return (0);
}
// Functions
// Creating a new node
void list::create()
{
struct node *nxt_node,*pre_node;
int value,no,i;
start=nxt_node=pre_node=NULL;
cout<<"How many nodes : ";
cin>>no;
cout<<"Enter "<< no <<" Elements: ";
for(i=1;i<=no;i++)
{
cin>>value;
nxt_node=new node;
nxt_node->data=value;
nxt_node->next=NULL;
if(start==NULL)
start=nxt_node;
else
pre_node->next=nxt_node;
pre_node=nxt_node;
}
cout<<"The list is created!";
}
// Displaying LIST
void list::show()
{
struct node *ptr=start;
cout<<"The List is ";
while(ptr!=NULL)
{
cout<< ptr->data<<" -> ";
ptr=ptr->next;
}
cout<<" ";
}
void list::merge(list l1,list l2)
{
struct node *nxt_node,*pre_node,*pptr,*qptr;
int dat;
pptr=l1.start;
qptr=l2.start;
start=nxt_node=pre_node=NULL;
while(pptr!=NULL && qptr!=NULL)
{
if(pptr->data<=qptr->data)
{
dat=pptr->data;
pptr=pptr->next;
}
else
{
dat=qptr->data;
qptr=qptr->next;
}
nxt_node=new node;
nxt_node->data=dat;
nxt_node->next=NULL;
if(start==NULL)
start=nxt_node;
else
pre_node->next=nxt_node;
pre_node=nxt_node;
}
if(pptr==NULL)
{
while(qptr!=NULL)
{
nxt_node=new node;
nxt_node->data=qptr->data;
nxt_node->next=NULL;
if(start==NULL)
start=nxt_node;
else
pre_node->next=nxt_node;
pre_node=nxt_node;
qptr=qptr->next;
}
}
else if(qptr==NULL)
{
while(pptr!=NULL)
{
nxt_node=new node;
nxt_node->data=pptr->data;
nxt_node->next=NULL;
if(start==NULL)
start=nxt_node;
else
pre_node->next=nxt_node;
pre_node=nxt_node;
pptr=pptr->next;
}
}
cout<<"The lists are merged.";
return;
}
Inserting, deleting and displaying elements in the Double Circular Linked List
Posted by Naveen's Blogs
Tag :
Data Structures,
Linked list
#include< iostream.h >
#include< conio.h >
class cirdlink
{
struct node
{
int data;
node *rnext;
node *lnext;
}*new1,*head,*tail,*ptr,*temp;
public:
cirdlink()
{
head=tail=NULL;
}
void creation();
void insertion();
void deletion();
void display();
};
void cirdlink :: creation()
{
if(head==NULL)
{
new1=new node[sizeof(node)];
new1->rnext=NULL;
new1->lnext=NULL;
cout<<"enter student number :";
cin>>new1->data;
head=new1;
tail=new1;
head->rnext=tail;
head->lnext=tail;
tail->rnext=head;
tail->lnext=head;
}
else
cout<<" creation done only once !";
}
void cirdlink :: insertion()
{
int i,pos;
new1=new node[sizeof(node)];
new1->rnext=NULL;
new1->lnext=NULL;
cout<<"enter student number :";
cin>>new1->data;
cout<<"enter position you want to insert :";
cin>>pos;
if(pos==1)
{
new1->rnext=head;
head=new1;
tail->lnext=head;
tail->rnext=head;
head->lnext=tail;
}
else
{
i=1;
temp=head;
while(i < pos-1 && temp->rnext!=tail)
{
i++;
temp=temp->rnext;
}
if(temp->rnext==tail)
{
new1->rnext=tail->rnext;
tail->rnext=new1;
new1->lnext=tail;
tail=new1;
head->lnext=tail;
}
else
{
new1->rnext=temp->rnext;
new1->lnext=temp;
temp->rnext=new1;
new1->rnext->lnext=new1;
}
}
}
void cirdlink :: deletion()
{
int pos,i;
cout<<"Enter Position you want to Delete ?";
cin>>pos;
if(pos==1 && head!=tail)
{
ptr=head;
head=head->rnext;
head->lnext=tail;
tail->rnext=head;
delete ptr;
}
else
{
i=1;
temp=head;
while(i < pos-1 && temp->rnext!=tail)
{
i++;
temp=temp->rnext;
}
if(temp->rnext!=tail)
{
ptr=temp->rnext;
temp->rnext=ptr->rnext;
ptr->rnext->lnext=ptr->lnext;
delete ptr;
}
else
{
if(temp->rnext==tail && head!=tail)
{
ptr=tail;
tail=temp;
tail->rnext=head;
head->lnext=tail;
delete ptr;
}
else
{
head=NULL;
tail=NULL;
delete head;
delete tail;
}
}
}
}
void cirdlink::display()
{
int ch;
cout<<"1.forward
2.backward:";
cout<<"Enter your choice<1/2>?";
cin>>ch;
switch(ch)
{
case 1: if(head!=NULL)
{
temp=head;
while(temp!=tail)
{
cout<< temp->data<<" ";
temp=temp->rnext;
}
if(temp==tail)
cout<< temp->data;
}
break;
case 2 : if(tail!=NULL)
{
temp=tail;
while(temp!=head)
{
cout<< temp->data<<" ";
temp=temp->lnext;
}
if(temp==head)
cout<< temp->data;
}
break;
}
}
void main()
{
cirdlink c1;
int ch;
char op;
do
{
clrscr();
cout<<"----------Menu------------";
cout<<" 1.Creation
2.Insertion
3.Deletion
4.Display ";
cout<<"Enter Your choice <1..4> ?";
cin>>ch;
switch(ch)
{
case 1 : c1.creation();
break;
case 2 : c1.insertion();
break;
case 3 : c1.deletion();
break;
case 4 : c1.display();
break;
}
cout<<"Do you want to continue < Y/N > ?";
cin>>op;
}while(op=='y' || op=='Y');
getch();
}
#include < iostream >
#include < cstdlib >
#include < string >
using namespace std;
class Dllist
{
private:
typedef struct Node
{
string name;
Node* next;
Node* prev;
};
Node* head;
Node* last;
public:
Dllist()
{
head = NULL;
last = NULL;
}
bool empty() const { return head==NULL; }
friend ostream& operator<<(ostream& ,const Dllist& );
void Insert(const string& );
void Remove(const string& );
};
void Dllist::Insert(const string& s)
{
// Insertion into an Empty List.
if(empty())
{
Node* temp = new Node;
head = temp;
last = temp;
temp->prev = NULL;
temp->next = NULL;
temp->name = s;
}
else
{
Node* curr;
curr = head;
while( s>curr->name && curr->next != last->next)
curr = curr->next;
if(curr == head)
{
Node* temp = new Node;
temp->name = s;
temp->prev = curr;
temp->next = NULL;
head->next = temp;
last = temp;
// cout<<" Inserted "<< s <<" After " << curr->name << endl;
}
else
{
if(curr == last && s>last->name)
{
last->next = new Node;
(last->next)->prev = last;
last = last->next;
last->next = NULL;
last->name = s;
// cout<<" Added "<< s <<" at the end "<< endl;
}
else
{
Node* temp = new Node;
temp->name = s;
temp->next = curr;
(curr->prev)->next = temp;
temp->prev = curr->prev;
curr->prev = temp;
// cout<<" Inserted "<< s <<" Before "<< curr->name << endl;
}
}
}
}
ostream& operator<<(ostream& ostr, const Dllist& dl )
{
if(dl.empty()) ostr<<" The list is empty. "<< endl;
else
{
Dllist::Node* curr;
for(curr = dl.head; curr != dl.last->next; curr=curr->next)
ostr<< curr->name<<" ";
ostr<< endl;
ostr<< endl;
return ostr;
}
}
void Dllist::Remove(const string& s)
{
bool found = false;
if(empty())
{
cout<<" This is an empty list! "<< endl;
return;
}
else
{
Node* curr;
for(curr = head; curr != last->next; curr = curr->next)
{
if(curr->name == s)
{
found = true;
break;
}
}
if(found == false)
{
cout<<" The list does not contain specified Node"<< endl;
return;
}
else
{
// Curr points to the node to be removed.
if (curr == head && found)
{
if(curr->next != NULL)
{
head = curr->next;
delete curr;
return;
}
else
{
delete curr;
head = NULL;
last = NULL;
return;
}
}
if (curr == last && found)
{
last = curr->prev;
delete curr;
return;
}
(curr->prev)->next = curr->next;
(curr->next)->prev = curr->prev;
delete curr;
}
}
}
int main()
{
Dllist d1;
int ch;
string temp;
while(1)
{
cout<< endl;
cout<<" Doubly Linked List Operations "<< endl;
cout<<" ------------------------------"<< endl;
cout<<" 1. Insertion "<< endl;
cout<<" 2. Deletion "<< endl;
cout<<" 3. Display "<< endl;
cout<<" 4. Exit "<< endl;
cout<<" Enter your choice : ";
cin>>ch;
switch(ch)
{
case 1: cout<<" Enter Name to be inserted : ";
cin>>temp;
d1.Insert(temp);
break;
case 2: cout<<" Enter Name to be deleted : ";
cin>>temp;
d1.Remove(temp);
break;
case 3: cout<<" The List contains : ";
cout<< d1;
break;
case 4: system("pause");
return 0;
break;
}
}
}
Appending Two Linked List based upon two data members
Posted by Naveen's Blogs
Tag :
Data Structures,
Linked list
#include<iostream>
using namespace std;
class CClass1
{
public:
char mStringData[10];;
long int mDataMember1;
long int mDataMember2;
CClass1 *structpNextValue;
void SetValue(CString string, long int a, long int b)
{
strcpy(mStringData, string);
mDataMember1 = a;
mDataMember2 = b;
}
CClass1(void);
~CClass1(void);
};
class CClass2
{
public:
char mStringData[10];
long int mDataMember1;
long int mDataMember2;
CClass2 *structpNextValue;
void SetValue(CString string, long int a, long int b)
{
strcpy(mStringData, string);
mDataMember1 = a;
mDataMember2 = b;
}
CClass2(void);
~CClass2(void);
};
CClass1 *pstrTemp;
lTemp = lNumOrphanRecord;
pstrTemp = (CClass1*)malloc(sizeof(CClass1));
pstrTemp->structpNextValue = NULL;
CClass2 *pstrExcTemp = &mObject2[0];
while(lTemp > 0)
{
pstrTemp->mDataMember1 = pstrExcTemp->mDataMember1;
strcpy(pstrTemp->mStringData, pstrExcTemp->mStringData);
pstrTemp->mDataMember2 = pstrExcTemp->mDataMember2;
pstrExcTemp = pstrExcTemp->structpNextValue;
if (mObject1->mDataMember1 == 0)
{
mObject1 = pstrTemp;
}
else
{
CClass1 *pstrPrev = NULL;
CClass1 *pstrCurr = mObject1;
long int tempSeqNum = mObject1->mDataMember1;
int Icount=0;
while ( (pstrCurr) &&(pstrCurr->mDataMember1 !=0) &&
(pstrCurr->mDataMember1 < pstrTemp->mDataMember1) )
{
pstrPrev = pstrCurr;
pstrCurr = pstrCurr->structpNextValue;
}
if ((pstrCurr) && (pstrCurr->mDataMember1 == pstrTemp->mDataMember1) )
{
if (pstrCurr->mDataMember2 < pstrTemp->mDataMember2)
{
pstrTemp->structpNextValue = pstrCurr->structpNextValue;
free(pstrCurr);
pstrCurr = pstrTemp;
if (tempSeqNum == pstrTemp->mDataMember1)
{
mObject1 = pstrCurr;
}
if(pstrPrev)
{
pstrPrev->structpNextValue = pstrCurr;
}
}
if(!pstrTemp)
pstrTemp = NULL;
lNumOrphanRecord--;
}
else
{
if (pstrPrev)
{
pstrPrev->structpNextValue = pstrTemp;
pstrTemp->structpNextValue = pstrCurr;
}
else
{
pstrTemp->structpNextValue = pstrCurr;
mObject1 = pstrTemp;
}
}
}
pstrTemp = (CClass1*)malloc(sizeof(CClass1));
pstrTemp->structpNextValue = NULL;
lTemp--;
}
lNumRecord += lNumOrphanRecord;
pstrExcTemp = &mObject2[0];
pstrExcTemp = pstrExcTemp->structpNextValue;
while(mObject2->structpNextValue != NULL)
{
pstrExcTemp = mObject2->structpNextValue;
mObject2->structpNextValue = pstrExcTemp->structpNextValue;
if(!pstrExcTemp)
pstrExcTemp = NULL;
}