Tuesday, 14 March 2017

Program-implementation of doubly linked list using c

#include <stdio.h>

#include <string.h>
#include <stdlib.h>
#include <stdint.h>
struct node {
   int info;
   int index;
   struct node *flink;
   struct node *plink;
}node;
//this link always point to first Link
struct node *head = NULL;
//this link always point to tail Link
struct node *tail = NULL;
struct node *ptr = NULL;
//is list empty
int isEmpty() {
   return head == NULL;
}
int count() {
   int count = 0;
   struct node *ptr=head;
   while(ptr!=NULL)
   {   count++;
    ptr=ptr->flink;
   }
   return count;
}
//display the list in from first to tail
void trav_forward() {
   //start from the beginning
   struct node *ptr = head;
   //navigate till the end of the list
     while(ptr != NULL) {      
      printf("(%d,%d) ",ptr->index,ptr->info);
      ptr = ptr->flink;
   }
}
//display the list from tail to first
void trav_backward() {
   //start from the tail
   struct node *ptr = tail;
   //navigate till the start of the list
     while(ptr!= NULL) {    
      //print info
      printf("(%d,%d) ",ptr->index,ptr->info);
      //move to flink item
      ptr = ptr ->plink;
      printf(" ");
   }
}
//insert link at the first location
void insertFirst(int index, int data) {
   //create a link
   struct node *link = (struct node*) malloc(sizeof(struct node));
   link->index = index;
   link->info = data;
   if(isEmpty()) {
      //make it the tail link
      tail = link;
      tail->flink=NULL;
 tail->plink=NULL;
   } else {
      //update first plink link
      head->plink = link;
   }
   //point it to old first link
   link->flink = head;
   //point first to new first link
   head = link;
   head->plink=NULL;
}
//insert link at the tail location
void inserttail(int index, int data) {
   //create a link
   struct node *link = (struct node*) malloc(sizeof(struct node));
   link->index = index;
   link->info = data;
   if(isEmpty()) {
      //make it the tail link
      tail = link;
       tail->flink=tail->plink=NULL;
   } else {
      //make link a new tail link
      tail->flink = link;          
      //mark old tail node as plink of new link
      link->plink = tail;
   }
   //point tail to new tail node
   tail = link;
   tail->flink=NULL;
}
//delete first item
void  deleteFirst() {
   //save reference to first link
   struct node *tempLink = head;
   //if only one link
   if(head->flink == NULL){
      tail = NULL;
   } else
   {
      head->flink->plink = NULL;
      head=head->flink;
   }
}
//delete link at the tail location
void deleteLast() {
   //save reference to tail link
   //if only one link
   if(head->flink == NULL) {
      head = NULL;
   } else {
      tail->plink->flink = NULL;
   }
   tail = tail->plink;
   tail->flink=NULL;
   //return the deleted link
   //return tempLink;
}
//delete a link with given index
void delete1(int index) {
   //start from the first link
   struct node* ptr = head;
   struct node* prevloc = NULL;
   //if list is empty
   if(head == NULL) {
      printf("\n opreration cannot be performed ");
   }
   //navigate through list
   while(ptr->index != index) {
      //if it is tail node
      if(ptr->flink == NULL) {
         printf("\n opreration cannot be performed ");
      } else {
         //store reference to ptr link
         prevloc = ptr;
         //move to flink link
         ptr = ptr->flink;            
      }
   }
   //found a match, update the link
   if(ptr == head) {
      //change first to point to flink link
      head = head->flink;
      head->plink=NULL;
   } else {
      //bypass the ptr link
      ptr->plink->flink = ptr->flink;
   }  
   if(ptr == tail) {
      //change tail to point to plink link
      tail = ptr->plink;
   } else {
      ptr->flink->plink = ptr->plink;
   }
   //return ptr;
}
int insertAfter(int index, int newindex, int info) {
   //start from the first link
   struct node *ptr = head;
   //if list is empty
   if(head == NULL) {
      return 0;
   }
   //navigate through list
   while(ptr->index != index) {
      //if it is tail node
      if(ptr->flink == NULL) {
         return 0;
      } else {          
         //move to flink link
         ptr = ptr->flink;
      }
   }
   //create a link
   struct node *newLink = (struct node*) malloc(sizeof(struct node));
   newLink->index = newindex;
   newLink->info = info;
   if(ptr == tail) {
      newLink->flink = NULL;
      tail = newLink;
      newLink->flink=NULL;
   } else {
      newLink->flink = ptr->flink;        
      ptr->flink->plink = newLink;
   }
   newLink->plink = ptr;
   ptr->flink = newLink;
   while(ptr!=NULL)
   {
    ptr->index++;
    ptr=ptr->plink;
   }
   
   return 1;
}

main()
{   int loc,value;
   insertFirst(1,10);
   insertFirst(2,20);
   insertFirst(3,30);
   insertFirst(4,1);
   insertFirst(5,40);
   insertFirst(6,56);
   printf("\nList (First to last): ");
   trav_forward();
   printf("\n");
   printf("\nList (last to first): ");
   trav_backward();
   printf("\nList , after deleting first record: ");
   deleteFirst();      
   trav_forward();
   printf("\nList , after deleting tail record: ");
   deleteLast();
   trav_forward();
   printf("\nList , insert after index : ");
   scanf("%d",&loc);
   printf("\n enter the value for new node : ");
   scanf("%d",&value);
   insertAfter(loc,loc,value);
   trav_forward();
   printf("\nList  , after delete index(4) : ");
   delete1(4);
   trav_forward();
}

No comments:

Post a Comment