Implementation of Linked List in C

A linked list is a linear data structure. It is defines as the collection of objects called nodes that are randomly stored in memory. These nodes are connected together via links.

 

A node contains two fields:

• Data part: This part of the node holds the value/element.
• Link part: This part of the node holds the address of the next node.

The last node of the linked list contains pointer to the null/end of list.

In this article, we have designed and implemented Linked List in C Programming Language. We have created a Node structure in C and implemented all Linked List operations in C.

 

Structure of a node

As we know that a node contains data part and link part. So we will create a structure using struct keyword.

struct node {     int data;     struct node*next; }; struct node *start, *p; p=(struct node*)malloc(sizeof(struct node));

 

Here, we've created a structure of a node.

int data is the data part of the node which will hold the data.

struct node * next is the pointer variable of node datatype.

struct node * start defines start as a variable which can store the address of the node.

p is a pointer variable which is used to create memory block in RAM.

 

Advantages of linked list

• Linked list is a dynamic data structure so it can grow or shrink during runtime by allocating and de-allocating memory.
• As the memory is allocated or de-allocated during runtime so there is no memory wastage.
• The operations like insertion, deletion of nodes are easy as compared to that of array.
• Data structures such as stack, queue can be implemented easily.

Disadvantages of linked list

• Traversal is difficult in linked list. If we want to access any node randomly, then we have to traverse all the nodes before it.
• It uses more memory because each node contains a pointer and it requires extra memory for itself.

Types of linked list

There are three types of linked list:

1. Singly Linked list
2. Doubly linked list
3. Circular Linked list

 

Singly linked list

Singly Linked list is also known as one way list list in which we can traverse only in forward/one direction because a node in singly linked list contains a data part and a link part.

The data part of the node holds the value/element and link part of the node holds the address of its immediate successor.

 

Operations on Singly linked list

1. Insertion:

The insertion operation in linked list is used to insert the new node. The insertion of node in singly linked list can be performed at different positions.

a) Insertion of node in the beginning:

In this a new node is inserted in the front of already existing linked list. For this we have to follow some steps:

First we will create a new node and store the data into the data part.

Now we will point the link part of the new node with the first node(start) of existing linked list

After that we will make new node as the first node (start)

p=(struct node *) malloc(sizeof(struct node));  p→data=value; p->next=start; start=p;     //new node 'p' will become the first node of the list

 

b) Insertion of node at the end:

The insertion of node at the end of singly linked list can have two cases:

First case when there is not even a single node in the list(list is empty). In this case the condition (start==NULL) will be satisfied.

Since, 'p' is the only node that will be inserted in the list so we need to make this node point to the 'start' pointer.

p->data=value;    p->next=NULL;   start=p;

 

Second case when we have to add a node at the end of already existing linked list. In this we will use a loop to traverse to the end of list. So, we need to declare a temporary variable temp in order to traverse through the list.

At the end of the loop, the temp will be point to the last node of the list. The next part of the temp node will point to the new node 'p'. The next part of node 'p' will point to the null.

temp=start; while(temp→next!=NULL)  //traverse through the list     temp=temp→next;     temp=start;  while(temp->next!=NULL)        temp=temp->next;  temp->next=p;       //next of temp will point to 'p' p->next=NULL;       //next of 'p' will point to null

 

C) Inserting a node at any specified location:

In this operation, we will skip some nodes until we reach the specified location. Once we reach the location, we will insert the node there. Here, we will use a for loop to reach the location where we want to insert our new node.

for(i=0;i<loc;i++)  //loc represents the location where we want to insert the node {      temp=temp->next;      if(temp==NULL)         return; }

 

Create a new node 'p store the data in the data part.

The next part of the new node p must contain the address part of the next part of the temp

Last step would be to make the next part of the temp point to the new node p.

p=(struct node*)malloc(sizeof(struct node)); p->data=value; p->next=temp->next; temp->next=p;

 

2. Deletion:

The deletion operation in linked list is used to delete the node. Just like insertion, the deletion operation on linked list can be performed at different positions.

a) Deletion of node in the beginning:

Deletion of a node in the beginning is a simple operation. Here, we will first copy the address of the first node 'start' to some temporary variable say 'p'.

Move the first node 'start' to the second node of the linked list i.e.start =start->next.

Now, free the pointer p.

The free() function is used to de-allocate the memory.

p=start;  start=start->next; free(p);

 

b) Deletion of node at the end of linked list:

There can be two cases while implementing deletion operation at the end of a singly linked list.

 

First case: if there is only one node in the list,then the condition (start==NULL) will be satisfied and the start node will be assigned to null.

p=start;    start=NULL;    free(p);    //'p' will be deleted

 

Second case: Here we have to traverse the list until we reach the end node of the list. The temp pointer is assigned to start pointer of the list and it will traverse the list till it reaches to the last node.

p=start;     while(p->next!=NULL)    {    p1=p;    //'p1' keeps track of second last node.   p=p->next;    }   p1->next=NULL;    free(p);

 

c) Deletion of node at any specified position:

When we performed insertion operation of node at specified location, we skipped the nodes until we reached the desired location. Similarly, in the deletion operation of node at specified location we will skip some nodes until we reach the specified location.

Here, we need to keep track of two nodes. One which is to be deleted 'p' and the other which is just before that node 'p1'.

p=start;  for(i=0;i<loc;i++)  {      p1=p;           p=p->next;  if(p==NULL)  //when the location entered is more than the size of linked list {      printf("\nlocation does not exist");      return;  }  }

 

Now,we just have to make some pointer adjustments. The next of p1 will point to the next of p.

p1->next=p->next; free(p);   //'p' will be deleted

 

3. Traversing

Traversing operation is the most commonly performed operation in singly linked list. Traversing means visiting each node of the linked list at least once in order to perform some operation. Example: printing the elements in the linked list.

 

So these were some operations that we can perform on singly linked list.

p=start;   while (p!=NULL)       p=p->next;

 

A complete program of different types of operations on singly linked list

#include<stdio.h>  #include<stdlib.h>  struct node   {      int data;      struct node *next;   };  struct node *start;                 /*fuction declaration of all the operations*/ void insert_begin();   void insert_last();  void insert_locc();  void delete_begin();  void delete_last();  void delete_locc();  void print();  void main ()  {      int ch=0;      while(ch!=8)       {            printf("\nEnter the operation to be performed\n");            printf("\n1.Insert in the begining\n2.Insert at last\n3.Insert at any specified position\n4.Delete from Beginning\n5.Delete from last\n6.Delete node after specified location\n7.Show\n8.Exit\n");                   scanf("\n%d",&ch);          switch(ch)          {        /*function calls of all the operations */             case 1:              insert_begin();                   break;              case 2:              insert_last();                     break;              case 3:              insert_locc();                   break;              case 4:              delete_begin();                   break;              case 5:              delete_last();                    break;              case 6:              delete_locc();                       break;              case 7:              print();                    break;              case 8:              exit(0);              break;              default:              printf("Enter valid option");          }      }  }           /*function definition*/ void insert_begin()                  //to insert the node at the beginnning of linked list {      struct node *p;       int value;      p=(struct node *) malloc(sizeof(struct node *));      if(p==NULL)      {          printf("\nOVERFLOW");      }      else      {          printf("\nEnter value\n");            scanf("%d",&value);            p->data=value;          p->next=start;          start=p;      }  }  void insert_last()                //to insert the node at the last of linked list {      struct node *p,*temp;      int value;         p=(struct node*)malloc(sizeof(struct node));          if(p==NULL)      {          printf("\nOVERFLOW");         }      else      {          printf("\nEnter value\n");          scanf("%d",&value);          p->data=value;          if(start==NULL)          {              p->next=NULL;              start=p;          }          else          {              temp=start;              while(temp->next!=NULL)              {                  temp=temp->next;              }              temp->next=p;              p->next=NULL;          }      }  }  void insert_locc()               //to insert the node at the specified location of linked list {      int i,loc,value;       struct node *p, *temp;      p=(struct node *)malloc(sizeof(struct node));      if(p==NULL)      {          printf("\nOVERFLOW");      }      else      {          printf("\nEnter element value");          scanf("%d",&value);          p->data=value;          printf("\nEnter the location after which you want to insert ");          scanf("\n%d",&loc);          temp=start;          for(i=0;i<loc;i++)          {              temp=temp->next;              if(temp==NULL)              {                  printf("\ncan't insert\n");                  return;              }          }          p->next=temp->next;           temp->next=p;     }  }  void delete_begin()          //to delete the node present in the beginning of the linked list {      struct node *p;      if(start==NULL)      {          printf("\nList is empty\n");      }      else       {          p=start;          start=p->next;          free(p);      }  }  void delete_last()          //to delete the node present in the last of the linked list {      struct node *p,*p1;      if(start==NULL)      {          printf("\nlist is empty");      }      else if(start->next==NULL)      {          start=NULL;          free(start);          printf("\nOnly node of the list deleted ...\n");      }      else      {          p=start;           while(p->next!=NULL)          {              p1=p;              p=p->next;          }          p1->next=NULL;          free(p);      }     }  void delete_locc()    //to delete the node present at the specified of the linked list {      struct node *p,*p1;      int loc,i;        printf("\n Enter the location of the node after which you want to perform deletion \n");      scanf("%d",&loc);      p=start;      for(i=0;i<loc;i++)      {          p1=p;               p=p->next;                     if(p==NULL)          {              printf("\nCan't delete");              return;          }      }      p1->next=p->next;      free(p);      printf("\nDeleted node %d ",loc+1);  }  void print()    //to print the values in the linked list {      struct node *p;      p=start;       if(p==NULL)      {          printf("Nothing to print");      }      else      {          printf("\nprinting values\n");           while (p!=NULL)          {              printf("\n%d",p->data);              p=p->next;          }      }  }

OUTPUT:

Enter the operation to be performed   1.Insert in begining 2.Insert at last 3.Insert at any specified position 4.Delete from Beginning 5.Delete from last 6.Delete node after specified location 7.Show 8.Exit 1   Enter value 89   Enter the operation to be performed   1.Insert in begining 2.Insert at last 3.Insert at any specified position 4.Delete from Beginning 5.Delete from last 6.Delete node after specified location 7.Show 8.Exit 1   Enter value 44   Enter the operation to be performed   1.Insert in begining 2.Insert at last 3.Insert at any specified position 4.Delete from Beginning 5.Delete from last 6.Delete node after specified location 7.Show 8.Exit 1   Enter value 78   Enter the operation to be performed   1.Insert in begining 2.Insert at last 3.Insert at any specified position 4.Delete from Beginning 5.Delete from last 6.Delete node after specified location 7.Show 8.Exit 2   Enter value 80   Enter the operation to be performed   1.Insert in begining 2.Insert at last 3.Insert at any specified position 4.Delete from Beginning 5.Delete from last 6.Delete node after specified location 7.Show 8.Exit 7   printing values   78 44 89 80 Enter the operation to be performed   1.Insert in begining 2.Insert at last 3.Insert at any specified position 4.Delete from Beginning 5.Delete from last 6.Delete node after specified location 7.Show 8.Exit 5   Enter the operation to be performed   1.Insert in begining 2.Insert at last 3.Insert at any specified position 4.Delete from Beginning 5.Delete from last 6.Delete node after specified location 7.Show 8.Exit 7   printing values   78 44 89 Enter the operation to be performed   1.Insert in begining 2.Insert at last 3.Insert at any specified position 4.Delete from Beginning 5.Delete from last 6.Delete node after specified location 7.Show 8.Exit

 

Doubly linked List

Doubly linked list is also a sequence of nodes in which a single node contains three fields. In doubly linked list there are two link fields and one data field.

The first link is the pointer to the previous node of the doubly linked list and the second link is the pointer to the next node of the doubly linked list.

 

Structure of a node in doubly linked list

struct node   {      struct node *prev;   //pointer to the previous node     int data;            //holds the data     struct node *next;   //pointer to the next node }

 

Operations on a doubly linked list

1. Insertion:

The insertion operation in linked list is used to insert the new node. The insertion of node in doubly linked list can be performed at different positions.I doubly linked list we have two pointers to maintain as compared to singly linked list

a) Insertion of node in the beginning:

There are two cases while inserting a new node in the beginning of the doubly linked list. Either the list is empty or there is at least one node in the linked list.

 

First we will create a new node

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

 

In the next step we will check we will work on the first case(when the list is empty). The list is empty if the condition (start==NULL) is accepted.In this case the node will be inserted as the only node.So,the 'prev' and the 'next' pointer of the node will point to 'NULL' and the 'start' pointer will point to node 'P'.

p->next=NULL;   //prevoius and next pointer will point to NULL p->prev=NULL;  p->data=value;     start=p;           //'start' will point to the new node/inserted node 'p'

 

In the second case the condition (start==NULL) will not be satisfied.It means there is at least one node in the linked list. The 'next' pointer of the node 'p' will point to the 'start' pointer. The 'prev' pointer of the node 'start' will point to the new node 'p'.

p->next=start;  //the next pointer of the 'p' will point to the 'start' pointer start→prev=p;     //the previous pointer of the 'start' will point to the new node/inserted node 'p' p→prev=NULL;  start=p;

 

b) Insertion of node in the end:

There are two cases while inserting a node at the last of the doubly linked list. Either the list is empty or there is at least one node in the linked list.

 

First we will create a new node

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

 

First case(when the list is empty). The list is empty if the condition (start==NULL) is accepted.In this case the node will be inserted as the only node and therefore the 'prev' and the 'next' pointer of the node 'p' will point to NULL and the 'start' pointer will point to node 'p'.

p->next=NULL;   //next pointer pointing to NULL p->prev=NULL;   //prev pointer pointing to NULL p->data=value;     start=p;        //start will point to the new node/inserted node 'p'

In the second case the condition (start==NULL) will be false. It means there is at least one node in the linked list. Now, we will take a temporary variable which will traverse the list by using pointer.

temp=head;            while(temp!=NULL)      temp=temp→next;     temp->next=ptr;      //pointer of temp will point to the new node ptr->prev=temp;      //previous pointer of new node(ptr) points to the last node(temp) ptr->next=NULL;      //next pointer of new node(ptr) points to the NULL as it will be the last node of the list.

 

c) Insertion of node at any specified location of doubly linked list:

In this operation, we will skip some nodes until we reach the specified location. Once we reach the location, we will insert the node there. Here, we will use a for loop to reach the location where we want to insert our new node.

First we will create a new node

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

 

In this, we will also use a temporary pointer variable to traverse the list until we reach the specified location.

The 'temp' pointer will point to the specified node at the end of the loop.

temp=start;      for(i=0;i<loc;i++)    //will iterate until it reaches to specified location    {         temp=temp->next;         if(temp==NULL)            return;    }  p→next=temp→next;  //the next pointer of 'p' point to the next node of temp  p→prev=temp;       //the prev of the new node 'p' point to temp  temp→next=p;       //the next pointer of temp point to the new node 'p'  temp→next→prev=p;  //the previous pointer of the next node of temp point to the new node'p'

 

2. Deletion:

The deletion operation in linked list is used to delete the node. Just like insertion, the deletion operation on doubly linked list can be performed at different positions.

a) Deletion of node in the beginning of doubly linked list:

Deletion of node at the beginning of doubly linked list can be done in few steps. First we will copy or store the 'start' pointer to pointer 'p' and shift the 'start' pointer to its next.

start=p;            //'p' is stored in 'start' start=start->next;  //shift 'start' pointer to its next start->prev=NULL;   //previous pointer of 'start' point to NULL free(p);            //delete/free the pointer 'p' by using free() function

 

b) Deletion of node at the end of the doubly linked list:

There can be a possibility that the list is empty and no operation can be performed on it. So the condition (start==NULL) will be satisfied and no deletion operation is performed.

And if the list is not empty then we will traverse through the list till we reach the end of doubly linked list.

p=start;   if(p->next!=NULL)     p=p->next; p→prev→next=NULL;  //next of previous of p will point to NULL free(p);           //delete/free the pointer p by using free() function

 

c) Deletion of node at the specified location of the doubly linked list:

In order to delete the node at any specified location in doubly linked list, first we will copy the start pointer to the temp pointer and then traverse the list until we get the specified/desired location.

temp=start; while(temp->data!=val)  temp=temp->next;

 

After this we will check whether the node which is to be deleted is the last node of the list, if it so then we have to make the next pointer of this node point to null so that it can be the new last node of the list.

If that is not satisfied then make the pointer 'p' point to the node which is to be deleted. Make the next of temp point to the next of node 'p'. Make the previous of next node of 'p' point to temp. free the node 'p'.

if(temp->next==NULL)       return;  //can't perform deletion if(temp->next->next==NULL)      temp->next=NULL;     p=temp->next;          temp->next=p->next;  //next of temp will point to the next of 'p'         p->next->prev=temp;  //previous of next of node 'p' will point to temp.         free(p);             //delete/free the pointer 'p' by using free() function

 

3. Traversing

Traversing operation is the most commonly performed operation in doubly linked list. Traversing means visiting each node of the linked list at least once in order to perform some operation. Example: printing the elements in the linked list.

We will use a while loop for printing or traversing the list.

while(p!=NULL)  {  printf("%d\n",p->data);  pr=p->next;  }

 

A complete program of different types of operations on doubly linked list

#include<stdio.h>  #include<stdlib.h>  struct node  {      struct node *prev;      struct node *next;      int data;  };  struct node *start;  /*fuction declaration of all the operations*/ void insert_begin();   void insert_last();  void insert_locc();  void delete_begin();  void delete_last();  void delete_locc();  void print();  void main ()  {  int ch=0;      while(ch!=8)      {          printf("\nEnter the operation to be performed\n");          printf("\n1.Insert in the begining\n2.Insert at last\n3.Insert at any specified position\n4.Delete from Beginning\n5.Delete from last\n6.Delete node after specified location\n7.Print\n8.Exit\n");          scanf("\n%d",&ch);          switch(ch)          {                   /*function calls of all the operations */             case 1:              insert_begin();                   break;              case 2:              insert_last();                     break;              case 3:              insert_locc();                   break;              case 4:              delete_begin();                   break;              case 5:              delete_last();                    break;              case 6:              delete_locc();                       break;              case 7:              print();                    break;              case 8:              exit(0);              break;              default:              printf("Enter valid option");         }       }  }  /*function deefinition*/ void insert_begin()      //to insert the node in the beginning {     struct node *p;      int value;     p=(struct node *)malloc(sizeof(struct node));     if(p==NULL)     {         printf("\nOVERFLOW");     }     else     {      printf("\nEnter value: ");      scanf("%d",&value);           if(start==NULL)     {         p->next=NULL;         p->prev=NULL;         p->data=value;         start=p;     }     else      {         p->data=value;         p->prev=NULL;         p->next=start;         start->prev=p;         start=p;     }  }  }  void insert_last()            //to insert the node at the last of the list  {     struct node *p,*temp;     int value;     p=(struct node *)malloc(sizeof(struct node));     if(p==NULL)     {         printf("\nOVERFLOW");     }     else     {         printf("\nEnter value: ");         scanf("%d",&value);          p->data=value;         if(start==NULL)         {             p->next=NULL;             p->prev=NULL;             start=p;         }         else         {            temp=start;            while(temp->next!=NULL)            {                temp=temp->next;            }            temp->next=p;            p->prev=temp;            p->next=NULL;            }        }      }  void insert_locc()      //to insert the node at the specified location of the list {     struct node *p,*temp;     int value,loc,i;     p=(struct node *)malloc(sizeof(struct node));     if(p==NULL)     {         printf("\n OVERFLOW");     }     else     {         temp=start;         printf("Enter the location");         scanf("%d",&loc);         for(i=0;i<loc;i++)         {             temp=temp->next;             if(temp==NULL)             {                 printf("\n There are less than %d elements", loc);                 return;             }         }         printf("Enter value: ");         scanf("%d",&value);         p->data=value;         p->next=temp->next;         p->prev=temp;         temp->next=p;         temp->next->prev=p;      }  }  void delete_begin()      //to delete the node present in the beginning of the list {      struct node *p;      if(start==NULL)      {          printf("\n UNDERFLOW");      }      else if(start->next==NULL)      {          start=NULL;           free(start);       }      else      {          p=start;          start=start->next;          start->prev=NULL;          free(p);       }  }  void delete_last()    //to delete the node present in the last of the list {      struct node *p;      if(start==NULL)      {          printf("\n UNDERFLOW");      }      else if(start->next==NULL)      {          start=NULL;           free(start);       }      else       {          p=start;           if(p->next!=NULL)          {              p=p->next;           }          p->prev->next=NULL;           free(p);      }  }  void delete_locc()    //to delete the node present at the specified of the list {      struct node *p, *temp;      int val;      printf("\n Enter the data after which the node is to be deleted : ");      scanf("%d", &val);      p=start;      while(p->data!=val)      p=p->next;      if(p->next==NULL)      {          printf("\nCan't delete\n");      }      else if(p->next->next==NULL)      {          p->next=NULL;      }      else      {           temp=p->next;          p->next=temp->next;          temp->next->prev=p;          free(temp);       }     }  void print()  //to print the values in the list {      struct node *p;      printf("\nvalues are:\n");      p=start;      while(p!=NULL)      {          printf("%d\n",p->data);          p=p->next;      }  }

OUTPUT:

Enter the operation to be performed   1.Insert in the begining 2.Insert at last 3.Insert at any specified position 4.Delete from Beginning 5.Delete from last 6.Delete node after specified location 7.Print 8.Exit 1   Enter value: 89   Enter the operation to be performed   1.Insert in the begining 2.Insert at last 3.Insert at any specified position 4.Delete from Beginning 5.Delete from last 6.Delete node after specified location 7.Print 8.Exit 1   Enter value: 65   Enter the operation to be performed   1.Insert in the begining 2.Insert at last 3.Insert at any specified position 4.Delete from Beginning 5.Delete from last 6.Delete node after specified location 7.Print 8.Exit 1   Enter value: 78   Enter the operation to be performed   1.Insert in the begining 2.Insert at last 3.Insert at any specified position 4.Delete from Beginning 5.Delete from last 6.Delete node after specified location 7.Print 8.Exit 2   Enter value: 84   Enter the operation to be performed   1.Insert in the begining 2.Insert at last 3.Insert at any specified position 4.Delete from Beginning 5.Delete from last 6.Delete node after specified location 7.Print 8.Exit 7   values are: 78 65 89 84   Enter the operation to be performed   1.Insert in the begining 2.Insert at last 3.Insert at any specified position 4.Delete from Beginning 5.Delete from last 6.Delete node after specified location 7.Print 8.Exit 5   Enter the operation to be performed   1.Insert in the begining 2.Insert at last 3.Insert at any specified position 4.Delete from Beginning 5.Delete from last 6.Delete node after specified location 7.Print 8.Exit 7   values are: 78   Enter the operation to be performed   1.Insert in the begining 2.Insert at last 3.Insert at any specified position 4.Delete from Beginning 5.Delete from last 6.Delete node after specified location 7.Print 8.Exit 8

 

Circular linked list

A circular linked list is a linked list in which the last node of the list points to the 'start' node of the list making a data structure look like a circle.

 

Types of circular linked list

1. Circular singly linked list
2. Circular doubly linked list

 

Circular singly linked list

Circular singly linked list is similar to that of singly linked list as it has a node which consists of two fields, data and link field but there is only one difference that is in circular singly linked list the last node of the list points to the first node of the list making a data structure look like a circle.

Operations on Circular singly linked list

1. Insertion:

The insertion operation in linked list is used to insert the new node. The insertion of node in singly linked list can be performed at different positions.

 

a) Insertion at the beginning:

While inserting a new node there can be two possibilities. Either the list is empty or there's at least one node in the list.

First we will allocate memory for the new node.

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

 

If the condition (start==NULL) is satisfied it means the list is empty. So this node will point to itself only.The 'start' pointer will also point to the inserted node.

If the condition (start==NULL) is false which means that the list contains at least one node. In this case, we need to traverse the list in order to reach the last node of the list.

if(start==NULL)  {      start=p;      p->next=start;  } temp=start;  while(temp->next!=start)  temp=temp->next; temp->next=p;   p->next=start;   //the next pointer of 'temp' will point to the existing 'start' node of the list start=p;         //make the new node 'p', the new  node of the circular singly linked list

 

At the end of the loop, the pointer temp would point to the last node of the list. Since, in a circular singly linked list, the last node of the list contains a pointer to the first node of the list. Therefore, we need to make the next pointer of the last node point to the 'start' node of the list and the new node which is being inserted into the list will be the new 'start' node of the list therefore the next pointer of temp will point to the new node 'p'.

b) Insertion at the end:

There can be two cases while inserting a new node at the end of the circular singly linked list. Either the list is empty or there is at least one node in the existing list.

 

Allocate memory to the new node.

In the first case, the condition (start==NULL) is satisfied. Since we are working on circular singly linked list then we have to make the pointer of the new node to point to itself.

struct node *p=(struct node *)malloc(sizeof(struct node)); if(start==NULL)  {  start=p;  p->next=start; }

 

In the second case, there is at least one node in the list.In this, we have to traverse the list in order to reach the last node.

When the last node is reached, the pointer temp would point to the last node of the list. Since, the new node which is being inserted into the list will be the new last node of the list. Therefore the existing last node i.e. 'temp' must point to the new node 'p'.

The new last node of the list i.e. 'p' will point to the 'start' node of the list.

temp=start;  while(temp->next!start)  temp=temp->next; temp->next=p; p->next=start;

 

2. Deletion:

In circular singly linked list deletion operation can be performed in many ways.

 

a) Deletion in the beginning

There can be three cases while deleting a node at the beginning of a circular singly linked list.

 

Case 1: when the list is empty. So the condition (start=NULL) will be satisfied and underflow will be printed.

if(start==NULL)  {  printf("\nUNDERFLOW");    return;   }

 

 

Case 2: list contains single node. Here,the condition (start->next==start) will be satisfied. In this case, we have only one node so we will delete it(start pointer) and make the 'start' pointer free.

if(start->next==start)  {  start=NULL;  free(start);  }

 

case 3: list contains more than one node. In that case, we need to traverse the list by using the pointer 'p' to reach the last node of the list.At the end of the loop, the pointer 'p' point to the last node of the list. Since, the last node of the list points to the 'start' node of the list.

p=start;   while(p->next!=start)  p=p->next; p->next=start->next; free(start);

 

b) Deletion at the end

There can be three cases while deleting a node at the end of a circular singly linked list.

 

case 1: when the list is empty. So the condition (start==NULL) will be satisfied and underflow will be printed.

if(start==NULL)  {  printf("\nUNDERFLOW");     return;   }

 

case 2: list contains single node. Here,the condition (start->next==start) will be satisfied. In this case, we have only one node so we will delete it(start pointer) and make the 'start' pointer free.

if(start->next==start)  {  start=NULL;  free(start);  }

 

case 3: list contains more than one element, then in order to delete the last element, we need to reach the last node. We also need to keep track of the second last node of the list.

p=start;  while(p->next!=start)  {  prep=p;  p=p->next;  }  prep->next=p->next;  free(p);

 

A complete program of different types of operations on circular singly linked list

#include<stdio.h>  #include<stdlib.h>  struct node   {      int data;      struct node *next;   };  struct node *start;    /*fuction declaration of all the operations*/ void insert_begin();   void insert_last();    void delete_begin();  void delete_last();   void print();  void main ()  {  int ch=0;      while(ch!=6)       {          printf("\nEnter the operation to be performed\n");         printf("\n1.Insert in begining\n2.Insert at last\n3.Delete from Beginning\n4.Delete from last\n5.Print\n6.Exit\n");                  scanf("\n%d",&ch);          switch(ch)          {               /*function calls of all the operations */             case 1:              insert_begin();                   break;              case 2:              insert_last();                     break;                case 3:              delete_begin();                   break;              case 4:              delete_last();                    break;              case 5:             print();                    break;              case 6:              exit(0);              break;              default:              printf("Enter valid option");         }      }  }  void insert_begin()  {      struct node *p,*temp;       int value;       p=(struct node *)malloc(sizeof(struct node));      if(p==NULL)      {          printf("\nOVERFLOW");      }      else        {          printf("\nEnter the value: ");          scanf("%d",&value);          p->data=value;          if(start==NULL)          {              start=p;              p->next=start;          }          else           {                 temp=start;              while(temp->next!=start)                  temp=temp->next;              p->next=start;               temp->next=p;               start=p;          }                 }                   }  void insert_last()  {      struct node *p,*temp;       int value;      p=(struct node *)malloc(sizeof(struct node));      if(p==NULL)      {          printf("\nOVERFLOW\n");      }      else      {          printf("\nEnter value:");          scanf("%d",&value);          p->data=value;          if(start==NULL)          {              start=p;              p->next=start;            }          else          {              temp=start;              while(temp->next!=start)              {                  temp=temp->next;              }              temp->next=p;               p->next=start;          }       }   } void delete_begin()  {      struct node *p;       if(start==NULL)      {          printf("\nUNDERFLOW");        }      else if(start->next==start)      {          start=NULL;          free(start);      }      else      {   p=start;           while(p->next!=start)              p=p->next;           p->next=start->next;          free(start);          start=p->next;       }  }  void delete_last()  {      struct node *p, *prep;      if(start==NULL)      {          printf("\nUNDERFLOW");      }      else if (start->next==start)      {          start=NULL;          free(start);  //node will be deleted     }      else       {          p=start;          while(p->next!=start)          {              prep=p;              p=p->next;          }          prep->next=p->next;          free(p);    //node deleted     }  }  void print()  {      struct node *p;      p=start;      if(start==NULL)      {          printf("\nnothing to print");      }         else      {          printf("\n printing values \n");          while(p->next!=start)          {              printf("%d\n",p->data);              p=p->next;          }          printf("%d\n",p->data);      }      }

OUTPUT:

Enter the operation to be performed   1.Insert in begining 2.Insert at last 3.Delete from Beginning 4.Delete from last 5.Print 6.Exit 1   Enter the value: 89   Enter the operation to be performed   1.Insert in begining 2.Insert at last 3.Delete from Beginning 4.Delete from last 5.Print 6.Exit 1   Enter the value: 65   Enter the operation to be performed   1.Insert in begining 2.Insert at last 3.Delete from Beginning 4.Delete from last 5.Print 6.Exit 1   Enter the value: 88   Enter the operation to be performed   1.Insert in begining 2.Insert at last 3.Delete from Beginning 4.Delete from last 5.Print 6.Exit 5    printing values ... 88 65 89   Enter the operation to be performed   1.Insert in begining 2.Insert at last 3.Delete from Beginning 4.Delete from last 5.Print 6.Exit 4   Enter the operation to be performed   1.Insert in begining 2.Insert at last 3.Delete from Beginning 4.Delete from last 5.Print 6.Exit 5    printing values 88 65   Enter the operation to be performed   1.Insert in begining 2.Insert at last 3.Delete from Beginning 4.Delete from last 5.Print 6.Exit

 

Circular doubly linked list

Circular doubly linked list is the complex type of linked list. In this a particular node contains three fields i.e., data field, pointer to previous node, pointer to the next node. It does not contain NULL in any of the node.

The last node of the doubly linked list holds the address of the first node of the list and the first node holds the address of the last node of the list.

Operations on Circular doubly linked list

1. Insertion:

The insertion operation in circular doubly linked list is used to insert the new node. The insertion of node can be performed at different positions.

a) Insertion at the beginning:

There can be two cases while inserting the new node in the list. Either the list is empty or there is at least one element in the list.

First we will allocate the memory to the new node.

In the first case, the condition (start==NULL) will be satisfied as the new node will be the first node of the list and the previous and next pointer of the new node will point to itself.

p=(struct node *)malloc(sizeof(struct node)); start=p;  p->next=start;   p->prev=start;

 

In the second case, the condition (start==NULL) will not be satisfied. Here, we need to reach the last node of the list through traversing the list.

At the end,temp must contain the address of the new node 'p' into its next part as the node which is to be inserted will be the first node.

temp=start;   while(temp->next!=start)  {      temp=temp->next;   } temp->next=p;      p->prev=temp;      start->prev=p;      p->next=start;      start=p;

 

b) Insertion at the end:

There can be two cases while inserting the new node in the list at the end. Either the list is empty or there is at least one element in the list.

First we will allocate the memory to the new node.

In the first case, the condition (start==NULL) will be satisfied as the new node will be the first node of the list and the previous and next pointer of the new node will point to itself.

p=(struct node *)malloc(sizeof(struct node)); start=p;  p->next=start;   p->prev=start;

 

In the second case, the condition (start==NULL) will not be satisfied. As the new node will be inserted at the end of the list. The new node will hold the address of the first node therefore we need to make the next pointer of the last node point to the 'start' node of the list and the previous pointer of the 'start' node will point to the last node.

start->prev=p;  p->next=start; temp->next=p;  p->prev=temp;

 

2. Deletion:

The deletion operation in circular doubly linked list is used to delete the node from the list. The deletion of node can be performed at different positions.

a) Deletion at the beginning:

There can be two cases while deleting a node at the beginning of a circular doubly linked list.

 

In the first case, the ndode which is to be deleted can be the only node of the list. So the condition (start->next==start) will be satisfied, therefore the list needs to be completely deleted.

start=NULL;   free(start);

 

In the second case, the list contains more than one element in the list, therefore the condition (start->next==start) will not be satisfied. Now we will use a while loop to reach to the last node of the list and modify some pointers, 'temp' will point to the last node of the list. The first node of the list i.e. pointed by 'start' pointer, will need to be deleted. Therefore the last node must contain the address of the node that is pointed by the next pointer of the 'start' node.

temp=start;   while(temp->next!=start)       temp=temp->next; temp->next=start->next; start->next->prev=temp; free(start);  start=temp->next;

 

b) Deletion at the end:

There can be two cases while deleting a node at he end of a circular doubly linked list.

 

First case is when the node which is to be deleted can be the only node present in the linked list. So, the condition (start->next==start) will be satisfied and the list needs to be completely deleted.

start=NULL;   free(start);

 

In the second case, the list contains more than one element in the list, therefore the condition (start->next==start) will not be satisfied. Now we will use a while loop to reach the last node of the list. Now, 'temp' will point to the node which is to be deleted from the list. Make the next pointer of previous node of temp, point to the 'start' node of the list.

temp=start;  while(temp->next!=start)      temp=temp->next; temp->prev->next=start; start->prev=p->prev;    free(start)

 

A complete program of different types of operations on circular doubly linked list

#include<stdio.h>  #include<stdlib.h>  struct node  {      struct node *prev;      struct node *next;      int data;  };  struct node *start;  void insert_begin();  void insert_last();   void delete_begin();  void delete_last();  void print();    void main ()  {  int ch=0;      while(ch!=6)      {          printf("\nEnter the operation to be performed\n");         printf("\n1.Insert in begining\n2.Insert at last\n3.Delete from Beginning\n4.Delete from last\n5.Print\n6.Exit\n");                  scanf("\n%d",&ch);          switch(ch)         {              case 1:              insert_begin();                   break;              case 2:              insert_last();                     break;                case 3:              delete_begin();                   break;              case 4:              delete_last();                    break;              case 5:             print();                    break;              case 6:              exit(0);              break;              default:              printf("Enter valid option");         }      }  }  void insert_begin()  {     struct node *p,*temp;      int value;     p=(struct node *)malloc(sizeof(struct node));     if(p==NULL)     {         printf("\nOVERFLOW");     }     else     {      printf("\nEnter the value:");      scanf("%d",&value);      p->data=value;     if(start==NULL)     {        start=p;        p->next=start;         p->prev=start;      }     else      {         temp=start;       while(temp->next!=start)      {          temp=temp->next;       }      temp->next=p;      p->prev=temp;      start->prev=p;      p->next=start;      start=p;     }   }  }  void insert_last()  {     struct node *p,*temp;     int value;     p=(struct node *) malloc(sizeof(struct node));     if(p==NULL)     {         printf("\nOVERFLOW");     }     else     {         printf("\nEnter value");         scanf("%d",&value);          p->data=value;         if(start==NULL)         {             start=p;             p->next=start;              p->prev=start;          }         else         {            temp=start;            while(temp->next!=start)            {                temp=temp->next;            }            temp->next=p;            p->prev=temp;            start->prev=p;        p->next=start;          }     }    }    void delete_begin()  {      struct node *temp;      if(start==NULL)      {          printf("\n UNDERFLOW");      }      else if(start->next==start)      {          start=NULL;           free(start);        }      else      {          temp=start;           while(temp->next!=start)          {              temp=temp->next;          }          temp->next=start->next;          start->next->prev=temp;          free(start);          start=temp->next;      }  }  void delete_last()  {      struct node *p;      if(start==NULL)      {          printf("\n UNDERFLOW");      }      else if(start->next==start)      {          start=NULL;           free(start);         }      else       {          p=start;           if(p->next!=start)          {              p=p->next;           }          p->prev->next=start;          start->prev=p->prev;            free(p);       }  }    void print() {      struct node *p;      p=start;      if(start==NULL)      {          printf("\nnothing to print");      }         else      {          printf("\n printing values \n");          while(p->next!=start)          {              printf("%d\n", p->data);              p=p->next;          }          printf("%d\n", p->data);      }  }

OUTPUT:

Enter the operation to be performed   1.Insert in begining 2.Insert at last 3.Delete from Beginning 4.Delete from last 5.Print 6.Exit 1   Enter the value:89   Enter the operation to be performed   1.Insert in begining 2.Insert at last 3.Delete from Beginning 4.Delete from last 5.Print 6.Exit 1   Enter the value:65   Enter the operation to be performed   1.Insert in begining 2.Insert at last 3.Delete from Beginning 4.Delete from last 5.Print 6.Exit 1   Enter the value:77   Enter the operation to be performed   1.Insert in begining 2.Insert at last 3.Delete from Beginning 4.Delete from last 5.Print 6.Exit 5    printing values 77 65 89   Enter the operation to be performed   1.Insert in begining 2.Insert at last 3.Delete from Beginning 4.Delete from last 5.Print 6.Exit 3   Enter the operation to be performed   1.Insert in begining 2.Insert at last 3.Delete from Beginning 4.Delete from last 5.Print 6.Exit 5    printing values 65 89   Enter the operation to be performed   1.Insert in begining 2.Insert at last 3.Delete from Beginning 4.Delete from last 5.Print 6.Exit 2   Enter value24   Enter the operation to be performed   1.Insert in begining 2.Insert at last 3.Delete from Beginning 4.Delete from last 5.Print 6.Exit 5    printing values 65 89 24   Enter the operation to be performed   1.Insert in begining 2.Insert at last 3.Delete from Beginning 4.Delete from last 5.Print 6.Exit