SINGLY LINKED LIST

SINGLY LINKED LIST (C++ CODE):

Last Updated on: 12th Dec 2015

 //performing differnt operations on sll

#include<iostream.h>
#include<stdio.h>
#include<conio.h>
class sll
{
 private:
  struct snode
  {
   int data;
   struct snode *next;
  }*start;
 public:
  sll()
  {
   start=NULL;
  }
  void create();
  void display();
  void insert_beg();
  void insert_end();
  void insert_mid();
  void delete_beg();
  void delete_end();
  void delete_mid();
  void search();
  void reverse();
  void addition();
  void concate(sll);
  void sort();
  void merge(sll);

};
void sll:: create()
{
  snode *new_node,*current;
 char ch;
 do
 {
  new_node=new snode;
  cout<<"\nenter the data:";
  cin>>new_node->data;
  new_node->next=NULL;
  if(start==NULL)
  {
   start=new_node;
   current=new_node;
  }
  else
  {
   current->next=new_node;
   current=current->next;
  }
  cout<<"\ndo u want  to add more nodes?";
  cin>>ch;
 }while(ch=='y'||ch=='Y');
}
void sll::display()
{
 snode *temp;
 if(start==NULL)
 {
  cout<<"\nList is empty";
 }
 else
 {
  temp=start;
  cout<<" list is:";
  while(temp!=NULL)
  {
   cout<<"\t"<<temp->data;
   temp=temp->next;
  }
 }
}
void sll::insert_beg()
{
 snode *node;
 node=new snode;
 cout<<"\nenter the data:";
 cin>>node->data;
 if(start==NULL)
 {
  start=node;
  node->next=NULL;
 }
 else
 {
  node->next=start;
  start=node;
 }
}
void sll::insert_end()
{
 snode *temp,*node;
 node=new snode;
 cout<<"\nenter the data:";
 cin>>node->data;
 temp=start;
 while(temp->next!=NULL)
 {
  temp=temp->next;
 }
 temp->next=node;
 node->next=NULL;
}
void sll::insert_mid()
{
 snode *temp,*node;
 int count=1,pos;
 node=new snode;
 cout<<"\nenter the data:";
 cin>>node->data;
 cout<<"\nenter the position:";
 cin>>pos;
 temp=start;
 while(count<pos-1)
 {
  temp=temp->next;
  count++;
 }
 node->next=temp->next;
 temp->next=node;
}
void sll::delete_beg()
{
 snode *temp;
 if(start==NULL)
 {
  cout<<"\n Cannot delete....";
 }
 else
 {
  temp=start;
  start=temp->next;
  cout<<temp->data<<"\thas been deleted\n";
  delete temp;
 }
}
void sll::delete_end()
{
 snode *temp1,*temp2;
 if(start==NULL)
 {
  cout<<"\n Cannot delete....";
 }
 else
 {
  temp1=start;
  temp2=start;
  while(temp1->next!=NULL)
  {
   temp1=temp1->next;
  }
  while(temp2->next!=temp1)
  {
   temp2=temp2->next;
  }
  temp2->next=NULL;
  cout<<temp1->data<<"\thas been deleted\n";
  delete temp1;
 }
}
void sll::delete_mid()
{
 snode *temp1,*temp2;
 int count=1,pos;
 if(start==NULL)
 {
  cout<<"\nCannot delete....";
 }
 else
 {
  cout<<"\nenter the position:";
  cin>>pos;
  temp1=start;
  temp2=start;
  while(count<=pos-1)
  {
   temp1=temp1->next;
   count++;
  }
  while(temp2->next!=temp1)
  {
   temp2=temp2->next;
  }
  temp2->next=temp1->next;
  cout<<temp1->data<<"\thas been deleted\n";
  delete temp1;
 }
}
void sll::search()
{
 snode *temp;
 int key,pos,count=1;
 if(start==NULL)
 {
  cout<<"\nList is empty.....";
 }
 else
 {
  temp=start;
  cout<<"\nenter the data u want to search:";
  cin>>key;
  while(temp->next!=NULL)
  {
   if(key==temp->data)
   {
    pos=count;
    cout<<"Data"<<key<<"found at position:"<<pos;
   }
   temp=temp->next;
   count++;
  }
 }
}
void sll::reverse()
{
 snode *back,*current,*temp;
 back=NULL;
 current=start;
 temp=start->next;
 while(current!=NULL)
 {
  current->next=back;
  back=current;
  current=temp;
  if(temp!=NULL)
  {
   temp=temp->next;
  }
 }
 start=back;
}
void sll::addition()
{
 snode *temp;
 int sum=0;
 if(start==NULL)
 {
  cout<<"\nWe cannot add as list is empty....";
 }
 else
 {
  temp=start;
  while(temp!=NULL)
  {
   sum=sum+temp->data;
   temp=temp->next;
  }
  cout<<"\nAddition="<<sum;
 }
}
void sll::concate(sll b)
{
 snode *temp;
 if(start==NULL)
 {
  create();
  display();
 }
 b.create();
 b.display();
 temp=start;
 while(temp->next!=NULL)
 {
  temp=temp->next;
 }
 temp->next=b.start;
}
void sll::sort()
{
 snode *temp1,*temp2;
 int temp;
 temp1=start;
 while(temp1!=NULL)
 {
  temp2=start;
  while(temp2->next!=NULL)
  {
   if(temp2->data>temp2->next->data)
   {
    temp=temp2->data;
    temp2->data=temp2->next->data;
    temp2->next->data=temp;
   }
   temp2=temp2->next;
  }
  temp1=temp1->next;
 }
}
void sll::merge(sll b)
{
 snode *temp1,*temp2,*temp3,*current;
 if(start==NULL)
 {
  create();
  display();
 }
 b.create();
 b.display();
 temp1=start;
 temp2=b.start;
 temp3=NULL;
 current=temp3;
 while(temp1!=NULL&&temp2!=NULL)
 {
  if(temp1->data>temp2->data)
  {
   temp3=temp2;
   temp2=temp2->next;
  }
  else if(temp1->data<temp2->data)
  {
   temp3=temp1;
   temp1=temp1->next;
  }
  else
  {
   temp3=temp1;
   temp1=temp1->next;
   temp2=temp2->next;
  }
  if(start==NULL)
  {
   current=temp3;
   start=temp3;
  }
  else
  {
   current->next=temp3;
   current=current->next;
  }
  if(temp1!=NULL)
  {
   current->next=temp1;
  }
  if(temp2!=NULL)
  {
   current->next=temp2;
  }
 }
}





void main()
{
 sll a,b,c;
 int ch;
 char choice;
 clrscr();
 do
 {
  cout<<"\nMENU....";
  cout<<"\n1.create";
  cout<<"\n2.display";
  cout<<"\n3.insert";
                cout<<"\na.at beg";
  cout<<"\n4.insert at end";
  cout<<"\n5.insert at middle";
  cout<<"\n6.delete at start";
  cout<<"\n7.delete at end";
  cout<<"\n8.delete at middle";
  cout<<"\n9.searching";
  cout<<"\n10.reverse";
  cout<<"\n11.Addition";
  cout<<"\n12.concatenation";
  cout<<"\n13.sort";
  cout<<"\n14.merge";
  cout<<"\nenter the choice:";
  cin>>ch;
  switch(ch)

  {
   case 1:
    a.create();
    a.display();
    break;
   case 2:
    a.display();
    break;
   case 3:
    a.insert_beg();
    a.display();
    break;
   case 4:
    a.insert_end();
    a.display();
    break;
   case 5:
    a.insert_mid();
    a.display();
    break;
   case 6:
    a.delete_beg();
    a.display();
    break;
   case 7:
    a.delete_end();
    a.display();
    break;
   case 8:
    a.delete_mid();
    a.display();
    break;
   case 9:
    a.search();
    break;
   case 10:
    a.reverse();
    a.display();
    break;
   case 11:
    a.addition();
    break;
   case 12:
    a.concate(b);
    a.display();
    break;
   case 13:
    a.sort();
    a.display();
    break;
   case 14:
    
    a.merge(b);
    a.display();
    break;
  }
  cout<<"\ndo u want to continue:";
  cin>>choice;
 }while(choice=='y'||choice=='Y');
 getch();

}

Hope you liked the Singly Linked List code. Please Let us know your feedback or any other questions. Cheers!!

DOUBLY LINKED LIST

DOUBLY_LINKED LIST (C++ CODE):

//To perform various operations on DLL

#include<iostream.h>
#include<conio.h>
class dll
{
 private:
 typedef struct node
 {
  int data;
  node *next;
  node *prev;
 };

 node *head;
 public:
 void create();
 void disp();
 int count();
 void search();
 void insert_front();
 void insert_end();
 void insert_mid();
 void sort();
 void con(dll b);
 void delfront();
 void delend();
 void delmid(int pos);

};

void dll::create()
{
  int n;
  node *p,*q;
  head=NULL;
  cout<<"\nenter number of nodes:";
  cin>>n;
  for(int i=0;i<n;i++)
  {
    cout<<"\nenter data:";
    p=new node;
    cin>>p->data;
    p->next=NULL;
    p->prev=NULL;
    if(head==NULL)
      head=p;
    else
    {
     q=head;
     while(q->next!=NULL)
  q=q->next;
     q->next=p;
     p->prev=q;
    }
  }
}

void dll::disp()
{
  node *p;
  p=head;
  cout<<"\nlist is:";
  while(p!=NULL)
  {
    cout<<"\t"<<p->data;
    p=p->next;
  }
}

int dll:: count()
{
  node *p;
  int cnt=0;
  p=head;
  while(p!=NULL)
  {
    cnt++;
    p=p->next;
  }
  return(cnt);
}

void dll::search()
{
 node *p;
 int num,cnt=0;
 p=head;
 cout<<"enter the number to be searched:";
 cin >>num;
 while(p!=NULL)
 {
  cnt++;
  if(p->data==num)
  cout<<"number is at pos:"<<cnt;
  p=p->next;
 }
}

void dll::insert_front()
{
  node *p;
  p=new node;
  cout<<"\n enter data:";
  cin>>p->data;
  p->next=head;
  p->prev=NULL;
  head=p;
}

void dll::insert_end()
{
 node *p,*q;
 p=new node;
 cout<<"\n enter data:";
 cin>>p->data;
 p->next=NULL;
 q=head;
 while(p->next!=NULL)
 q=q->next;
 q->next=p;
 p->prev=q;
}

void dll::insert_mid()
{
  int loc;
  node *p,*q;
  cout<<"\n enter location:";
  cin>>loc;
  q=head;
  for(int i=1;i<=loc;i++)
  {
   q=q->next;
  }
  if(q==NULL)
  {
   cout<<"less than"<<loc<<"nodes";
   return;
  }
  p=new node;
  cout<<"\n enter data:";
  cin>>p->data;
  q->next=p;
  p->next=q->next;
  p->prev=q;
}

void dll::sort()
{
  node *p,*q;
  int num;
  for(p=head;p!=NULL;p=p->next)
  {
   for( q=p->next;q!=NULL;q=q->next)
   {
    if(p->data>q->data)
    {
     num=p->data;
     p->data=q->data;
     q->data=num;
    }
   }
  }
}

void dll::con(dll b)
{
  node *p;
  p=head;
  while(p->next!=NULL)
  p=p->next;
  p->next=b.head;
  disp();

}

void dll::delfront()
{
  node *p;
  p=head;
  head=head->next;
  head->prev=NULL;
  p->next=NULL;
  delete(p);
}

void dll::delend()
{
  node *p;
  p=head;
  while(p->next!=NULL)
  p=p->next;
  p->prev->next=NULL;
  delete(p);
}

void dll::delmid(int pos)
{
 node *p,*q;
 p=head;
 for(int i=1;i<pos;i++)


  p=p->next;

 if(p==NULL)
 {
  cout<<"less than"<<pos<<"nodes";
  return;
 }
 else
 {
  p->next->prev=p->prev;
  p->prev->next=p->next;
  delete(p);
 }
}


void main()
{
 int op,cnt,op1,op2,pos;
  char ch;
  clrscr();
  dll l1,a,b;
 do
 {
  cout<<"\n\n***menu***";
  cout<<"\n1.create\n2.display\n3.count\n4.search\n5.insert\n6.sort\n 7.concatenate\n 8.delete";
  cout<<"\nenter ur choice:";
  cin>>op;
  switch(op)
  {
   case 1:
   l1.create();
   break;
   case 2:
   l1.disp();
   break;
   case 3:
   cnt=l1.count();
   cout<<"\nnumber of nodes: "<<cnt;
   break;
   case 4:
   l1.search();
   break;
   case 5:
   cout<<"\n 1.insert at front\n2.insert at end\n3.insert at mid";
   cout<<"\n enter your choice:";
   cin>>op1;
   switch(op1)
   {
    case 1:
    l1.insert_front();
    break;
    case 2:
    l1.insert_end();
    break;
    case 3:
    l1.insert_mid();
    break;
   }
    break;
    case 6:
    l1.sort();
    cout<<"\n sorted list is:";
    l1.disp();
    break;
    case 7:
    a.create();
    b.create();
    a.con(b);
    break;
    case 8:
    cout<<"\n1.front\n2.end\n3.mid";
    cout<<"\n enter your choice:";
    cin>>op2;
    switch(op2)
    {
     case 1:
     l1.delfront();
     break;
     case 2:
     l1.delend();
     break;
     case 3:
     cout<<"\n enter the pos to be deleted:";
     cin>>pos;
     l1.delmid(pos);
     break;
    }
    break;
   }
  cout<<"\ndo u want to continue?:";
  cin>>ch;
 }while(ch=='y'||ch=='Y');

}

CIRCULARLY LINKED LIST

CIRCULARLY LINKED LIST (C++ CODE):

/*performing different operations on cll*/


#include<iostream.h>
#include<conio.h>
class cll
{
struct cnode
{
int data;
struct cnode *next;
}*last;
public:
cll()
{
last=NULL;
}
void create();
void display();
void insert_beg();
void insert_end();
void insert_mid();
void delete_beg();
void delete_end();
void delete_mid();
int length();

void search();
void concate(cll);
void sort();
void merge(cll);

};
void cll:: create()
{
cnode *new_node,*current;
char ch;
do
{
new_node=new cnode;
cout<<"\nenter the data:";
cin>>new_node->data;
new_node->next=new_node;
if(last==NULL)
{
last=new_node;
current=new_node;
}
else
{
new_node->next=current->next;
current->next=new_node;
last=new_node;
current=current->next;
}
cout<<"\ndo u want  to add more nodes?";
cin>>ch;
}while(ch=='y'||ch=='Y');
}
void cll::display()
{
cnode *temp;
if(last==NULL)
{
cout<<"\nList is empty";
}
else
{
temp=last->next;
cout<<" list is:";
while(temp!=last)
{
cout<<"\t"<<temp->data;
temp=temp->next;
}
cout<<"\t"<<last->data;
}
}
void cll::insert_beg()
{
cnode *node,*temp;
node=new cnode;
cout<<"\nenter the data:";
cin>>node->data;
if(last==NULL)
{
last=node;
last->next=last;
}
else
{
temp=last->next;
node->next=temp;
last->next=node;
}
}
void cll::insert_end()
{
cnode *temp,*node;
node=new cnode;
cout<<"\nenter the data:";
cin>>node->data;
temp=last;
node->next=temp->next;
temp->next=node;
last=node;
}
void cll::insert_mid()
{
cnode *temp,*node;
int count=1,pos;
node=new cnode;
cout<<"\nenter the data:";
cin>>node->data;
cout<<"\nenter the position:";
cin>>pos;
temp=last->next;
while(count<pos-1)
{
temp=temp->next;
count++;
}
node->next=temp->next;
temp->next=node;
}
void cll::delete_beg()
{
cnode *temp;
if(last==NULL)
{
cout<<"\n Cannot delete....";
}
else
{
temp=last->next;
last->next=temp->next;
cout<<"\n"<<temp->data<<"has been deleted from list\n";
delete temp;
}
}
void cll::delete_end()
{
cnode *temp1,*temp2;
int len;
if(last==NULL)
{
cout<<"\n Cannot delete....";
return;
}
else
{
  len=length();
if(len==1)
{
delete last;
last=NULL;
}
else
{
temp1=last;
temp2=last->next;
while(temp2->next!=temp1)
{
temp2=temp2->next;
}
temp2->next=last->next;
last=temp2;
cout<<"\n"<<temp1->data<<"has been deleted from list\n";
delete temp1;
}
}
}
int cll::length()
{
cnode *temp;
int count=1;
if(last==NULL)
{
cout<<"\nList is empty";
}
else
{
temp=last->next;
while(temp!=last)
{
temp=temp->next;
count++;
}
}
return count;
}

void cll::delete_mid()
{
cnode *temp1,*temp2;
int count=1,pos;
if(last==NULL)
{
cout<<"\nCannot delete....";
}
else
{
cout<<"\nenter the position:";
cin>>pos;
temp1=last->next;
temp2=last->next;
while(count<=pos-1)
{
temp1=temp1->next;
count++;
}
while(temp2->next!=temp1)
{
temp2=temp2->next;
}
temp2->next=temp1->next;
cout<<"\n"<<temp1->data<<"has been deleted from list\n";
delete temp1;
}
}
void cll::search()
{
cnode *temp;
int key,pos=1,flag=0;
if(last==NULL)
{
cout<<"\nList is empty.....";
}
else
{
temp=last->next;
cout<<"\nenter the data u want to search:";
cin>>key;
while(temp!=last)
{
if(key==temp->data)
{
flag=1;
}
pos++;
temp=temp->next;

}
}
if(flag==1||last->data==key)
{
cout<<"\nkey "<<key<<"found at position "<<pos;
}
else
cout<<"\nkey not found";

}
void cll::concate(cll b)
{
cnode *temp1,*temp2;
if(last==NULL)
{
cout<<"\nenter the first list:";
create();
display();
}
cout<<"\nenter the second list:";
b.create();
b.display();
temp1=last->next;
temp2=b.last->next;
last->next=temp2;
b.last->next=temp1;
last=b.last;

}
void cll::sort()
{
cnode *temp1,*temp2,*temp3;
int temp,count=1,len;
temp1=last->next;
temp3=last->next;
len=length();
while(count<=len)
{
temp2=last->next;
while(temp2->next!=temp3)
{
if(temp2->data>temp2->next->data)
{
temp=temp2->data;
temp2->data=temp2->next->data;
temp2->next->data=temp;
}
temp2=temp2->next;
}
temp1=temp1->next;
count++;
}
}

void main()
{
cll a,b,c;
int ch,len;
char choice;
clrscr();
do
{
cout<<"\nMENU....";
cout<<"\n1.create";
cout<<"\n2.display";
cout<<"\n3.insert at beg";
cout<<"\n4.insert at end";
cout<<"\n5.insert at middle";
cout<<"\n6.delete at start";
cout<<"\n7.delete at end";
cout<<"\n8.delete at middle";
cout<<"\n9.searching";
cout<<"\n10.length";
cout<<"\n11.concatenation";
cout<<"\n12.sort";

cout<<"\nenter the choice:";
cin>>ch;
switch(ch)

{
case 1:
a.create();
a.display();
break;
case 2:
a.display();
break;
case 3:
a.insert_beg();
a.display();
break;
case 4:
a.insert_end();
a.display();
break;
case 5:
a.insert_mid();
a.display();
break;
case 6:
a.delete_beg();
a.display();
break;
case 7:
a.delete_end();
a.display();
break;
case 8:
a.delete_mid();
a.display();
break;
case 9:
a.search();
break;
case 10:
      len=a.length();
cout<<"\nNo. of nodes="<<len;
break;
case 11:
a.concate(b);
a.display();
break;
case 12:
a.sort();
a.display();
break;
}
cout<<"\ndo u want to continue:";
cin>>choice;
}while(choice=='y'||choice=='Y');
getch();
}

DLL MERGE

DLL MERGE (C++ CODE):



#include<iostream.h>
#include<conio.h>
#include<stdio.h>
class dll
{
private:
struct dnode
{
int data;
struct dnode *next,*prev;
}*start;
public:
dll()
{
start=NULL;
}
void create();
void display();
void sort();
void merge(dll,dll);
};
void dll::create()
{
dnode *new_node,*current;
char ch;
do
{
new_node=new dnode;
cout<<"\nenter the data:";
cin>>new_node->data;
new_node->next=NULL;
new_node->prev=NULL;
if(start==NULL)
{
start=new_node;
current=new_node;
}
else
{
current->next=new_node;
new_node->prev=current;
current=current->next;
}
cout<<"\ndo u want  to add more nodes?";
cin>>ch;
}while(ch=='y'||ch=='Y');
}
void dll::display()
{
dnode *temp;
if(start==NULL)
{
cout<<"\nList is empty";
}
else
{
temp=start;
cout<<"\n list is:";
while(temp!=NULL)
{
cout<<"\t"<<temp->data;
temp=temp->next;
}
}
}
void dll::sort()
{
dnode *temp1,*temp2;
int temp;
if(start==NULL)
{
cout<<"\nCannot sort,....";
}
else
{
temp1=start;
while(temp1!=NULL)
{
temp2=start;
while(temp2->next!=NULL)
{
if(temp2->data>temp2->next->data)
{
temp=temp2->data;
temp2->data=temp2->next->data;
temp2->next->data=temp;
}
temp2=temp2->next;
}
temp1=temp1->next;
}
}
}
void dll::merge(dll a,dll b)
{
dnode *temp1,*temp2,*temp3,*current;
temp1=a.start;
temp2=b.start;
while(temp1!=NULL&&temp2!=NULL)
{
if(temp1->data>temp2->data)
{
temp3=temp2;
temp2=temp2->next;
}
else if(temp1->data<temp2->data)
{
temp3=temp1;
temp1=temp1->next;
}
else
{
temp3=temp1;
temp1=temp1->next;
temp2=temp2->next;
}
if(start==NULL)
{
current=temp3;
start=temp3;
}
else
{
current->next=temp3;
temp3->prev=current;
current=current->next;
}
 }
if(temp1!=NULL)
{
current->next=temp1;
temp1->prev=current;
}
if(temp2!=NULL)
{
current->next=temp2;
temp2->prev=current;
}

}

void main()
{
dll a,b,c;
clrscr();
cout<<"\nenter the first list:";
a.create();
a.sort();
a.display();
cout<<"\nenter the second list:";
b.create();
b.sort();
b.display();
c.merge(a,b);
cout<<"\nList after merge is:";
c.display();
getch();

}