DOUBLY LINKED LIST
Structure Definition for Doubly Linked List: (Include structure definition for all Doubly Linked
List programs)
struct node{
int data;
struct node *llink;
struct node *rlink;
};
struct node *root=NULL,*tail;
//Display the elements of DLL
void display() {
struct node *temp;
temp=root;
while(temp!=NULL)
{
printf(“%d”,temp->data);
temp=temp->rlink;
}
}
//Insert a node at end
void insert_end(){
struct node*temp;
temp=(struct node*)malloc(sizeof(struct node));
printf(“enter data”);
scanf(“%d”,&temp->data);
temp->llink=NULL;
temp->rlink=NULL;
if(root==NULL){
root=temp;
tail=temp;
}
else{
tail->rlink=temp;
temp->llink=tail;
tail=temp;
}
}
//Insert at beginning
void ins_beg(){
struct node*temp;
temp=(struct node*)malloc(sizeof(struct node))
printf(“enter data”);
scanf(“%d”,&temp->data);
temp->llink=NULL
temp->rlink=NULL
if (root==NULL)
{
root=temp;
tail=temp;
}
else
{
root->llink=temp;
temp->rlink=root;
root=temp;
}
}
//Insert at specified position
void ins_at_pos(){
int pos, i=1;
printf (“enter pos”);
scanf (“%d”,&pos);
if (pos<1)
{
printf(“invalid pos”);
}
else if(pos==1)
{
ins_beg()
}
else
{
struct node*temp,*p=root;
temp=(struct node*)malloc(sizeof(struct node))
printf(“enter data”);
scanf(“%d”,&temp->data);
temp->llink=NULL;
temp->rlink=NULL;
while(i<pos-1)
{
temp=temp->rlink;
i++;
}
temp->llink=p;
temp->rlink=p->rlink;
temp->rlink=temp;
temp->rlink->llink=temp;
}
}
//Insert after a specified position
void in_after_pos(){
int pos , i=1;
printf("enter the positions\n");
scanf("%d",&pos);
if(pos<1)
{
printf("invalid position\n");
}
else
{
struct node *temp,*p = root;
temp = (struct node*)malloc(sizeof(struct node));
printf("enter the data\n");
scanf("%d",&temp->data);
temp->llink = NULL;
temp->rlink = NULL;
while(i<pos)
{
temp=temp->rlink;
i++;
}
temp->llink=p;
temp->rlink=p->rlink;
temp->rlink=temp;
temp->rlink->llink=temp;
}
}
//Delete at beginning
void del_beg(){
struct node *temp;
if (root == NULL)
{
printf("empty list\n");
}
else
{
temp=root;
root=root->rlink;
root->llink=NULL;
free(temp);
}
}
//Delete at end
void del_end(){
struct node *temp;
if(tail==NULL)
{
printf("empty list\n");
}
else
{
temp=tail;
tail->llink->rlink=NULL;
tail=tail->llink;
free(temp);
}
}
//Delete at the specified position
void del_pos()
{
int pos i=1;
struct node *temp = root;
printf("enter the positions\n");
scanf("%d",&pos);
while (i<pos)
{
temp=temp->rlink;
i++;
}
temp->llink->rlink=temp->rlink;
temp->rlink->llink=temp->llink;
free(temp);
}
//Reverse the list
void reverse(){
struct node *c,*n;
c=root;
while (c!=NULL)
{
n=c->rlink;
c->rlink=c->llink;
c->llink=n;
c=n;
}
c=root;
root=tail;
tail=c;
}
//Concatenate two lists
void concatenate(struct node *root1,struct node *root2){
struct node *temp;
temp=root1;
while(temp->rlink!=NULL)
{
temp=temp->rlink;
}
temp->rlink=root2;
root2->llink=temp;
}
Note:
1. Stack can be implemented using any linked list using the following functions
a) Insert at front, delete at front, display
Or
b) Insert at end, delete at end, display
2. Queue can be implemented using any linked list using the following functions
c) Insert at front, delete at end, display
Or
d) Insert at end, delete at front, display
