Operation on a linear doubly linked list
In singly link list, every node contains the address of its next node, so that we can easily traverse through the list, but it only one direction i.e. We cannot traverse reversely i.e. If we want to do operation with just previous node then we must again start with the first node. This drawback is overcome by introducing doubly linked list in which each node has a address of next node as well as previous node.
Program: Following program creates linear doubly linked list and displays the same.
#include<stdio.h>
#include<conio.h>
#include<malloc.h>
struct node
{
int info;
struct node *prev,*next;
};
typedef struct node NODE;
NODE *start=NULL;
void main()
{
NODE *temp, *n;
int data;
char ch=’y’;
clrscr();
while(ch==’y’ || ch==’Y’)
{
printf(“\n Enter data to store: ”);
scanf(“%d”,&data);
n=(NODE*)malloc(sizeof(NODE));
n->info=data;
n->prev=NULL;
if(start==NULL)
{
n->next=NULL
start->prev=n;
start=n;
}
else
{
n->next=start;
start->prev=n;
start=n;
}
fflush(stdin);
printf(“\n Do you want to continue ? (Y / N): ”);
ch=getchar();
}
if(start==NULL)
{
printf(“\n List is empty: ”);
return;
}
temp=start;
printf(“\n Linked list is: ”);
while(temp!= NULL)
{
printf(“%d->”, temp->info);
temp=temp->next;
}
getch();
}
Inserting an element in the list
It is possible in three ways-
- Insertion at the beginning
- Insertion at the end
- Insertion in between
- Insertion at beginning
n->prev=NULL;
n->next=start;
start->prev=n;
start=n;
- Insertion at the end
temp->next=n;
n->prev=temp;
n->next=NULL;
- Insertion in between
Temp->next->prev=n;
n->next=temp->next;
n->prev=temp;
temp->next=n;
Program:
Following program shows the operations insert at beginning, insert after in linear doubly linked list and displays the same.
#include<stdio.h>
#include<conio.h>
#include<malloc.h>
struct node
{
int info;
struct node *prev, *next;
};
typedef struct node NODE;
NODE *start=NULL;
void main()
{
int ch;
void create();
void addatbeg();
void addafter();
void display();
printf(“\n Create doubly linked list: ”);
create();
while(1)
{
clrscr();
printf(“\n 1. Insert at beginning ”);
printf(“\n 2. Insert after”);
printf(“\n 3. Display”);
printf(“\n 4. Exit”);
printf(“\n Enter your choice: ”);
scanf(“%d”,&ch);
switch(ch)
{
case 1:
addatbeg();
break;
case 2:
addafter();
break;
case 3:
display();
break;
case 4: exit(0);
default: printf(“\n Enter correct choice…”);
}
}
}
void create()
{
int data;
char ch=’y’;
NODE *n;
while(ch==’y’ || ch==’y’)
{
printf(“\n Enter data to store: ”);
scanf(“%d”, &data);
n=(NODE*)malloc(sizeof(NODE));
n->info=data;
n->prev=NULL;
if(start==NULL)
{
n->next=NULL;
start->prev=n;
start=n;
}
else
{
n->next=start;
start->prev=n;
start=n;
}
fflush(stdin);
printf(“\n Do you want to continue ? (Y / N): ”);
ch=getchar();
}
}
void addatbeg()
{
NODE *n;
int data;
printf(“\n Enter the element: ”);
scanf(“%d”,&data);
n=(NODE*)malloc(sizeof(NODE));
n->prev=NULL;
n->info=data;
n->next=start;
start->prev=n;
start=n;
}
void addafter
{
NODE *n, *temp;
int i, data, pos;
printf(“\n Enter data to store: ”);
scanf(“%d”, &data);
printf(“\n Enter the position after which this data is inserted: ”);
scanf(“%d”, &pos);
temp=start;
for(i=0;i<pos-1;i++)
{
temp=temp->next;
if(temp==NULL)
{
printf(“\n There are less than %d elements”,pos);
return;
}
}
n=(NODE*)malloc(sizeof(NODE));
n->info=data;
temp->next->prev=n;
n->next=temp->next;
n->prev=temp;
temp->next=n;
}
void display()
{
NODE *temp;
if(start==NULL)
{
printf(“\n List is empty”);
return;
}
temp=start;
printf(“\n Linked list is: ”);
while(temp!=NULL)
{
printf(“%d->”,temp->info)
temp=temp->next;
}
getch();
printf(“\n \n”);
}
Deleting an element
1.Deleting from beginning
temp1=start;
start=start->next;
start->prev=null;
free(temp1);
- Deleting the last element
temp1=temp->next;
temp->next=null;
free(temp1);
- Deletion in between
temp1=temp->next;
temp->next=temp1->next;
temp1->next->prev=temp;
free(temp1);
Program:
Following program shows the operations delete in linear doubly linked list and displays the same. It deletes the node with given data.
#include<stdio.h>
#include<conio.h>
#include<malloc.h>
struct node
{
int info;
struct node *next, *prev;
};
typedef struct node NODE;
NODE *start;
void main()
{
int ch;
void delet();
void display();
void create();
clrscr();
printf(“\n Create doubly linked list: ”);
create();
while(1)
{
clrscr();
display();
printf(“\n 1. Delete”);
printf(“\n 2. Display”);
printf(“\n 3. Exit”);
printf(“\n Enter your choice: ”);
scanf(“%d”,&ch);
switch(ch)
{
case 1:
delet();
break;
case 2:
display();
break;
case 3:
exit(0);
default:
printf(“\n Enter correct choice…”);
}
}
}
void create()
{
int data;
char ch=’y’;
NODE *n;
while(ch==’y’ || ch==’Y’)
{
printf(“\n Enter data to store: ”);
scanf(“%d”,&data);
n=(NODE*)malloc(sizeof(NODE));
n->info=data;
n->prev=NULL;
if(start==NULL)
{
n->next=NULL;
start->prev=n;
start=n;
}
else
{
n->next=start;
start->prev=n;
start=n;
}
fflush(stdin);
printf(“\n Do you want to continue ? (Y / N)”);
ch=getchar();
}
}
void delet()
{
NODE *temp, *temp1;
int data;
printf(“\n Enter the element for deletion: ”);
scanf(“%d”,&data);
if(start->info==data) // first element deleted
{
temp1=start;
start=start->next;
start->prev=NULL;
free(temp1);
return;
}
temp=start;
while(temp->next->next!=NULL) /* element deleted in between */
{
if(temp->next->info==data)
{
temp1=temp->next;
temp->next=temp1->next;
temp->next->prev=temp;
free(temp1);
return;
}
temp=temp->next;
}
if(temp->next->info==data) /* last element deleted */
{
temp1=temp->next;
free(temp1);
temp->next=NULL;
return;
}
printf(“\n Element %d not found”,data);
getch();
}
void display()
{
NODE *temp;
if(start==NULL)
{
printf(“\n Linked list is empty”);
return;
}
temp=start;
printf(“\n Double linked list: ”);
while(temp!=NULL)
{
printf(“%d->”,temp->info);
temp=temp->next;
}
printf(“\n \n”);
}
Some More:
POP- Introduction to Programming Using ‘C’
OOP – Object Oriented Programming
DBMS – Database Management System
RDBMS – Relational Database Management System
Join Now: Data Warehousing and Data Mining