Write C program to Delete, insert nodes at Beginning, Middle and at End using functions in Double Linked List

Write C program to Delete, insert nodes at Beginning, Middle and at End using functions in Double Linked List

#include<stdio.h>

 

struct dnode

  {

   struct dnode *Llink;

   int data;

   struct dnode *Rlink;

  };

  struct dnode *L,*R;

  struct dnode *getnode()

  {

    struct dnode *p;

    p=(struct dnode *) malloc(sizeof(struct dnode));

    printf("Enter the data in the Node:");

    scanf("%d",&p->data);

    p->Llink=NULL;

    p->Rlink=NULL;

    return p;

  }

  void creatednodes()

  {

   struct dnode *f,*t,*temp;

   int ct=0;

   char ch='Y';

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

   {

    if(ct==0)

    {

      f=getnode();

      ct++;

    }

    else

    {

     temp=f;

     while(temp->Rlink!=NULL)

     {

      temp=temp->Rlink;

     }

     t=getnode();

     temp->Rlink=t;

     t->Llink=temp;

    }

    printf("do you want to continue: ");

    fflush(stdin);

    ch=getchar();

   }

   L=f;

   R=t;

  }

  int countdnodes(struct dnode *L)

  {

    struct dnode *temp;

    int ct=0;

    temp=L;

    while(temp!=NULL)

    {

      ct++;

      temp=temp->Rlink;

    }

    return ct;

  }

  void displaynodesLtoR(struct dnode *L)

  {

    struct dnode *temp;

    temp=L;

    printf("NULL<-->");

    while(temp!=NULL)

    {

      printf("%d<-->",temp->data);

      temp=temp->Rlink;

    }

    printf("NULL\n");

  }

  void displaynodesRtoL(struct dnode *R)

  {

   struct dnode *temp;

   temp=R;

   printf("NULL<-->");

   while(temp!=NULL)

   {

    printf("%d<-->",temp->data);

    temp=temp->Llink;

   }

   printf("NULL\n");

  }

  struct dnode *insertfirstdnode(struct dnode *L)

   {

    struct dnode *t;

    t=getnode();

    t->Rlink=L;

    L->Llink=t;

    L=t;

   return L;

  }

  struct dnode *insertlastdnode(struct dnode *R)

  {

   struct dnode *t;

   t=getnode();

   R->Rlink=t;

   t->Llink=R;

   R=t;

   return R;

  }

  struct dnode *insertmiddlednode(struct dnode *L,int pos)

  {

    struct dnode *temp,*t;

    int i;

    temp=L;

    for(i=1;i<pos-1;i++)

    {

      temp=temp->Rlink;

    }

    t=getnode();

    t->Llink=temp;

    t->Rlink=temp->Rlink;

    temp->Rlink->Llink=t;

    temp->Rlink=t;

    return L;

   }

   void Insertdnodes(int pos)

   {

     struct dnode *t,*temp;

     int ct,i;

     ct=countdnodes(L);

     if(pos==1)

     {

       t=getnode();

       t->Rlink=L;

       L->Llink=t;

       L=t;

     }

     else if(pos>ct)

     {

      t=getnode();

      R->Rlink=t;

      t->Llink=R;

      R=t;

     }

     else

      {

       temp=L;

       for(i=1;i<pos-1;i++)

       {

            temp=temp->Rlink;

       }

       t=getnode();

       t->Llink=temp;

       t->Rlink=temp->Rlink;

       temp->Rlink->Llink=t;

       temp->Rlink=t;

      }

    }

    void deletednodes(int pos)

    {

      struct dnode *t,*t1,*t2;

      int ct,i;

      ct=countdnodes(L);

      if(pos==1)

      {

       t=L;

       L=L->Rlink;

       t->Rlink=NULL;

       L->Llink=NULL;

       free(t);

      }

      else if(pos==ct)

      {

       t=R;

       R=t->Llink;

       R->Rlink=NULL;

       t->Llink=NULL;

       free(t);

      }

      else

      {

       t=L;

       for(i=1;i<pos;i++)

       {

             t=t->Rlink;

       }

       t->Llink->Rlink=t->Rlink;

       t->Rlink->Llink=t->Llink;

       free(t);

      }

    }

  void main()

  {

    int ct;

    clrscr();

    creatednodes();

    printf("display nodes left to right\n");

    displaynodesLtoR(L);

    printf("display nodes right to left\n");

    displaynodesRtoL(R);

    ct=countdnodes(L);

    printf("number of nodes=%d\n",ct);

   /* Insertdnodes(3);

    displaynodesLtoR(L);

    displaynodesRtoL(R);*/

    deletednodes(2);

    displaynodesLtoR(L);

    displaynodesRtoL(R);

  /*  L=insertfirstdnode(L);

    displaynodesLtoR(L);

    displaynodesRtoL(R);

    R=insertlastdnode(R);

    displaynodesLtoR(L);

    displaynodesRtoL(R);

    L=insertmiddlednode(L,3);

    displaynodesLtoR(L);

    displaynodesRtoL(R);*/

    getch();

  }

Double Linked List

Double Linked List

            A Double Linked List is represented as follows

The main disadvantages of single linked list is that traversal is possible only in one direction i.e., forward direction.  If we are pointing to a node, say ‘P’, then we can move only in one direction of link.  Suppose, if we want to find the predecessor of ‘P’, then we have to start from the beginning of the linked list.  Thus given the address of a node, we can only find the address of successor, and it is not possible to find the address of predecessor directly.  To overcome this we use double Linked List.

            In order to facilitate  faster processing of data, it is require to traverse the list in both direction.  Such a list is called Double Linked List.  Here each node contain 3-fields, two of which are link fields and one is data field.  Thus a typically node is as follows:

  

LLink

Data

RLink

            

      RLink, links in the forward direction and LLink, links in backward direction i.e., RLink contains the address of successor node and LLink contains address of predecessor node.  Double Linked List is also called as Two Way Chain.  Address of the leftmost node is L and address of rightmost node R.  if we traverse in forward direction R is the last node.  Hence Rà RLink=Null.  Similarly, if it traverse in backward direction L is the last node.  Hence  LàLLink=Null.

            Suppose, if X is the address of a node then XàLLink represent the address of the predecessor and Xà RLink represent the address of successor.  Declaration of Double Linked List  in C is as follows:

struct node

{

   Struct node *LLink;

   int data;

   struct node *RLink;

};

Write C program to Insert & Delete nodes at Beginning, Middle and at End using functions in Circular Linked List

Write C program to Insert & Delete nodes at Beginning, Middle and at End using functions in Circular Linked List

  #include <stdio.h>

  struct node

  {

   int data;

   struct node*link;

  };

  struct node * getnode()

  {

    struct node *p;

    p=(struct node *)malloc(sizeof(struct node));

    printf("enter data into the node:");

    scanf("%d",&p->data);

    p->link=NULL;

    return p;

  }

  int  countnodes(struct node *f)

   {

    struct node *temp;

    int ct=0;

    temp=f;

    while(temp->link!=f)

    {

      ct++;

      temp=temp->link;

    }

    ct++;

    return ct;

  }

  struct node * createnodes()

  {

    struct node *first,*t,*temp;

    char ch='Y';

    int ct=0;

    while(ch=='Y')

    {

      if(ct==0)

      {

       first=getnode();

       ct++;

       temp=first;

       first->link=first;

      }

      else

      {

       temp=first;

       while(temp->link!=first)

       {

            temp=temp->link;

       }

       t=getnode();

       temp->link=t;

       t->link=first;

      }

      printf("do you want to continue:");

      fflush(stdin);

      ch=getchar();

     }

     return first;

   }

   void displaylist (struct node *f)

   {

     struct node *temp;

     temp=f;

     while(temp->link!=f)

     {

      printf("%d-->",temp->data);

      temp=temp->link;

     }

     printf("%d-->\n",temp->data);

  }

  /*  struct node * insertnodes(struct node *f,int pos)

    {

     struct node *t,*t1,*n;

     int ct,i;

     ct=countnodes(f);

     if(pos==1)

     {

            t=getnode();

            t->link=f;

            t1=f;

            while(t1->link!=f)

            {

              t1=t1->link;

            }

            t1->link=t;

            f=t;

     }

     else if(pos>ct)

     {

      t=f;

      for(i=1;i<ct;i++)

      {

       t=t->link;

      }

      n=getnode();

      t->link=n;

      n->link=f;

     }

     else

     {

      t=f;

      t1=f;

      for(i=1;i<pos;i++)

      {

       t=t->link;

      }

      for(i=1;i<pos-1;i++)

      {

       t1=t1->link;

      }

      n=getnode();

      n->link=t;

      t1->link=n;

     }

     return f;

   } */

   struct node * deletefirstnode(struct node *f)

   {

     struct node *temp,*t;

     temp=f;

     t=f;

     while(temp->link!=f)

     {

      temp=temp->link;

     }

     f=f->link;

     temp->link=f;

     free(t);

     return f;

   }

   struct node *deletelastnode(struct node *f)

   {

     struct node *temp,*t;

     temp=f;

     t=f;

     while(temp->link!=f)

     {

      temp=temp->link;

     }

     while(t->link!=temp)

     {

      t=t->link;

     }

     t->link=temp;

     free(temp);

     return f;

    }

   struct node *deletemiddlenode(struct node *f,int pos)

    {

     struct node *temp,*t;

     int i;

     temp=f;

     t=f;

     for(i=1;i<pos;i++)

     {

      temp=temp->link;

     }

     for(i=1;i<pos-1;i++)

     {

       t=t->link;

     }

     t->link=temp->link;

     free(temp);

     return f;

    }

   void main()

   {

     int ct,n;

     struct node *first;

     clrscr();

     first=createnodes();

     displaylist(first);

     ct=countnodes(first);

     printf("number of nodes=%d\n",ct);

    /* printf("Enter the node position to be inserted\n");

     scanf("%d",&n);

     first=insertnodes(first,n);

     displaylist(first);*/

     first=deletefirstnode(first);

     displaylist(first);

     first=deletelastnode(first);

     displaylist(first);

     getch();

  }

Circular Linked List

Circular Linked List

A linked list where the link field of last node contains address of first node is called a circular linked list .It is represented as follows.

Circular linked list have certain advantageous over single linked list.

1.  Traversing is simple.

           In a single linked list, it is not possible to traverse the entire linked list starting from any node. In other words, if we start from first node only, we can visit all nodes. Starting from the middle node we cannot visit all nodes. However in circular linked list one can traverse the entire linked list starting from any node.

2.      Deletion requires less number of inputs in circular linked list over  single

linked list.

            In single linked list if we wish to delete a node, we require the address of that node and also we require the address of first node. This is because the predecessor of the node to be deleted had to be kept track off. However, in circular linked list, if we want to delete a node we require the address of that node. However, we do not require the address of first node. Since the initialization of the temp pointer which has to point to the predecessor node is made at deleted node itself  i.e. In single linked list if we require two address, one X, which is the address of node deleted, second is first, this is required because temp is initialized to first and moved it tempàlink=X.

            Where as in circular linked list we require only one address of X i.e. X, which is the address of node to be deleted. Here temp is initialized to X itself and moved till tempàlink=X.

           

            However there is a disadvantageous in circular linked list. If one is not careful while processing a circular linked list, then we can end up in an infinite loop. In circular linked list it is not possible to distinguish last node from other nodes since its link field also contain address .To over come  this we use a special node called head node at beginning of the linked list .The head node link field points to first node and first link field of last node contain address of head node. The data field of head node is unused. The circular linked list with head node is as follows:

Write C program to Delete nodes at Beginning, Middle and at End using functions in Single Linked List

Write C program to Delete nodes at Beginning, Middle and at End using functions

  #include <stdio.h>

  struct node

  {

   int data;

   struct node*link;

  };

  struct node * getnode()

  {

    struct node *p;

    p=(struct node *)malloc(sizeof(struct node));

    printf("enter data into the node:");

    scanf("%d",&p->data);

    p->link=NULL;

    return p;

  }

  int  countnodes(struct node *f)

   {

    struct node *temp;

    int ct=0;

    temp=f;

    while(temp!=NULL)

    {

      ct++;

      temp=temp->link;

    }

    return ct;

  }

  struct node * createnodes()

  {

    struct node *first,*t,*temp;

    char ch='Y';

    int ct=0;

    while(ch=='Y')

    {

      if(ct==0)

      {

       first=getnode();

       ct++;

       temp=first;

      }

      else

      {

       temp=first;

       while(temp->link!=NULL)

       {

            temp=temp->link;

       }

       t=getnode();

       temp->link=t;

       temp=t;

      }

      printf("do you want to continue:");

      fflush(stdin);

      ch=getchar();

     }

     return first;

   }

   void displaylist (struct node *f)

   {

     struct node *temp;

     temp=f;

     while(temp!=NULL)

     {

      printf("%d-->",temp->data);

      temp=temp->link;

     }

     printf("NULL\n");

  }

/* struct node * deletefirstnode(struct node *first)

  {

     struct node *temp;

     temp=first;

     first=temp->link;

     free(temp);

   return first;

  }

  struct node * deletelastnode(struct node *first)

   {

    struct node *temp,*temp1;

    temp=first;

    temp1=first;

    while(temp->link!=NULL)

    {

     temp=temp->link;

    }

    while(temp1->link!=temp)

    {

     temp1=temp1->link;

    }

     temp1->link=NULL;

     free(temp);

     return first;

   }

   struct node *deletemiddlenode(struct node *first, int pos)

   {

     struct node *temp,*temp1;

     int i;

     temp=first;

     temp1=first;

     for(i=1;i<pos;i++)

     {

      temp=temp->link;

     }

     for(i=1;i<pos-1;i++)

     {

      temp1=temp1->link;

     }

     temp1->link=temp->link;

     free(temp);

     return first;

    }    */

    struct node * deletenodes(struct node *f,int pos)

    {

     struct node *t,*t1;

     int ct,i;

     ct=countnodes(f);

     t=f;

     t1=f;

     if(ct<pos)

     {

      printf("please cheak number of nodes & position to deleted\n");

     }

     else if(pos==1)

     {

      f=f->link;

      free(t);

     }

     else if(pos==ct)

     {

      for(i=1;i<pos;i++)

      {

       t=t->link;

      }

      for(i=1;i<pos-1;i++)

      {

       t1=t1->link;

      }

      t1->link=NULL;

      free(t);

     }

     else

     {

      for(i=1;i<pos;i++)

      {

       t=t->link;

      }

      for(i=1;i<pos-1;i++)

      {

       t1=t1->link;

      }

      t1->link=t->link;

      free(t);

     }

     return f;

   }

   void main()

   {

     int ct,n;

     struct node *first;

     clrscr();

     first=createnodes();

     displaylist(first);

     ct=countnodes(first);

     printf("number of nodes=%d\n",ct);

    /* first=deletefirstnode(first);

     displaylist(first);

     first=deletelastnode(first);

     displaylist(first);

     first=deletemiddlenode(first,4);*/

     printf("enter which node to be deleted\n");

     scanf("%d",&n);

     first=deletenodes(first,n);

     displaylist(first);

     getch();

  }