Doubly Linked List in C

Doubly linked list data structure in linear data structure where each element has following three elements.

  1. Data
  2. Address of Next Node
  3. Address of Previous Node

Doubly Linked LIst

Advantages of Doubly Linked List

  1.  Traversal in both forward and backward directions.

Disadvantages of Doubly Linked List

  1. Extra previous node pointer needed .
  2. Random search not allowed.

Operations performed on Doubly Linked List

  1. Creation
  2. Insertion At Beginning
  3. Insertion At End
  4. Insertion At specified Position
  5. Display all elements

Source Code

#include<stdio.h>
#include<conio.h>
#include<alloc.h>
struct student
{
int id;
char name[20];
int marks;
struct student *next,*prev;
}*start=NULL,*last=NULL;
typedef struct student n;
void create_list(int);
void add_nodeAtbegin();
void add_nodeAtEnd();
void specifiedpos(int);
void displaylist();
void displayInReverseOrder();
void main()
{
int choice,num,pos=0,end;
clrscr();
printf("Menu");
printf("\n1:Create List");
printf("\n2:Add node at first position");
printf("\n3:Add node at end position ");
printf("\n4:Add node at specified position");
printf("\n5:Display all element ");
printf("\n6:Display In Reverse order");
printf("\n0 Exit");
printf("\nEnter your choice");
scanf("%d",&choice);
while(choice>0)
{
switch(choice)
{
case 1:
printf("\nEnter how many node you want to create");
scanf("%d",&num);
create_list(num);
break;
case 2:
printf("\nYou're adding node at beginning position");
add_nodeAtbegin();
break;
case 3:
printf("\nYou are adding node at end position");
add_nodeAtEnd();
break;
case 4:
printf("\nEnter position to which you want to add new node");
scanf("%d",&pos);
specifiedpos(pos);
break;

case 5:
printf("\nDisplay all elements");
displaylist();
break;
case 6:
displayInReverseOrder();
break;
default :
printf("\nWrong Input");
break;
}
printf("\nDo you want to continue");
scanf("%d",&choice);
}
getch();
}
void create_list(int num)
{
int i;
n  *new_node,*current_node;
//reset start and end to NULL while creating fresh list
start=NULL;
last = NULL;
for(i=0;i<num;i++)
{
new_node=(n*)malloc(sizeof(n));
new_node->next=NULL;
new_node->prev=NULL;
printf("\nEnter Student ID");
scanf("%d",&new_node->id);
getchar();
printf("\nEnter Name");
gets(new_node->name);
printf("\nEnter Marks");
scanf("%d",&new_node->marks);
if(start==NULL)
{
start=new_node;
current_node=new_node;
}
else
{
current_node->next=new_node;
new_node->prev=current_node;
current_node=new_node;
}
}
last=new_node;
}
void add_nodeAtbegin()
{
n *new_node;
new_node=(n*)malloc(sizeof(n));
printf("\nEnter Student ID");
scanf("%d",&new_node->id);
getchar();//remove new line
printf("\nEnter Name");
gets(new_node->name);
printf("\nEnter marks");
scanf("%d",&new_node->marks);
new_node->next=start;
start->prev=new_node;
start=new_node;
}
void add_nodeAtEnd()
{
n *new_node;
if(start==NULL)
{
printf("\nlist is empty");
}
else
{
new_node=(n*)malloc(sizeof(n));
printf("\nEnter Student ID");
scanf("%d",&new_node->id);
getchar(); //to remove new line from buffer
printf("\nEnter  name");
gets(new_node->name);
printf("\nEnter marks");
scanf("%d",&new_node->marks);

new_node->next=NULL;
last->next=new_node;
new_node->prev=last;
}
}
void displaylist()
{
n *temp=start;
printf("\n=============Information Of Students==============");
while(temp!=NULL)
{
printf("\nStudent ID=%d",temp->id);
printf("\nName=");
puts(temp->name);
printf("Marks=%d",temp->marks);
temp=temp->next;
printf("\n--------------------");
}
}
void specifiedpos(int pos)
{
int cnt=1,marks;
n *new_node,*temp=start,*current_node;
new_node=(n*)malloc(sizeof(n));
new_node->next=NULL;
printf("\nEnter student id");
scanf("%d",&new_node->id);
getchar();
printf("\nEnter Name");
gets(new_node->name);
printf("\nEnter marks");
scanf("%d",&marks);

while(temp!=NULL)
{
if(cnt==pos)
{
 current_node=temp;
 break;
 }
 temp=temp->next;
 cnt++;
 }
 //New Node next address will be updated by found node address
 new_node->next=current_node;
 //new_node prev address updated by current_node->prev
 new_node->prev = current_node->prev;

 //Update node address at position-1(current_node->prev->next=new_node) by new_node
 current_node->prev->next = new_node;

 //Found node prev address will be update by
 current_node->prev = new_node;
 }
 void displayInReverseOrder(){
  n *temp=last;
  printf("\n:::::::::::::In Reverse Order:::::::::::::");
  while(temp!=NULL)
  {
  printf("\n---------------------");
  printf("\nStudent id =%d",temp->id);
  printf("\nStudent Name=");
  puts(temp->name);
  printf("\nMarks=%d",temp->marks);
  temp=temp->prev;
  }
 }

Leave a Reply