C++ Program Code to implement the concept of doubly linked list, utilizing the concept of template class

/* The following C++ Program Code is used to implement the concept of doubly linked list. The program also utilizes the concept of template classes in order to have inter-compatibility for various data types. The user at the starting creates a linked list, & to get the other options he should enter the element as '0'. Then the program gives option to delete, insert, & display the linked list element. */

#include<iostream>
#include<conio.h>
using namespace std;
#define double Double


template<class T>
class node
{
      public:
             T data;
             node *l,*r;
};


template<class T>
class double
{
      private:
              node<T> *first;
      public:
             double()
             {
                     first==NULL;
             }
             void createlist();
             void del();
             void insert();
             void disp();
};


template<class T>
void double<T>::createlist()
{
     int a;
     node<T> *cur,*ptr;
     first=NULL;
     cout<<"\nEnter data for new node : ";
     cin>>a;
     while(a)
     {
             cur=new node<T>;
             cur->data=a;
             cur->l=cur->r=NULL;
             if(first==NULL)
             {
                            first=cur;
             }
             else
             {
                 cur->l=ptr;
                 ptr->r=cur;
             }
             ptr=cur;
             cout<<"\nEnter data of node : ";
             cin>>a;
     }
}


template<class T>
void double<T>::disp()
{
     node<T> *ptr,*last;
     ptr=first;
     last=NULL;
     cout<<"\nThe list is\n";
     while(ptr!=NULL)
     {
                     cout<<ptr->data<<"\t";
                     if(ptr->r==NULL)
                     last=ptr;
                     ptr=ptr->r;
     }
     cout<<"\nThe reverse list is\n";
     ptr=last;
     while(ptr!=NULL)
     {                 
                     cout<<ptr->data<<"\t";
                     ptr=ptr->l;
     }
}


template<class T>
void double<T>::insert()
{
     T ele;
     char ch;
     node<T> *ptr,*cur;
     ptr=first;
     cur=new node<T>;
     cout<<"Enter data for the node:";
     cin>>cur->data;
     cur->r=cur->l=NULL;
     cout<<"Do u want to insert at first place [y/n]:";
     cin>>ch;
     if(ch=='y'||ch=='Y')
     {
                         ptr->l=cur;
                         cur->r=ptr;
                         first=cur;
     }
     else
     {
         cout<<"After which element you want to insert? : ";
         cin>>ele;
         while(ptr!=NULL)
         {
                         if(ptr->data==ele)
                         {
                                           cur->r=ptr->r;
                                           cur->l=ptr;
                                           ptr->r->l=cur;
                                           ptr->r=cur;
                                           break;
                         }
                         else
                         {
                             ptr=ptr->r;
                         }
         }
     }
}


template<class T>
void double<T>::del()
{
     T ele;
     char ch;
     node<T> *ptr;
     ptr=first;
     cout<<"Do you want to delete first element[y/n]? : ";
     cin>>ch;
     if(ch=='y'||ch=='Y')
     {
                         ptr->r->l=NULL;
                         first=ptr->r;
     }
     else
     {
         cout<<"\nEnter the element you want to delete : ";
         cin>>ele;
         while(ptr!=NULL)
         {
                         if(ptr->data==ele)
                         {
                                           ptr->r->l=ptr->l;
                                           ptr->l->r=ptr->r;
                                           break;
                         }
                         else
                         {
                             ptr=ptr->r;
                         }
         }
     }
}


void main()
{
    int ch;
    double<int> d;
    d.createlist();
    do
    {
                   cout<<"\n 1.Insert \n 2.Delete \n 3.Display \n 4.Exit \n";
                   cout<<"Enter choice : ";
                   cin>>ch;
                   switch(ch)
                   {
                             case 1: d.insert();
                             break;
                             case 2: d.del();
                             break;
                             case 3: d.disp();
                             break;
                             case 4:exit(0);
                             break;
                             default: cout<<"\nWrong choice!";
                   }
    }while(ch<=4);
    system("pause");
}

Screenshot:

Read More...

C++ Program Code To Implement Singly Linked List Using Template Class

/* The Following C++ code is tested in MS Visual Studio 2010. The Given code simulates the concept of Singly linked list utilizing the concept of Template Class, First it asks the user to create a list, then after the user enters a '0', it displays other options of the list to process it further */

#include<iostream>

using namespace std;

#include<conio.h>

template<class T>

class node

{

     public:

              T data;

              node<T> *link;

};

template<class T>

class list

{

      private:

              node<T> *first;

      public:

      list();

      ~list();

      void createlist();

      void deletion();

      void insertion();

      void display();
     
      };

template<class T>

list<T>::list()

{

               first=NULL;

}

template<class T>

list<T>::~list()

{

                node<T> *next;

                while(first)

                {

                            next=first->link;

                            delete first;

                            first=next;

                }

}

template<class T>

void list<T>::createlist()

{

                     T a;
                    
                     node<T> *cur,*ptr;

                     cout<<"\nEnter data Of New Node (Enter 0 To Have other options):";

                     cin>>a;

                     while(a)

                     {

                             cur=new node<T>;

                             cur->data=a;

                             cur->link=NULL;

                             if(first==NULL)

                             first=cur;

                             else

                             ptr->link=cur;

                             ptr=cur;

                             cout<<"\nEnter data Of New Node (Enter 0 To Have other options):";

                             cin>>a;

                     }

}

template<class T>

void list<T>::insertion()

{
                node<T> *cur,*ptr;

                 T ele;
                  
                 char ch;
         
                 ptr=first;

                 cur=new node<T>;

                 cout<<"\nEnter data Of New Node:";

                 cin>>cur->data;

                 cur->link=NULL;

                 cout<<"\n Do u wish to insert at the start [y/n]:";

                 cin>>ch;

                 if(ch=='Y'||ch=='y')

                 {

                                     cur->link=first;

                                     first=cur;

                 }

                 else

                 {

                     cout<<"\n Specify after which element do u want to insert :";

                     cin>>ele;

                     while(ptr!=NULL)

                     {

                                     if(ptr->data==ele)

                                     {

                                                      cur->link=ptr->link;

                                                      ptr->link=cur;

                                                      break;

                                     }

                                     else

                                     {

                                         ptr=ptr->link;

                                     }

                     }

                 }

}

template<class T>

void list<T>::deletion()

{

                 T ele;

                 char ch;

                 node<T> *ptr,*ptr1;

                 if(first==NULL)

                 {

                                cout<<"\nSorry list is empty.";

                 }

                 else
                
                 {

                     ptr=first;

                     cout<<"\nDo u want to delete first element? [y/n]:";

                     cin>>ch;

                     if(ch=='y'||ch=='Y')

                     {

                                         first=first->link;

                                         delete ptr;

                     }

                     else

                     {

                         cout<<"\nSpecify which element do u want to delete :";

                         cin>>ele;

                         while(ptr!=NULL)

                         {

                                         if(ptr->link->data==ele)

                                         {

                                                                 ptr1=ptr->link;

                                                                 ptr->link=ptr1->link;

                                                                 delete ptr1;
                                                                
                                                                 return;

                                         }
                                       
                                        else

                                         {

                                             ptr=ptr->link;

                                         }

                         }

                     }

                 }

}

template<class T>

void list<T>::display()

{

     node<T> *ptr;

     if(first==NULL)

     {

                    cout<<"\n Sorry list is empty..";

     }

     else

     {

         ptr=first;

         while(ptr!=NULL)

         {
                        
                         cout<<ptr->data<<"   ";

                         ptr=ptr->link;

         }

     }

}

int main()

{

    int n;

    list <int> l;

    l.createlist();

    do

    {

                   cout<<"\n 1.Insertion \n2.Deletion \n3.Print List \n4.Exit \n";

                   cout<<"\n Enter your option : ";

                   cin>>n;

                   switch(n)

                   {

                            case 1: l.insertion();

                            break;

                            case 2: l.deletion();

                            break;

                            case 3: l.display();

                            break;

                            case 4:
                                 exit(0);

                            break;

                   }

    }while(n<=4);
   
    _getch();

    return 0;

}


Screenshot:

Read More...

C / C++ Program Code To Implement Singly Linked List, With Functions to perform Printing, Create, Insertion, Reversal of the Linked List

/*The Following C / C++ Program used to implement the singly linked list creation & various related operations. The User is given the functions to create, print, print in reversem insert the node element in begineeing, end or anywhere, same with delete operation & function to reverse the linked list. */

#include<stdio.h>
#include<conio.h>
#include<stdlib.h>
 
typedef struct node
   { int data;
     struct node *next;
   }node;

node *create(); //function to create Linked List
node *insert_b(node *head,int x); //Function to insert an element at the beginning
node *insert_e(node *head,int x); //Function to insert an element at the end
node *insert_in(node *head,int x); //Function to insert an element in the middle or anywhere
node *delete_b(node *head); //Function to delete a node from beginning
node *delete_e(node *head); //Function to delete a node from end
node *delete_in(node *head); //Function to delete a node anywhere in between
node *reverse(node *head); //Function to reverse the the Linked list
void printreverse(node *head); //Function to print reverse linked list
void print(node *head); //Function to print the linked list

void main()
{ int op,op1,x;
  node *head=NULL;
 
  do
    {
      printf("\n\n1)Create\n2)Insert Element\n3)Delete Element\n4)Display Reverse List ");
      printf("\n5)Reverce The List\n6)Display The List\n7)Exit");
      printf("\nEnter your Choice:");
      scanf("%d",&op);
      switch(op)
       { 
     case 1:head=create();break;
     case 2:printf("\n\t1)Beginning\n\t2)End\n\t3)In between");
        printf("\nEnter your choice : ");
        scanf("%d",&op1);
        printf("\nEnter the data to be inserted : ");
        scanf("%d",&x);
        switch(op1)
         {  case 1: head=insert_b(head,x);
                break;
            case 2: head=insert_e(head,x);
                break;
            case 3: head=insert_in(head, x);
                break;
          }
        break;
     case 3:printf("\n\t1)Beginning\n\t2)End\n\t3)In between");
        printf("\nEnter your choice : ");
        scanf("%d",&op1);
        switch(op1)
         {  case 1:head=delete_b(head);
               break;
            case 2:head=delete_e(head);
               break;
            case 3:head=delete_in(head);
               break;
          }
         break;
     case 4:printreverse(head);break;
     case 5:head=reverse(head);
        print(head);
        break;
     case 6:print(head);break;
       }
    }while(op!=7);
    system("pause");
}

void printreverse(node *head)
  {
    if(head !=NULL)
       {
      printreverse(head->next);
      printf("%d   ",head->data);
       }
  }


 
node *create()
{ 
node *head,*p;
  int i,n;
  head=NULL;
  printf("\n Enter no of data:");
  scanf("%d",&n);
  printf("\nEnter the data:");
  for(i=0;i<n;i++)
   {
     if(head==NULL)
     p=head=(node*)malloc(sizeof(node));
     else
       {
     p->next=(node*)malloc(sizeof(node));
     p=p->next;
       }
       p->next=NULL;
       scanf("%d",&(p->data));
   }
 return(head);
}

 
node *insert_b(node *head,int x)
{   
node *p;
    p=(node*)malloc(sizeof(node));
    p->data=x;
    p->next=head;
    head=p;
    return(head);
}

 
node *insert_e(node *head,int x)
{   
node *p,*q;
    p=(node*)malloc(sizeof(node));
    p->data=x;
    p->next=NULL;
    if(head==NULL)
       return(p);
    //locate the last node
    for(q=head;q->next!=NULL;q=q->next)
    ;
    q->next=p;
    return(head);
}

 

node *insert_in(node *head,int x)
{   
node *p,*q;
    int y;
    p=(node*)malloc(sizeof(node));
    p->data=x;
    p->next=NULL;
    printf("\Insert after which number ? : ");
    scanf("%d",&y);
    //locate the lthe data 'y'
    for(q=head ; q != NULL && q->data != y ; q=q->next)
    ;
    if(q!=NULL)
      {
    p->next=q->next;
    q->next=p;
      }
    else
       printf("\nData not found ");
    return(head);
}

 
node *delete_b(node *head)
{
  node *p,*q;
  if(head==NULL)
     {
    printf("\nUnderflow....Empty Linked List");
    return(head);
     }
  p=head;
  head=head->next;
  free(p);
  return(head);
}

 
node *delete_e(node *head)
{
  node *p,*q;
  if(head==NULL)
     {
    printf("\nUnderflow....Empty Linked List");
    return(head);
     }
  p=head;
  if(head->next==NULL)
     { 
// Delete the only element
       head=NULL;
       free(p);
       return(head);
     }
   for(q=head;q->next->next !=NULL;q=q->next)
   ;
   p=q->next;
   q->next=NULL;
   free(p);
   return(head);
}
node *delete_in(node *head)
{
  node *p,*q;
  int x,i;
  if(head==NULL)
     {
    printf("\nUnderflow....Empty Linked List");
    return(head);
     }
  printf("\nEnter the data to be deleted : ");
  scanf("%d",&x);
  if(head->data==x)
     {
       p=head;
       head=head->next;
       free(p);
       return(head);
     }
   for(q=head;q->next->data!=x && q->next !=NULL;q=q->next )
   ;
   if(q->next==NULL)
     {
       printf("\nUnderflow.....data not found");
       return(head);
     }
   p=q->next;
   q->next=q->next->next;
   free(p);
   return(head);
}

 
void print(node *head)
{ node *p;
 printf("\n\n");
 for(p=head;p!=NULL;p=p->next)
  printf("%d  ",p->data);
}

 
node *reverse(node *head)
  { 
   node *p,*q,*r;
    p=NULL;
    q=head;
    r=q->next;
    while(q!=NULL)
      {
    q->next=p;
    p=q;
    q=r;
    if(q!=NULL)
       r=q->next;
      }
   return(p);
  }


Screenshot:

Read More...

C program for merge sorting, using linked list: Creating two linked lists & merge them using Merge sort.

#include<stdio.h>                                           //for standard input/output functions
#include<conio.h>                                          //for console input/output functions

struct node
{
int info;
struct node *next;
}*front = NULL,*front1=NULL,*front2=NULL;      //creating 3 node's pointer variable
 //with initial value NULL, as empty list
 
void insert()                                                             //Function to insert the list item,  
{
struct node *t,*q;
int item;
t = (struct node *)malloc(sizeof(struct node));   //To reserve the memory space to node's element
 printf("Input the item value to be added in the queue : ");
scanf("%d",&item);                                            //user inputs the integer data
 t->info = item;
if( front == NULL )                                              //If the list is still empty
 {
front=t;
front->next=NULL;
}
else                                                                         //If the list is not empty 
{
q = front;
while( q->next!= NULL )
q=q->next;
t->next = q->next;
q->next = t;
}
}

void insert1()                      //Function to insert the list item,
{
struct node *t,*q;
int item;
t = (struct node *)malloc(sizeof(struct node)); //To reserve the memory space to node's element
printf("Input the item value to be added in the queue : ");
scanf("%d",&item);                                         //user inputs the integer data
t->info = item;
if( front == NULL )                                           //if the list is empty
 {
front=t;
front->next=NULL;
}
else                                                                     //if the list is not empty 
{
q = front;
while( q->next!= NULL )
q=q->next;
t->next = q->next;
q->next = t;
}
}

void m1_sort(struct node *t)          //for internal use in function m_sort()
 { 
struct node *tt;
tt=front2;
while(tt!=NULL)
tt=tt->next;
tt->next=t;
}

void m_sort()                                   //for sorting the list & merging
 {
struct node *t1,*t,*temp,*tt;
t=front;
t1=front1;
while(t!=NULL||t1!=NULL)         //for traversing the list till the occurrence of NULL element  
{
if((t->info)<(t1->info))
{
temp=(struct node*)malloc(sizeof(struct node));
temp->info=t->info;
temp->next=NULL;
if(front2==NULL)
front2=temp;
else
{
tt=front2;
while(tt!=NULL)
tt=tt->next;
tt->next=temp;
}
}
else
{
temp=(struct node*)malloc(sizeof(struct node));
temp->info=t1->info;
temp->next=NULL;
if(front2==NULL)
front2=temp;
else
{
tt=front2;
while(tt!=NULL)
tt=tt->next;
tt->next=temp;
}
}
t=t->next;
t1=t1->next;
}
if(t1!=NULL)
m1_sort(t1);
else if(t!=NULL)
m1_sort(t);
}


void display()                          //to display the list element 
{
struct node *ptr;
ptr = front2;
if(front == NULL)
printf("Queue is empty\n");
else
{ 
printf("Queue is :\n");
printf("Priority Item\n");
while(ptr != NULL)
{
printf("%5d\n",ptr->info);
ptr = ptr->next;
}
}
}


int main()
{
int ch;
while(ch!=4)
{
printf("1.Insert in 1st queue\n");
printf("2.Insert in 2nd queue\n");
printf("3.Display\n");
printf("4. Sort!!\n");
printf("5.Quit\n");
printf("Enter your choice : ");
scanf("%d", &ch);                       //asking the user choice of the list operation
switch(ch)
{
case 1:
insert();
break;
case 2:
insert1();
break;
case 3:
display();
break;
case 4:
m_sort();
break;
case 5:
exit(1);
default :
printf("Wrong choice\n");
}
}
getche();                                     //for exit the program after a keystroke
return 0;
}

Read More...