Difference between singly linked list and doubly linked list

  • Linked lists are among the simplest and most common data structures. 
  • It is used to implement the  several other common types (Abstract data types,stacks,Queues,Associative arrays and S-expressions).
  • Mainly they are two types of linked list singly linked list and doubly linked list

 Difference between singly linked list and doubly linked list


Single linked list
Double linked list
It has tail only
It has head and tail
It has next node only
It has next and previous only
Singly linked lists contain nodes which have a data field as well as a 'next' field, which points to the next node in line of nodes. Operations that can be performed on singly linked lists include insertion, deletion and traversal.
In a 'doubly linked list', each node contains, besides the next-node link, a second link field pointing to the 'previous' node in the sequence. The two links may be called 'forward('s') and 'backwards', or 'next' and 'prev'('previous').
Singly linked list
A singly linked list whose nodes contain two fields: an integer value and a link to the next node

Doubly linked list



A doubly linked list whose nodes contain three fields: an integer value, the link forward to the next node, and the link backward to the previous node

Coding for singly linked list :
#include<stdio.h>
#include<malloc.h>
#include<stdlib.h>
struct NODE
{
     int data;
     struct NODE *next;
}*start = NULL;
struct NODE *newNode = NULL,*currentNode = NULL;
void createNode();
void displayList();
void searchNode();
int lengthList();
void insertNode();
void deleteNode();
int main()
{
     int choice,len;
     char wish;
     do{
          printf("\n\tSINGLY LINKED LIST OPERATIONS\n");
          printf("\t-------------------------------------  \n");
          printf("\n\t 1.CreatNode \n\t 2.Display List \n\t
          3.Search Node \n\t 4.Length");
          printf("\n\t 5.Insert \n\t 6.Delete Node \n\t
          7.Exit");
          printf("\n Enter your choice: ");
          scanf("%d",&choice);
          switch(choice)
          {
              case 1:
                   createNode();
                   break;
              case 2:
                   displayList();
                   break;
              case 3:
                   searchNode();
                   break;
              case 4:
                   len = lengthList();
                   printf("\n Lenght of the list is: %d",len);
                   break;
              case 5:
                   insertNode();
                   break;
              case 6:
                   deleteNode();
                   break;
              case 7:
                   exit(0);
              default:
                   printf("\n Enter correct choice....");
          }
          printf("\n Do you want to continue the list
          operations? (y/n)");
          scanf("%c%c",&wish,&wish);
     }while(wish=='y');
     return 0;
}


void createNode()
{
     char ch;
     do
     {
        newNode = (struct NODE *)malloc(sizeof(struct NODE));
          printf("\n Enter the data: ");
          scanf("%d", &newNode->data);
          newNode->next = NULL;
          if(start==NULL)
          {
              start = newNode;
              currentNode = newNode;
          }
          else
          {
              currentNode->next = newNode;
              currentNode = newNode;
          }
          printf("\nSuccessfully Nodes are created and linked
          together properly..");
          printf("\nContinue to create Node:(y/n)");
          scanf("%c%c",&ch,&ch);
     }while(ch=='y');
}

void displayList()
{
     struct NODE *temp = NULL;
     temp = start;
     printf("\n\n");
     if(start == NULL)
     {
          printf("\n There is no nodes are available to
          print..\n");
          exit(0);
     }
     else
     {
          while(temp != NULL)
          {
              printf("%5d",temp->data);
              temp = temp->next;
          }
     }
}

void searchNode()
{
     int no,flag=0;
     char ch;

     struct NODE *temp = NULL;
    do
    {
          printf("\n Enter the Data to find:");
          scanf("%d",&no);
          flag=0;
          temp = start;

          while(temp != NULL)
          {
              if(no == temp->data)
              {
                   printf("%d is present at list..",temp
                   ->data);
                   flag=1;
                   break;
              }
              temp = temp->next;
          }
          if(flag==0)
          {
              printf("\n Your search element is not present in
              list..");
          }
          printf("\n Want to Search again? (y/n)");
          scanf("%c%c",&ch,&ch);
     }while(ch=='y');
}

int lengthList()
{
     int count=0;
     struct NODE *temp = NULL;

     temp = start;

     while(temp != NULL)
     {
          count++;
          temp = temp -> next;
     }
     return count;
}

void insertNode()
{
     int pos,len;
     struct NODE *temp = NULL;
     len = lengthList();
     printf("\n Enter the position to add: ");
     scanf("%d",&pos);
     if(pos>0 && pos<= len+1)
     {
          newNode = (struct NODE *)malloc(sizeof(struct NODE));
          printf("\n Enter the data:");
          scanf("%d",&newNode->data);
          newNode->next = NULL;
          if(pos==1)
          {
               newNode->next = start;
              start = newNode;
          }
          else
          {
              temp = start;
              while(pos > 2)
              {
                   temp = temp->next;
                   pos--;
              }
              newNode->next = temp->next;
              temp->next = newNode;
          }
     }
     else
          printf("\n Given position is wrong..");
}
void deleteNode()
{
     int pos,len;
     struct NODE *temp = start;
     len = lengthList();
     printf("\n Enter the position to delete: ");
     scanf("%d",&pos);
     if(pos>0 && pos<=len)
     {
          if(pos==1)
          {
              start = start->next;
              free(temp);
          }
          else
          {
              while(pos  > 2)
              {
                   temp = temp->next;
                   pos--;
              }
              newNode = temp->next;
              temp->next = newNode->next;
              free(newNode);
          }
     }
     else
     {
          printf("\n Invalid Position...");
     }
}

OUTPUT:

               SINGLY LINKED LIST OPERATIONS
        -----------------------------------------
         1.CreatNode
         2.Display List
         3.Search Node
         4.Length
         5.Insert
         6.Delete Node
         7.Exit
Enter your choice: 1
Enter the data: 12
Successfully Nodes are created and linked together properly..
Continue to create Node:(y/n)
Enter the data: 1
Successfully Nodes are created and linked together properly..
Continue to create Node:(y/n)
Enter the data: 6
Successfully Nodes are created and linked together properly..
Continue to create Node:(y/n)
Do you want to continue the list operations? (y/n)


Coding for Doubly Linked list :
#include<stdio.h>
struct NODE
{
     int data;
     struct NODE *prev;
     struct NODE *next;
}*start = NULL;
struct NODE *newNode = NULL,*currentNode = NULL;

void createNode()
{
     char ch;
     struct NODE *temp = NULL;
     do
     {
          newNode = (struct NODE *)malloc(sizeof(struct NODE));
          printf("\n Enter the data: ");
          scanf("%d", &newNode->data);
          newNode->next = NULL;
          newNode->prev = NULL;
          if(start==NULL)
          {
              start = newNode;
              currentNode=newNode;
          }
          else
          {
              currentNode->next=newNode;
              newNode->prev=currentNode;
              currentNode=newNode;
          }
          printf("\nSuccessfully Nodes are created and linked together properly..");
          printf("\nContinue to create Node:(y/n)");
          scanf("%c%c",&ch,&ch);
     }while(ch=='y');
}
void displayList()
{
     struct NODE *temp = NULL;
     temp = start;
     printf("\n\n");
     if(start == NULL)
     {
          printf("\n There is no nodes are available to print..\n");
          exit(0);
     }
     else
     {
          while(temp != NULL)
          {
              printf("%5d",temp->data);
              temp = temp->next;
          }
     }
}

void searchNode()
{
     int no,flag=0;
     char ch;
     struct NODE *temp = NULL;
    do
    {
          printf("\n Enter the Data to find:");
          scanf("%d",&no);
          flag=0;
          temp = start;
          while(temp != NULL)
          {
              if(no == temp->data)
              {
                   printf("%d is present at list..",temp->data);
                   flag=1;
                   break;
              }
              temp = temp->next;
          }
          if(flag==0)
          {
              printf("\n Your search element is not present in list..");
          }
          printf("\n Want to Search again? (y/n)");
          scanf("%c%c",&ch,&ch);
     }while(ch=='y');
}

int lengthList()
{
     int count=0;
     struct NODE *temp = NULL;
     temp = start;
     while(temp != NULL)
     {
          count++;
          temp = temp -> next;
     }
     displayList();
     return count;
}

void insertNode()
{
     int pos,len;
     struct NODE *temp = NULL;
     len = lengthList();
     printf("\n Enter the position to add: ");
     scanf("%d",&pos);
     if(pos>0 && pos<= len+1)
     {
          newNode = (struct NODE *)malloc(sizeof(struct NODE));
          printf("\n Enter the data:");
          scanf("%d",&newNode->data);
          newNode->prev = NULL;
          newNode->next = NULL;
          if(pos==1)
          {
              newNode->next = start;
              start->prev = newNode;
              start = newNode;
          }
          else
          {
              temp = start;
              while(pos > 2)
              {
                   temp = temp->next;
                   pos--;
              }
              if(temp->next!=NULL)
            temp->next->prev = newNode;

              newNode->next = temp->next;
              newNode->prev = temp;
              temp->next = newNode;
          }
     }
     else
          printf("\n Given position is wrong..");
}

void deleteNode()
{
     int pos,len;
     struct NODE *temp = start;
     len = lengthList();
     printf("\n Enter the position to delete: ");
     scanf("%d",&pos);
     if(pos>0 && pos<=len)
     {
          if(pos==1)
          {
              start = start->next;
              start->prev = NULL;
              free(temp);
          }
          else
          {
            while(pos  > 2)
              {
                   temp = temp->next;
                   pos--;
              }
              newNode = temp->next;
              temp->next = newNode->next;
              if(newNode->next!=NULL)
              newNode->next->prev = temp;
              free(newNode);
          }
     }
     else
     {
          printf("\n Invalid Position to Delete...");
     }
}

int main()
{
     int choice,len;
     char wish;
     do{
          printf("\n\tDOUBLY LINKED LIST OPERATIONS\n");
          printf("\t-----------------------------------------\n");
          printf("\n\t 1.CreatNode \n\t 2.Display List \n\t 3.Search Node \n\t 4.Length");
          printf("\n\t 5.Insert \n\t 6.Delete Node \n\t 7.Exit");
          printf("\n Enter your choice: ");
          scanf("%d",&choice);
          switch(choice)
          {
              case 1:
                   createNode();
                   break;

              case 2:
                   displayList();
                   break;
              case 3:
                   searchNode();
                   break;
              case 4:
                   len = lengthList();
                   printf("\n Lenght of the list is: %d",len);
                   break;
              case 5:
                   insertNode();
                   break;
              case 6:
                   deleteNode();
                   break;
              case 7:
                   exit(0);
              default:
                   printf("\n Enter correct choice....");
          }
          printf("\n Do you want to continue the list operations? (y/n)");
          scanf("%c%c",&wish,&wish);
     }while(wish=='y');
     return 0;
}



OUTPUT:

              DOUBLY LINKED LIST OPERATIONS
        -----------------------------------------
         1.CreatNode
         2.Display List
         3.Search Node
         4.Length
         5.Insert
         6.Delete Node
         7.Exit
 Enter your choice: 1
 Enter the data: 12
Successfully Nodes are created and linked together properly..
Continue to create Node:(y/n)
 Enter the data: 43
Successfully Nodes are created and linked together properly..
Continue to create Node:(y/n)
 Enter the data: 78










Share this post
  • Share to Facebook
  • Share to Twitter
  • Share to Google+
  • Share to Stumble Upon
  • Share to Evernote
  • Share to Blogger
  • Share to Email
  • Share to Yahoo Messenger
  • More...

0 comments:

Post a Comment