.png)
We strongly recommend to refer Linked lists post as a prerequisite of this post.
A Doubly Linked Lists (DLL) is a linked data structure that consists of sequentially linked nodes. Each node contains three fields: two link fields (prev and next) and one data field.
The beginning and ending nodes' previous and next links, respectively, point to NULL.
Following is the representation of a DLL node in C:
struct Node{
int data;
struct Node* prev; // Pointer to previous node in DLL
struct Node* next; // Pointer to next node in DLL
};Before moving forward we must discuss some points about DLL:
As stated it can be traversed in both forward and backward direction.
The delete operation in DLL is more efficient if pointer to the node to be deleted is given.
Every node of DLL Require extra space for an previous pointer. It is possible to implement DLL with single pointer though.
All operations require an extra pointer previous to be maintained
Operations that can be performed on DLL:
1) Insertion
2) Deletion
3) Traversing
Simple Implementation Using C:
#include <stdio.h>
#include <stdlib.h>
struct Node
{
int data;
struct node *prev;
struct node *next;
}*head=NULL,*tail=NULL,*temp=NULL,*q=NULL;
int count=0;
typedef struct Node node;
void insert_beg();
void insert_end();
void insert_pos();
void delete_pos();
void traverse_beg();
void traverse_end();
void main()
{
while(1)
{
int ch;
printf("\n-----------------------------");
printf("\n 1 - Insert at beginning");
printf("\n 2 - Insert at end");
printf("\n 3 - Insert at position i");
printf("\n 4 - Delete at i");
printf("\n 5 - Display from beginning");
printf("\n 6 - Display from end");
printf("\n 7 - Exit");
printf("\n-----------------------------");
printf("\n\n Enter your choice (1-7)");
scanf("%d",&ch);
switch(ch)
{
case 1:
printf("Inserting at beginning ->");
insert_beg();
break;
case 2:
printf("Inserting at end ->");
insert_end();
break;
case 3:
printf("Inserting at i");
insert_pos();
break;
case 4:
printf("Deleting at i");
delete_pos();
break;
case 5:
printf("Displaying from beginning");
traverse_beg();
break;
case 6:
q = head;
if (q == NULL)
printf("\n Error : List empty to display ");
else
{
printf("\n Reverse order of linked list is : ");
traverse_end(q->data);
}
break;
case 7: exit(0);
default: printf("\n Wrong choice menu");
}
}
}
void create()
{
int data;
temp=(node*)malloc(sizeof(node));
printf("\n Enter value of the node: ");
scanf("%d",&data);
temp->data=data;
temp->next=NULL;
temp->prev=NULL;
count++;
}
void insert_beg()
{
if(head==NULL)
{
create();
head=temp;
}
else
{
create();
temp->next=head;
head->prev=temp;
head=temp;
}
}
void insert_end()
{
if(head == NULL)
{
create();
head=temp;
temp=tail;
}
else
{
tail=head;
while(tail->next!=NULL)
{
tail=tail->next;
}
create();
tail->next=temp;
temp->prev=tail;
tail=temp;
}
}
void insert_pos()
{
int pos,i=2;
printf("\n Enter position to be inserted : ");
scanf("%d", &pos);
q = head;
if(head == NULL && (pos == 1))
{
create();
head=temp;
tail=head;
return;
}
if((pos < 1) || (pos >= count + 1))
{
printf("\n Position out of range");
return;
}
if((head == NULL) && (pos != 1))
{
printf("\n Empty list cannot insert other than 1st position");
return;
}
else
{
while(i<pos)
{
q=q->next;
i++;
}
create();
temp->prev=q;
temp->next=q->next;
q->next=temp->prev;
q->next=temp;
}
}
void traverse_beg()
{
q=head;
if(q == NULL)
{
printf("List empty to display \n");
return;
}
printf("\n Linked list elements from beginning : ");
while(q->next!=NULL)
{
printf("%d",q->data);
q=q->next;
}
printf("%d",q->data);
}
void traverse_end(int i)
{
if(q!=NULL)
{
i=q->data;
q=q->next;
traverse_end(i);
printf("%d",i);
}
}
void delete_pos()
{
int i=1,pos;
printf("Enter position to be deleted : ");
scanf("%d",&pos);
q = head;
if((pos < 1) || (pos >= count +1))
{
printf("\n Error : Position out of range !!!!");
return;
}
if(head == NULL)
{
printf("\n Error : Empty list no elements to be deleted");
return;
}
else
{
while(i < pos)
{
q = q->next;
i++;
}
if(i == 1)
{
if(q ->next == NULL)
{
printf("\n Node deleted from the list");
free(q);
q = head = NULL;
return;
}
}
if(q->next == NULL)
{
q->prev = NULL;
q->next = NULL;
free(q);
printf("Node deleted from the list");
return;
}
free(q);
}
count--;
}Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.
Recommended Posts:
Follow programmers door for more.
Comments