DATA STRUCTURES

doubly linked list

Doubly Linked List:

Doubly linked list is a list in which a node has three parts data part and two pointers in which first pointer(previous) contains the address of the previous node and second pointer(next) contains the address of next node in the list. In Doubly linked list we can traverse in both directions means there is also a reverse direction in the list. Here also starting of linked list is pointed out by start pointer and end of list is marked by NULL in the next pointer of the last node.

syntax/structure

struct node
{
struct node *previous;
int data;
struct node *next;
}

 

Menu driven program for doubly linked list:

#include<stdio.h>
#include<conio.h>
#include<string.h>
#include<stdlib.h>
struct node
{
int roll;
char name[20];
struct node *next;
struct node *prev;
};
struct node *head=NULL;

void insertnode_start(int data,char name[])
{
struct node *temp;
temp=(struct node *)malloc(sizeof(struct node));
temp->roll=data;
strcpy(temp->name,name);
temp->next=NULL;
temp->prev=NULL;
if(head==NULL)
head=temp;
else
{
temp->next=head;
head=temp;
}
}
void insertnode_end(int data,char name[])
{
struct node *cur=head;
struct node *temp;
temp=(struct node *)malloc(sizeof(struct node));
temp->roll=data;
strcpy(temp->name,name);
temp->next=NULL;
temp->prev=NULL;
if(head==NULL)
head=temp;
else
{
while(cur->next!=NULL)
{
cur=cur->next;
}
temp->prev=cur;
cur->next=temp;
}
}
void insertnode_loc(int loc, int data,char name[])
{
int i;
struct node *cur=head;
struct node *temp;
temp=(struct node *)malloc(sizeof(struct node));
temp->roll=data;
strcpy(temp->name,name);
temp->next=NULL;
temp->prev=NULL;
for(i=1;i<loc;i++)
cur=cur->next;
if(loc<1 || cur==NULL || cur->next==NULL)
{
printf("nWrong Location - Insertion not possible n");
return;
}
temp->next=cur->next;
temp->prev=cur;
cur->next=temp;
(temp->next)->prev=temp;
}

void deletenode_start()
{
struct node *cur=head;
if(head==NULL)
{
printf("nDoubly Linked is Emptyn ");
return;
}
head=head->next;
head->prev=NULL;
free(cur);
printf("nNode Deleted from Startn");
}

void deletenode_end()
{
struct node *cur=head;
struct node *prev_cur;
if(head==NULL)
{
printf("nDoubly Linked is Emptyn ");
return;
}
while(cur->next!=NULL)
{
prev_cur=cur;
cur=cur->next;
}
prev_cur->next=NULL;
free(cur);
printf("nNode Deleted from Endn");
}
void deletenode_loc(int loc)
{
struct node *cur=head;
struct node *prev_cur;
int i;
if(head==NULL)
{
printf("nDoubly Linked is Empty n");
return;
}
for(i=1;i<loc;i++)
{
prev_cur=cur;
cur=cur->next;
}
if(loc<1 || cur==NULL || cur->next==NULL)
{
printf("nWrong Location - Deletion not possible n");
return;
}
prev_cur->next=cur->next;
(cur->next)->prev=prev_cur;
free(cur);
printf("nNode %d Deletedn ",loc);
}


void traverse_llist()
{
struct node *cur=head;
if(head==NULL)
printf(" Doubly Linked List is empty");
else
{
printf("Roll nott Name n");
while(cur!=NULL)
{
printf("%dtt%s n",cur->roll,cur->name);
cur=cur->next;
}

}
}
main()
{
int roll;
char name[20];
int l;
int choice;

do
{

printf("nn******** Various Operation on doubly Linked List Data Structure********nnMain Menu:");
printf("n Enter 1 : Add Node to doubly Linked List (Start, End or Location)");
printf("nEnter 2 : Delete a Node to doubly Linked List (Start, End or Location).");
printf("n Enter 3 : Traverse all Nodes in doubly Linked List");
printf("n Enter Any other Key to Exit");
printf("nEnter Your Choice: __");
scanf("%d", &choice);



switch(choice)
{
case 1:
printf("Enter 1: to insert at start/begning nn");
printf("Enter 2: to insert at end nn");
printf("Enter 3: to insert in between nodes nn");
scanf("%d",&choice);
switch(choice)
{
case 1:

// insert at start
printf("Enter a roll no to addn");
scanf("%d",&roll);
printf("Enter a name to addn");
scanf("%s",&name);

insertnode_start(roll,name);


break;
case 2:
// insert at end
printf("Enter a value to addn");
scanf("%d",&roll);
printf("Enter a name to addn");
scanf("%s",&name);
insertnode_end(roll,name);

break;
case 3:
//insert in between nodes
printf("Enter the location where you want to add itemn");
scanf("%d",&l);
printf("Enter roll no to addn");
scanf("%d",&roll);
printf("Enter a name to addn");
scanf("%s",&name);
insertnode_loc(l,roll,name);
break;


default:
printf("%d:invalid option. try again...n",choice);
}
break;
case 2:
printf("Enter 1: to delete at start/begning nn");
printf("Enter 2: to delete at end nn");
printf("Enter 3: to delete in between nodes nn");
scanf("%d",&choice);
switch(choice)
{
case 1:

// delete at start

deletenode_start();
break;
case 2:
// delete at end
deletenode_end();

break;
case 3:
//delete in between nodes
printf("Enter the location where you want to delete itemn");
scanf("%d",&l);
deletenode_loc(l);
break;

default:
printf("%d:invalid option. try again...n",choice);
}
break;
case 3:
traverse_llist();
break;

default:
exit(0);
}
} while(choice);
getch();
}

 

Show More

Related Articles

Leave a Reply

Your email address will not be published. Required fields are marked *

Check Also
Close
Back to top button