Doubly Linked & Circularly List in C

 Doubly Linked List in C

In Single Linked List, each element or node contains a pointer of the next element or node. We know that Single Linked list, only one direction traversing is possible. To overcome this disadvantage we use Doubly Linked List which traverses in both directions. 

In Doubly Linked List, we need to link the List in both directions, each element or node has the pointer of the left element or node and the pointer of the right element or node 

Doubly Linked List

Doubly Linked List is defined as the collection of elements, each element consisting of three fields:

• Pointer to Left element 
• Pointer to Right element
• Data field

link of the first or leftmost element is NULL, this represents that there is no element available to that element left or starting point. same, the link of the last or rightmost element is NULL, this represents that there is no element to that element right.

ALGORITHM to Creation of Doubly Link

Step 1: begin

Step 2: define the structure ELEMENT with fields

        Left Pointer    

        Right Pointer    

        Data

Step 3: declare a pointer by name head and by using malloc() memory function allocation space for one element and store the address in the head pointer

            head=(ELEMENT *)malloc(sizeof(ELEMENT ))

Step 4: read the value for head data head->data

            head->left=NULL

            head->right=(ELEMENT *)malloc(sizeof(ELEMENT ))

Code for creation of Doubly Linked List

* CREATION OF A DOUBLY LINKED LIST */

/* DBLINK.C */

# include < stdio.h >

# include < malloc.h >

   struct dl_list {

      int data;

      struct dl_list * right;

      struct dl_list * left;

   };

typedef struct dl_list dlist;

void dl_create(dlist * );

void traverse(dlist * );

/* Function creates a simple doubly linked list */

void dl_create(dlist * start) {

   printf("\n Input the values of the element -1111 to come out : ");

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

   if (start -> data != -1111) {

      start -> right = (dlist * ) malloc(sizeof(dlist));

      start -> right -> left = start;

      start -> right -> right = NULL;

      dl_create(start -> right);

   } else

      start -> right = NULL;

}

/* Display the list */

void traverse(dlist * start) {

   printf("\n traversing the list using right pointer\n");

   do {

      printf(" %d = ", start -> data);

      start = start -> right;

   } while (start -> right); /* Show value of last start only one time */

   printf("\n traversing the list using left pointer\n");

   start = start -> left;

   do {

      printf(" %d =", start -> data);

      start = start -> left;

   } while (start -> left);

}

void main() {

   dlist * head;

   head = (dlist * ) malloc(sizeof(dlist));

   head -> left = NULL;

   head -> right = NULL;

   dl_create(head);

   printf("\n Created doubly linked list is as follows");

   traverse(head);

}

OUTPUT

Input the values of the element -1111 to come out :

1
Input the values of the element -1111 to come out :
2
Input the values of the element -1111 to come out :
3
Input the values of the element -1111 to come out :
-1111
Created doubly linked list is as follows
traversing the list using right pointer
1 = 2 = 3 =
traversing the list using left pointer
3 = 2 = 1 =

Circularly Linked Lists

 A linked list in which the last element of the list is pointed to the first element of the list. starting and ending point is not available in this linked list.

Creation of Circular linked List

#include<stdio.h>

#include<stdlib.h>
#define NULL 0
 
//define the list 
struct linked_list {
   int data;
   struct linked_list * next;
};
typedef struct linked_list clist;
clist * head, * s;
  
void main() {
    //declaration of function
   void create_clist(clist * );
   int count(clist * );
   void traverse(clist * );
   head = (clist * ) malloc(sizeof(clist));
   //copy the address of first element in s ponter
   s = head;
   //calling create function
   create_clist(head);
   printf(" \n traversing the created clist and the starting address is %u \n",
      head);
   //calling traverse function to print list
   traverse(head);
   printf("\n number of elements in the clist %d \n", count(head));
}
 
//define the create function
void create_clist(clist * start) {
   printf("input the element -1111 for coming out of the loop\n");
   scanf("%d", & start -> data);
   /*at -1111 list will terminat and first element address copy to start-> next of last element */
   if (start -> data == -1111)
      start -> next = s;
   else {
      start -> next = (clist * ) malloc(sizeof(clist));
      create_clist(start -> next);
   }
}
 
//define the traverse function 
void traverse(clist * start) {
   /*If start->next address not = to first element adress then print data and again calling traverse function*/
   if (start -> next != s) {
      printf("data is %d \t next element address is %u\n", start -> data, start -> next);
      traverse(start -> next);
   }
   if (start -> next == s)
      printf("data is %d \t first element address is %u\n", start -> data, start -> next);
}
 
 //define the count function 
int count(clist * start) {
   /*Until start->next is not = to return to countfunction and 1 increament */
   if (start -> next == s)
      return 0;
   else
      return (1 + count(start -> next));
}
OUTPUT

input the element -1111 for coming out of the loop
1
input the element -1111 for coming out of the loop
2
input the element -1111 for coming out of the loop
3
input the element -1111 for coming out of the loop
4
input the element -1111 for coming out of the loop
-1111
 
 traversing the created clist and the starting address is 2971857568 
data is 1        next element address is 2971859680
data is 2        next element address is 2971859712
data is 3        next element address is 2971859744
data is 4        next element address is 2971859776
data is -1111    first element address is 2971857568

number of elements in the clist 4 

ALGORITHM (Insertion of an element into a Circular 

Linked List)

If new element is to be inserted after an existing element , that element traced by call 

the find function. the new element is inserted before the 'key' element

Step 1: Begin

Step 2: if list is empty or new element comes before start (head) element, then insert

            the element as new start element 

Step 3: If the element come after the last element, then insert the new element as last

            element and adjust the pointer of last element to the start element 

Step 4: If insert the new element in the by using find function .find function returns the

            address of the found element to the insert list function.

Step 5: End

Code for insertion of a node into a Circular linked list

#include<stdio.h>
#include<stdlib.h>
#define NULL 0
 
   ........
   ........
 
/* prototype of find and insert functions
here return type is linked list address*/
clist * find(clist * , int);
clist * insert_clist(clist * );
/*definition of insert_clist function */
clist * insert_clist(clist * start) {
   clist * n, * n1;
   int key, x;
   printf("enter value of new element");
   scanf("%d", & x);
   printf("eneter value of key element");
   scanf("%d", & key);
   /*if condition true if new element comes before
   start element, else find function called*/
   if (start -> data == key) {
      n = (clist * ) malloc(sizeof(clist));
      n -> data = x;
      /* cope the address of start element in new
      element next pointer*/
      n -> next = start;
      /* copy the addressof start in n to make
      n element start element*/
      start = n;
   } else {
      n1 = find(start, key);
      if (n1 == NULL)
         printf("\n key is not found\n");
      else {
         n = (clist * ) malloc(sizeof(clist));
         n -> data = x;
         /* copy next element address in new element
         next pointer*/
         n -> next = n1 -> next;
         /* copy the address of new element in element
         trace by find function*/
         n1 -> next = n;
      }
   }
   return (start);
}
 
/*definition of find function */
clist * find(clist * start, int key) {
      /* it find element comes before the element which
      have key value data. If condition ture for next
      element data is key value, otherthan other if condition
      ture for next element data is NULl or end of list, else
      call find function again with next element*/
 
      if (start -> next -> data == key)
         return (start);
      if (start -> next -> next == NULL)
         return (NULL);
      else
         find(start -> next, key);
   }
   ........
   ........
 
void main() {
   void create_clist(clist * );
   int count(clist * );
   void traverse(clist * );
   head = (clist * ) malloc(sizeof(clist));
   s = head;
   create_clist(head);
   printf(" \n traversing the created clist and the starting address is %u \n", head);
   traverse(head);
   printf("\n number of elements in the clist %d \n", count(head));
   head = insert_clist(head);
   printf("\n traversing the clist after insert_clist and starting address is %u\n", head);
   traverse(head);
}

ALGORITHM (Deletion of an element from a Circular Linked List) 

Step 1: Begin 

Step 2: if the list is empty, then element cannot be deleted. 

Step 3: else, if element to be deleted is first node, then make the start (head) to point to the                 second element. 

Step 4: else, delete the element from the list by calling find function and returning the found                address of the element.

 

Step 5: End. 

Code for deletion of a node into a Circular linked list

#include<stdio.h>

#include<stdlib.h>

#define NULL 0

........

........

/* prototype of find and delete_function*/

clist * delete_clist(clist * );

 

/*definition of delete_clist */

clist * delete_clist(clist * start) {

   int key;

   clist * f, * temp;

   printf("\n enter the value of element to be deleted \n");

   scanf("%d", & key);

   /* Step 2 if delete first element*/

   if (start -> data == key) {

      temp = start -> next;

      free(start);

      start = temp;

   } else {

      /*Step 3 delete the from the list*/

      f = find(start, key);

      /* if element key value not found*/

      if (f == NULL)

         printf("\n key not fund");

      else {

         temp = f -> next -> next;

         free(f -> next);

         f -> next = temp;

      }

   }

   return (start);

}

 

........

........

 

void main() {

   void create_clist(clist * );

   int count(clist * );

   void traverse(clist * );

   head = (clist * ) malloc(sizeof(clist));

   s = head;

   create_clist(head);

   printf(" \n traversing the created clist and the starting address is %u \n", head);

   traverse(head);

   printf("\n number of elements in the clist %d \n", count(head));

   head = insert_clist(head);

   printf("\n traversing the clist after insert_clist and starting address is %u\n", head);

   traverse(head);

   printf("\n number of elements in the clist %d \n", count(head));

   head=delete_clist(head);

   printf(" \n traversing the clist after delete_clistand starting address is %u\n",head);

   traverse(head);

  

}

Final Code for Code for creation, insertion and deletion of Doubly Linked List

#include<stdio.h>

#include<stdlib.h>

#define NULL 0

 

struct linked_list {

   int data;

   struct linked_list * next;

};

typedef struct linked_list clist;

clist * head, * s;

 

/* prototype of find and insert functions

here return type is linked list address*/

clist * find(clist * , int);

clist * insert_clist(clist * );

/*definition of insert_clist function */

clist * insert_clist(clist * start) {

   clist * n, * n1;

   int key, x;

   printf("enter value of new element");

   scanf("%d", & x);

   printf("eneter value of key element");

   scanf("%d", & key);

   /*if condition true if new element comes before

   start element, else find function called*/

   if (start -> data == key) {

      n = (clist * ) malloc(sizeof(clist));

      n -> data = x;

      /* cope the address of start element in new

      element next pointer*/

      n -> next = start;

      /* copy the addressof start in n to make

      n element start element*/

      start = n;

   } else {

      n1 = find(start, key);

      if (n1 == NULL)

         printf("\n key is not found\n");

      else {

         n = (clist * ) malloc(sizeof(clist));

         n -> data = x;

         /* copy next element address in new element

         next pointer*/

         n -> next = n1 -> next;

         /* copy the address of new element in element

         trace by find function*/

         n1 -> next = n;

      }

   }

   return (start);

}

 

 

/*definition of find function */

clist * find(clist * start, int key) {

    /* it find element comes before the element which

    have key value data. If condition ture for next

    element data is key value, otherthan other if condition

    ture for next element data is NULl or end of list, else

    call find function again with next element*/

   

   if (start -> next -> data == key)

      return (start);

   if (start -> next -> next == NULL)

      return (NULL);

   else

      find(start -> next, key);

}

 

/* prototype of find and delete_function*/

clist * delete_clist(clist * );

 

/*definition of delete_clist */

clist * delete_clist(clist * start) {

   int key;

   clist * f, * temp;

   printf("\n enter the value of element to be deleted \n");

   scanf("%d", & key);

   /* Step 2 if delete first element*/

   if (start -> data == key) {

      temp = start -> next;

      free(start);

      start = temp;

   } else {

      /*Step 3 delete the from the list*/

      f = find(start, key);

      /* if element key value not found*/

      if (f == NULL)

         printf("\n key not fund");

      else {

         temp = f -> next -> next;

         free(f -> next);

         f -> next = temp;

      }

   }

   return (start);

}

 

void main() {

   void create_clist(clist * );

   int count(clist * );

   void traverse(clist * );

   head = (clist * ) malloc(sizeof(clist));

   s = head;

   create_clist(head);

   printf(" \n traversing the created clist and the starting address is %u \n", head);

   traverse(head);

   printf("\n number of elements in the clist %d \n", count(head));

   head = insert_clist(head);

   printf("\n traversing the clist after insert_clist and starting address is %u\n", head);

   traverse(head);

   printf("\n number of elements in the clist %d \n", count(head));

   head=delete_clist(head);

   printf(" \n traversing the clist after delete_clistand starting address is %u\n",head);

   traverse(head);

  

}

void create_clist(clist * start) {

   printf("inputthe element -1111 for coming oout of the loop\n");

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

   if (start -> data == -1111)

      start -> next = s;

   else {

      start -> next = (clist * ) malloc(sizeof(clist));

      create_clist(start -> next);

   }

}

void traverse(clist * start) {

   if (start -> next != s) {

      printf("data is %d \t next element address is %u\n", start -> data, start -> next);

      traverse(start -> next);

   }

   if (start -> next == s)

      printf("data is %d \t next element address is %u\n", start -> data, start -> next);

}

int count(clist * start) {

   if (start -> next == s)

      return 0;

   else

      return (1 + count(start -> next));

}

 

Full Code Output

inputthe element -1111 for coming oout of the loop

1

inputthe element -1111 for coming oout of the loop

2

inputthe element -1111 for coming oout of the loop

3

inputthe element -1111 for coming oout of the loop

4

inputthe element -1111 for coming oout of the loop

-1111

 

 traversing the created clist and the starting address is 785420960 

data is 1        next element address is 785423072

data is 2        next element address is 785423104

data is 3        next element address is 785423136

data is 4        next element address is 785423168

data is -1111    next element address is 785420960

number of elements in the clist 4 

enter value of new element55

eneter value of key element3

 traversing the clist after insert_clist and starting address is 785420960

data is 1        next element address is 785423072

data is 2        next element address is 785423200

data is 55       next element address is 785423104

data is 3        next element address is 785423136

data is 4        next element address is 785423168

data is -1111    next element address is 785420960

 number of elements in the clist 5 

 enter the value of element to be deleted 

2

 

 traversing the clist after delete_clistand starting address is 785420960

data is 1        next element address is 785423200

data is 55       next element address is 785423104

data is 3        next element address is 785423136

data is 4        next element address is 785423168

data is -1111    next element address is 785420960