circular doubly linked list data structure

Circular doubly linked list data structure

Circular Doubly Linked List has properties of both doubly linked list and circular linked list in which two consecutive elements are linked or connected by previous and next pointer and the last node points to the first node by next pointer and also the first node points to the last node by the previous pointer.

A circular doubly linked list is a more complexed type of data structure in which a node contains pointers to its previous node as well as the next node. The circular doubly linked list doesn’t contain NULL in any of the nodes. The last node of the list contains the address of the first node of the list. The first node of the list also contains the address of the last node in its previous pointer.

A circular doubly linked list is shown in the following figure.

Declaring a Doubly circular Linked list

In C language, a double circular linked list can be implemented using structure and pointers.

struct dclink
{
  struct dclink*pre;
  int data;
  struct dclink*next;
};
typedef struct dclink LINK;
LINK*head = NULL;

The above definition is used to create every node in the list. The data field stores the element and the next is a pointer to store the address of the next node and ‘pre’ stores previous node address.

In place of a data type, struct LinkedList is written before next. That’s because of its a self-referencing pointer. It means a pointer that points to whatever it is a part of. Here next is a part of a node and it will point to the next node.typedef is used to define a data type in C.

Creating a node

void createlink()
{
  LINK*th1,*th2;
  char ch;
  int value;
  if(head==NULL)
  {
     head=(LINK*)malloc(sizeof(LINK));
     head->pre=head;
     printf("\nEnter a value: ");
     scanf("%d",&value);
     head->data=value;
     head->next=head;
     printf("\nDou You want to continue Y?");
     fflush(stdin);
     ch=getchar();
     if(ch!='Y'&&ch!='y')
       return;
  }
  th1=head->pre;
  do
  {
    th2=(LINK*)malloc(sizeof(LINK));
    th2->pre=th1;
    printf("\nEnter a value: ");
    scanf("%d",&value);
    th2->data=value;
    th2->next=head;   //th2->next=th1->next;
    th1->next=th2;
    head->pre=th2;
   th1=th2;
   printf("\nDo You want to continue Y? :");
   fflush(stdin);
   ch=getchar();
  }while(ch=='Y'||ch=='y');
  th1=th2=NULL;
  return;
}

Here if HEAD is NULL then always it creates a node at head position. Otherwise, the new node will always be added after the last node. This is known as inserting a node at the rear end.

In double circular LinkedList always nod -> pre should point to previous not and nod -> next should point to head node.

Double circular Lined List traversal

void displayforword()
{
  LINK*th1;
  if(head==NULL)
  {
   printf("\nLIST IS EMPTY");
   return;
  }
  th1=head;
  do
  {
   printf("%d",th1->data);
   th1=th1->next;
  }while(th1!=head);
  return;
}

Here is HEAD is NULL it indicates list is empty else travel from head to end of the list and display all the data until the head has occurred.

void displaybackword()
{
  LINK*th1;
  if(head==NULL)
  {
   printf("\nLIST IS EMPTY");
   return;
  }
  th1=head->pre;
  do
  {
   printf("%d",th1->data);
   th1=th1->pre;
  }while(th1!=head->pre);
  return;
}

Here is HEAD is NULL it indicates list is empty else travel from head->pre to the beginning of the list and display all the data until the head->pre has occurred.

Finding the Number of Nodes

int linkcount()
{
  int count=0;
  LINK*th1;
  if(head==NULL)
   return 0;
  th1=head;
  do
  {
   ++count;
   th1=th1->next;
  }while(th1!=head);
  return count;
}

Double Lined List Insert Operation

Insertion can be performed on any position, the following code can insert a new node at all possible positions 

void insertlink()
{
  LINK*th1,*th2;
  int i,lp,nl;
  int value;
  if(head==NULL)
  {
    head=(LINK*)malloc(sizeof(LINK));
    head->pre=head;
          printf("\nEnter a value: ");
          scanf("%d",&value);
    head->data=value;
    head->next=head;
    return;
  }
  printf("\nEnter Link position: ");
  scanf("%d",&lp);
  nl=linkcount();
  if(lp<1||lp>nl+1)
  {
   printf("\ninvalid postion");
   getch();
   return;
  }
  if(lp==1)
  {
   th1=(LINK*)malloc(sizeof(LINK));
   th1->pre=head->pre;
         printf("\nEnter a value: ");
         scanf("%d",&value);
   th1->data=value;
   th1->next=head;
   head->pre->next=th1;
   head->pre=th1;
   head=th1;
   return;
  }
  th1=head;
  for(i=1;i<lp-1; i++)
   th1=th1->next;

  th2=(LINK*)malloc(sizeof(LINK));
  th2->pre=th1;
  printf("\nEnter a value: ");
  scanf("%d",&value);
  th2->data=value;
  th2->next=th1->next;
  th1->next->pre=th2;
  th1->next=th2;
  th1=th2=NULL;
  return;
}

Double Lined List Deletion Operation

void deletelink()
{
  LINK*th1,*th2;
  int nl,i,lp;
  if(head==NULL)
  {
   printf("\nLIST IS EMPTY");
   return;
  }
  printf("\nEnter Link position: ");
  scanf("%d",&lp);
  nl=linkcount();
  if(lp<1||lp>nl)
  {
   printf("\ninvalid position");
   return;
  }
  if(nl==1)
  {
   free(head);
   head=NULL;
   return;
  }
  if(lp==1)
  {
   th1=head;
   head=head->next;
   head->pre=th1->pre;
   th1->pre->next=head;
   th1->pre=NULL;
   th1->next=NULL;
   free(th1);
   return;
  }
  if(nl==lp)
  {
    th1=head->pre;
    head->pre=th1->pre;
    th1->pre->next=head;
    th1->pre=NULL;
    th1->next=NULL;
    free(th1);
    return;
  }
  th1=head;
  for(i=1; i<lp-1; i++)
    th1=th1->next;
  
   th2=th1->next;
   th1->next=th2->next;
   th2->next->pre=th2->pre; 
  //th2->next->pre=th1;
   th2->pre=NULL;
   th2->next=NULL;
   free(th2);
   return;
}