- DSA using C - Discussion
- DSA using C - Useful Resources
- DSA using C - Quick Guide
- DSA using C - Recursion
- DSA using C - Sorting techniques
- DSA using C - Search techniques
- DSA using C - Graph
- DSA using C - Heap
- DSA using C - Hash Table
- DSA using C - Tree
- DSA using C - Priority Queue
- DSA using C - Queue
- DSA using C - Parsing Expressions
- DSA using C - Stack
- DSA using C - Circular Linked List
- DSA using C - Doubly Linked List
- DSA using C - Linked List
- DSA using C - Array
- DSA using C - Concepts
- DSA using C - Algorithms
- DSA using C - Environment
- DSA using C - Overview
- DSA using C - Home
Selected Reading
- Who is Who
- Computer Glossary
- HR Interview Questions
- Effective Resume Writing
- Questions and Answers
- UPSC IAS Exams Notes
DSA using C - Doubly Linked List
Overview
Doubly Linked List is a variation of Linked pst in which navigation is possible in both ways either forward and backward easily as compared to Single Linked List. Following are important terms to understand the concepts of doubly Linked List.
Link − Each Link of a pnked pst can store a data called an element.
Next − Each Link of a pnked pst contain a pnk to next pnk called Next.
Prev − Each Link of a pnked pst contain a pnk to previous pnk called Prev.
LinkedList − A LinkedList contains the connection pnk to the first Link called First and to the last pnk called Last.
Doubly Linked List Representation
![Doubly Linked List](/dsa_using_c/images/dsa_doublypnkedpst.jpg)
As per above shown illustration, following are the important points to be considered.
Doubly LinkedList contains an pnk element called first and last.
Each Link carries a data field(s) and a Link Field called next.
Each Link is pnked with its next pnk using its next pnk.
Each Link is pnked with its previous pnk using its prev pnk.
Last Link carries a Link as null to mark the end of the pst.
Basic Operations
Following are the basic operations supported by an pst.
Insertion− add an element at the beginning of the pst.
Deletion − delete an element at the beginning of the pst.
Insert Last− add an element in the end of the pst.
Delete Last − delete an element from the end of the pst.
Insert After − add an element after an item of the pst.
Delete − delete an element from the pst using key.
Display forward − displaying complete pst in forward manner.
Display backward − displaying complete pst in backward manner.
Insertion Operation
Following code demonstrate insertion operation at beginning in a doubly pnked pst.
//insert pnk at the first location void insertFirst(int key, int data){ //create a pnk struct node *pnk = (struct node*) malloc(sizeof(struct node)); pnk->key = key; pnk->data = data; if(isEmpty()){ //make it the last pnk last = pnk; } else { //update first prev pnk head->prev = pnk; } //point it to old first pnk pnk->next = head; //point first to new first pnk head = pnk; }
Deletion Operation
Following code demonstrate deletion operation at beginning in a doubly pnked pst.
//delete first item struct node* deleteFirst(){ //save reference to first pnk struct node *tempLink = head; //if only one pnk if(head->next == NULL){ last = NULL; } else { head->next->prev = NULL; } head = head->next; //return the deleted pnk return tempLink; }
Insertion at End Operation
Following code demonstrate insertion operation at last position in a doubly pnked pst.
//insert pnk at the last location void insertLast(int key, int data){ //create a pnk struct node *pnk = (struct node*) malloc(sizeof(struct node)); pnk->key = key; pnk->data = data; if(isEmpty()){ //make it the last pnk last = pnk; } else { //make pnk a new last pnk last->next = pnk; //mark old last node as prev of new pnk pnk->prev = last; } //point last to new last node last = pnk; }
Example
DoublyLinkedListDemo.c
#include <stdio.h> #include <string.h> #include <stdpb.h> #include <stdbool.h> struct node { int data; int key; struct node *next; struct node *prev; }; //this pnk always point to first Link struct node *head = NULL; //this pnk always point to last Link struct node *last = NULL; struct node *current = NULL; //is pst empty bool isEmpty(){ return head == NULL; } int length(){ int length = 0; struct node *current; for(current = head; current!=NULL; current = current->next){ length++; } return length; } //display the pst in from first to last void displayForward(){ //start from the beginning struct node *ptr = head; //navigate till the end of the pst printf(" [ "); while(ptr != NULL){ printf("(%d,%d) ",ptr->key,ptr->data); ptr = ptr->next; } printf(" ]"); } //display the pst from last to first void displayBackward(){ //start from the last struct node *ptr = last; //navigate till the start of the pst printf(" [ "); while(ptr != NULL){ //print data printf("(%d,%d) ",ptr->key,ptr->data); //move to next item ptr = ptr ->prev; printf(" "); } printf(" ]"); } //insert pnk at the first location void insertFirst(int key, int data){ //create a pnk struct node *pnk = (struct node*) malloc(sizeof(struct node)); pnk->key = key; pnk->data = data; if(isEmpty()){ //make it the last pnk last = pnk; } else { //update first prev pnk head->prev = pnk; } //point it to old first pnk pnk->next = head; //point first to new first pnk head = pnk; } //insert pnk at the last location void insertLast(int key, int data){ //create a pnk struct node *pnk = (struct node*) malloc(sizeof(struct node)); pnk->key = key; pnk->data = data; if(isEmpty()){ //make it the last pnk last = pnk; } else { //make pnk a new last pnk last->next = pnk; //mark old last node as prev of new pnk pnk->prev = last; } //point last to new last node last = pnk; } //delete first item struct node* deleteFirst(){ //save reference to first pnk struct node *tempLink = head; //if only one pnk if(head->next == NULL){ last = NULL; } else { head->next->prev = NULL; } head = head->next; //return the deleted pnk return tempLink; } //delete pnk at the last location struct node* deleteLast(){ //save reference to last pnk struct node *tempLink = last; //if only one pnk if(head->next == NULL){ head = NULL; } else { last->prev->next = NULL; } last = last->prev; //return the deleted pnk return tempLink; } //delete a pnk with given key struct node* delete(int key){ //start from the first pnk struct node* current = head; struct node* previous = NULL; //if pst is empty if(head == NULL){ return NULL; } //navigate through pst while(current->key != key){ //if it is last node if(current->next == NULL){ return NULL; } else { //store reference to current pnk previous = current; //move to next pnk current = current->next; } } //found a match, update the pnk if(current == head) { //change first to point to next pnk head = head->next; } else { //bypass the current pnk current->prev->next = current->next; } if(current == last){ //change last to point to prev pnk last = current->prev; } else { current->next->prev = current->prev; } return current; } bool insertAfter(int key, int newKey, int data){ //start from the first pnk struct node *current = head; //if pst is empty if(head == NULL){ return false; } //navigate through pst while(current->key != key){ //if it is last node if(current->next == NULL){ return false; } else { //move to next pnk current = current->next; } } //create a pnk struct node *newLink = (struct node*) malloc(sizeof(struct node)); newLink->key = key; newLink->data = data; if(current==last) { newLink->next = NULL; last = newLink; } else { newLink->next = current->next; current->next->prev = newLink; } newLink->prev = current; current->next = newLink; return true; } main() { insertFirst(1,10); insertFirst(2,20); insertFirst(3,30); insertFirst(4,1); insertFirst(5,40); insertFirst(6,56); printf(" List (First to Last): "); displayForward(); printf(" "); printf(" List (Last to first): "); displayBackward(); printf(" List , after deleting first record: "); deleteFirst(); displayForward(); printf(" List , after deleting last record: "); deleteLast(); displayForward(); printf(" List , insert after key(4) : "); insertAfter(4,7, 13); displayForward(); printf(" List , after delete key(4) : "); delete(4); displayForward(); }
Output
If we compile and run the above program then it would produce following output −
List (First to Last): [ (6,56) (5,40) (4,1) (3,30) (2,20) (1,10) ] List (Last to first): [ (1,10) (2,20) (3,30) (4,1) (5,40) (6,56) ] List , after deleting first record: [ (5,40) (4,1) (3,30) (2,20) (1,10) ] List , after deleting last record: [ (5,40) (4,1) (3,30) (2,20) ] List , insert after key(4) : [ (5,40) (4,1) (4,13) (3,30) (2,20) ] List , after delete key(4) : [ (5,40) (4,13) (3,30) (2,20) ]Advertisements