English 中文(简体)
DSA using C Tutorial

Selected Reading

DSA using C - Doubly Linked List
  • 时间：2024-09-08

DSA using C - Doubly Linked List

Previous Page Next Page  

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

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

友情链接

Allggapp Allqahome-程序员问答家园 mvfinale.com-影视剧情大结局大全