Doubly Linked List

A linked list is a way to store a collection of elements. Like an array, these can be character or integers. Each element in a linked list is stored in the form of a node.

A doubly-linked list is a linked data structure that consists of a set of sequentially linked records called nodes. Each node contains two fields, called links, that are references to the previous and to the next node in the sequence of nodes.

Declaring a Doubly Linked list

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

struct dlink
{
  struct dlink*pre;
  int data;
  struct dlink*next;
};
typedef struct dlink 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;
    int value;
    char ch;
    if(head==NULL)
    {
        head=(LINK*)malloc(sizeof(LINK));
        head->pre=NULL;
        printf("\nEnter a value: ");
        scanf("%d",&value);
        head->data=value;
        head->next=NULL;
        printf("\nDo You Want to continue Y?: ");
        fflush(stdin);
        ch=getchar();
        if(ch!='Y'&&ch!='y')
            return;
    }
    th1=head;
    while(th1->next!=NULL)
        th1=th1->next;
    do
    {
        th2=(LINK*)malloc(sizeof(LINK));
        th2->pre=th1;
        printf("\nEnter a value: ");
        scanf("%d",&value);
        th2->data=value;
        th2->next=NULL;
        th1->next=th2;
        th1=th1->next;   //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.

Double Lined List traversal

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

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

Finding the Number of Nodes

int linkcount()
{
  LINK*th;
  int count=0;
  if(head==NULL)
   return 0;
  th=head;
  while(th!=NULL)
  {
    ++count;
    th=th->next;
  }
  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 value;
  int nl,i,lp;
  if(head==NULL)
  {
    head=(LINK*)malloc(sizeof(LINK));
    head->pre=NULL;
          printf("\nEnter data: ");
          scanf("%d",&value);
    head->data=value;
    head->next=NULL;
    return;
  }
  printf("\nEnter link position: ");
  scanf("%d",&lp);
  nl=linkcount();
  if(lp<1||lp>nl+1)
  {
    printf("\ninvalid position");
    return;
  }
  if(lp==1)
  {
   th1=(LINK*)malloc(sizeof(LINK));
   th1->pre=NULL;
         printf("\nEnter data: ");
         scanf("%d",&value);
   th1->data=value;
   th1->next=head;
   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 data: ");
  scanf("%d",&value);
  th2->data=value;
  th2->next=th1->next;
  th1->next=th2;

  if(lp!=nl+1)
   th2->next->pre=th2;

  th1=th2=NULL;
  return;
}

Double Lined List Deletion Operation

void deletelink()
{
  LINK*th1,*th2;
  int lp,i,nl;
  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;
   th1->next=NULL;
   head->pre=NULL;
   free(th1);
   return;
  }
  th1=head;
  for(i=1; i<lp-1; i++)
   th1=th1->next;

  
  th2=th1->next;
  th1->next=th2->next;
  
  if(lp!=nl)
    th2->next->pre=th1;

  th2->pre=NULL;
  th2->next=NULL;
  free(th2);
  return;
}