Doubly Linked List

In a 'doubly linked list', each node contains, besides the next-node link, a second link field pointing to the 'previous' node in the sequence. The two links may be called 'forward('s') and 'backwards', or 'next' and 'prev'('previous').


Implementation of doubly linked list


Code:
 
#include <stdio.h>
#include "stdlib.h"
 
struct node{
                int num;
                struct node *next;
                struct node *prev;
}*head, *tail;
 
int sizeoflist;
 
void Display(){
               
                if(head == NULL){
                                printf("\nLinked List is empty!!");
                                return;
                }
                struct node *ptr = head;
                printf("\n-----------Displaying linked list-----------\n");
                printf("\nHead->");
                while(ptr!=NULL){
                                printf("%d -> ", ptr->num);
                                ptr = ptr->next;
                }
                printf("Tail");
}
 
/*adding element at the end of the linked list*/
void Add_at_tail(){
                struct node *ptr = (struct node*)malloc(sizeof(struct node));
                printf("\nEnter value to be added at the end of the list: ");
                scanf("%d", &ptr->num);
                ptr->next = NULL;
                ptr->prev = NULL;
               
                if(tail == NULL){
                                /*Linked list is not formed. Add first element to the linked list*/
                                head = ptr;
                                tail = ptr;
                }
                else{
                                /*add element at the end of the linked list*/
                                tail->next = ptr;
                                ptr->prev = tail;
                                tail = ptr;
                }
               
                printf("\n%d is added at the tail..", ptr->num);
                sizeoflist++;
}
 
/*adding element at the beginning of the linked list*/
void Add_at_head(){
                struct node *ptr = (struct node*)malloc(sizeof(struct node));
                printf("\nEnter value to be added at the beginning of the list: ");
                scanf("%d", &ptr->num);
                ptr->next = NULL;
                ptr->prev = NULL;
               
                if(head == NULL){
                                /*Linked list is not formed. Add first element to the linked list*/
                                head = ptr;
                                tail = ptr;
                }
                else{
                                /*add element at the end of the linked list*/
                                ptr->next = head;
                                head->prev = ptr;
                                head = ptr;
                }
               
                printf("\n%d is added at the head..", ptr->num);
                sizeoflist++;
}
 
 
/*adding element at the nth position of the linked list*/
/*Linked list position starts from 1*/
void Add_at_nth_position(){
               
                int position = 0;
               
                printf("\nEnter the position where you want to add element in the list: ");
                scanf("%d", &position);
               
                if(position <= 1 || position >= sizeoflist){
                                printf("\nINVALID POSITION!! Position should be strictly in between 1 and %d", sizeoflist);
                                return;
                }
 
                /*position is in between 1 and sizeoflist*/          
                struct node *ptr = (struct node*)malloc(sizeof(struct node));
                printf("\nEnter value to be added at the %d-th position of the list: ", position);
                scanf("%d", &ptr->num);
                ptr->next = NULL;
                ptr->prev = NULL;
               
                /*find position*/
                struct node *prevnode = NULL, *temp = head;
                int curloc = 1;
                while(temp != NULL && curloc != position){
                                prevnode = temp;
                                temp = temp->next;
                                curloc++;
                }
               
                /*we need to add ptr in between prevnode and temp*/
                prevnode->next = ptr;
                ptr->prev = prevnode;
                ptr->next = temp;
                temp->prev = ptr;
               
                printf("\n%d is added at %d-th position in the linked list..", ptr->num, position);
                sizeoflist++;
}
 
/*deleting tail of the linked list*/
void Delete_from_tail(){
                struct node *temp = head, *prevnode = NULL;
               
                if(head == NULL){
                                printf("\nLinked List is empty!!");
                                return;
                }
                else if(sizeoflist == 1){
                                /*only one element in the linked list*/
                                printf("\n%d is deleted from the linked list from tail position", tail->num);
                                free(tail);
                                head = NULL;
                                tail = NULL;
                }
                else{
                                /*multiple elements in linked list*/
                                prevnode = tail->prev;
                                printf("\n%d is deleted from the linked list from tail position", tail->num);           
                                free(tail);
                                tail = prevnode;
                                tail->next = NULL;
                }             
                sizeoflist--;
}
 
/*deleting head of the linked list*/
void Delete_from_head(){
                struct node *temp = NULL;
               
                if(head == NULL){
                                printf("Linked List is empty!!");
                                return;
                }
                else if(sizeoflist == 1){
                                /*only one element in the linked list*/
                                printf("\n%d is deleted from the linked list from head position", head->num);
                                free(head);
                                head = NULL;
                                tail = NULL;
                }
                else{
                                /*multiple elements in linked list*/
                                printf("\n%d is deleted from the linked list from head position", head->num);
                                temp = head->next;
                                free(head);
                                head = temp;
                                head->prev = NULL;
                }
                sizeoflist--;
}
 
/*deleting element from the nth position of the linked list*/
/*Linked list position starts from 1*/
void Delete_from_nth_position(){
               
                int position = 0;
               
                printf("\nEnter the position from where you want to delete element in the list: ");
                scanf("%d", &position);
               
                if(head == NULL){
                                printf("Linked List is empty!!");
                                return;
                }
                else if(position <= 1 || position >= sizeoflist){
                                printf("\nINVALID POSITION!! Position should be strictly in between 1 and %d", sizeoflist);
                                return;
                }
 
                /*position is in between 1 and sizeoflist*/          
                /*find position*/
                struct node *prevnode = NULL, *temp = head, *tmp = NULL;
                int curloc = 1;
                while(temp!=NULL && curloc != position){
                                prevnode = temp;
                                temp = temp->next;
                                curloc++;
                }
               
                /*we need to delete temp and point prevnode to temp->next*/
                tmp = temp->next;
                prevnode->next = tmp;
                tmp->prev = prevnode;
                printf("\n%d is deleted from %d-th position from the linked list", temp->num, position);
                free(temp);
                temp = NULL;
               
                sizeoflist--;
 
}
 
void main(){
               
                int option;
                char con, c;
               
                do{
                                do{
                                                printf("\n\nWhat do you want to do?");
                                                printf("\n1. Add to head\n2. Add to tail\n3. Add at nth position\n4. Delete head");
                                                printf("\n5. Delete tail\n6. Delete at nth position\n7. Display\n8. Exit\nOption : ");
                                                scanf("%d", &option);
                                               
                                                switch(option){
                                                                case 1:
                                                                                Add_at_head();
                                                                                break;
                                                                case 2:
                                                                                Add_at_tail();
                                                                                break;
                                                                case 3:
                                                                                Add_at_nth_position();
                                                                                break;
                                                                case 4:
                                                                                Delete_from_head();
                                                                                break;
                                                                case 5:
                                                                                Delete_from_tail();
                                                                                break;
                                                                case 6:
                                                                                Delete_from_nth_position();
                                                                                break;
                                                                case 7:
                                                                                Display();
                                                                                break;
                                                                case 8:
                                                                                goto exit;
                                                                                break;
                                                                default:
                                                                                break;  
                                                }
                                               
                                }while(1);
                               
                                exit:
                                               
                                printf("\nDo you want to continue (y/n) ?:");
                                getchar();
                                con = getchar();
                }while(con == 'y' || con == 'Y');
}
 
 
Output:
 
What do you want to do?
1. Add to head
2. Add to tail
3. Add at nth position
4. Delete head
5. Delete tail
6. Delete at nth position
7. Display
8. Exit
Option : 1
 
Enter value to be added at the beginning of the list: 12
 
12 is added at the head..
 
What do you want to do?
1. Add to head
2. Add to tail
3. Add at nth position
4. Delete head
5. Delete tail
6. Delete at nth position
7. Display
8. Exit
Option : 2
 
Enter value to be added at the end of the list: 23
 
23 is added at the tail..
 
What do you want to do?
1. Add to head
2. Add to tail
3. Add at nth position
4. Delete head
5. Delete tail
6. Delete at nth position
7. Display
8. Exit
Option : 1
 
Enter value to be added at the beginning of the list: 34
 
34 is added at the head..
 
What do you want to do?
1. Add to head
2. Add to tail
3. Add at nth position
4. Delete head
5. Delete tail
6. Delete at nth position
7. Display
8. Exit
Option : 2
 
Enter value to be added at the end of the list: 45
 
45 is added at the tail..
 
What do you want to do?
1. Add to head
2. Add to tail
3. Add at nth position
4. Delete head
5. Delete tail
6. Delete at nth position
7. Display
8. Exit
Option : 1
 
Enter value to be added at the beginning of the list: 56
 
56 is added at the head..
 
What do you want to do?
1. Add to head
2. Add to tail
3. Add at nth position
4. Delete head
5. Delete tail
6. Delete at nth position
7. Display
8. Exit
Option : 7
 
-----------Displaying linked list-----------
 
Head->56 -> 34 -> 12 -> 23 -> 45 -> Tail
 
What do you want to do?
1. Add to head
2. Add to tail
3. Add at nth position
4. Delete head
5. Delete tail
6. Delete at nth position
7. Display
8. Exit
Option : 3
 
Enter the position where you want to add element in the list: 1
 
INVALID POSITION!! Position should be strictly in between 1 and 5
 
What do you want to do?
1. Add to head
2. Add to tail
3. Add at nth position
4. Delete head
5. Delete tail
6. Delete at nth position
7. Display
8. Exit
Option : 3
 
Enter the position where you want to add element in the list: 5
 
INVALID POSITION!! Position should be strictly in between 1 and 5
 
What do you want to do?
1. Add to head
2. Add to tail
3. Add at nth position
4. Delete head
5. Delete tail
6. Delete at nth position
7. Display
8. Exit
Option : 3
 
Enter the position where you want to add element in the list: 3
 
Enter value to be added at the 3-th position of the list: 55
 
55 is added at 3-th position in the linked list..
 
What do you want to do?
1. Add to head
2. Add to tail
3. Add at nth position
4. Delete head
5. Delete tail
6. Delete at nth position
7. Display
8. Exit
Option : 7
 
-----------Displaying linked list-----------
 
Head->56 -> 34 -> 55 -> 12 -> 23 -> 45 -> Tail
 
What do you want to do?
1. Add to head
2. Add to tail
3. Add at nth position
4. Delete head
5. Delete tail
6. Delete at nth position
7. Display
8. Exit
Option : 4
 
56 is deleted from the linked list from head position
 
What do you want to do?
1. Add to head
2. Add to tail
3. Add at nth position
4. Delete head
5. Delete tail
6. Delete at nth position
7. Display
8. Exit
Option : 5
 
45 is deleted from the linked list from tail position
 
What do you want to do?
1. Add to head
2. Add to tail
3. Add at nth position
4. Delete head
5. Delete tail
6. Delete at nth position
7. Display
8. Exit
Option : 7
 
-----------Displaying linked list-----------
 
Head->34 -> 55 -> 12 -> 23 -> Tail
 
What do you want to do?
1. Add to head
2. Add to tail
3. Add at nth position
4. Delete head
5. Delete tail
6. Delete at nth position
7. Display
8. Exit
Option : 6
 
Enter the position from where you want to delete element in the list: 1
 
INVALID POSITION!! Position should be strictly in between 1 and 4
 
What do you want to do?
1. Add to head
2. Add to tail
3. Add at nth position
4. Delete head
5. Delete tail
6. Delete at nth position
7. Display
8. Exit
Option : 6
 
Enter the position from where you want to delete element in the list: 4
 
INVALID POSITION!! Position should be strictly in between 1 and 4
 
What do you want to do?
1. Add to head
2. Add to tail
3. Add at nth position
4. Delete head
5. Delete tail
6. Delete at nth position
7. Display
8. Exit
Option : 6
 
Enter the position from where you want to delete element in the list: 3
 
12 is deleted from 3-th position from the linked list
 
What do you want to do?
1. Add to head
2. Add to tail
3. Add at nth position
4. Delete head
5. Delete tail
6. Delete at nth position
7. Display
8. Exit
Option : 7
 
-----------Displaying linked list-----------
 
Head->34 -> 55 -> 23 -> Tail
 
What do you want to do?
1. Add to head
2. Add to tail
3. Add at nth position
4. Delete head
5. Delete tail
6. Delete at nth position
7. Display
8. Exit
Option : 8
 
Do you want to continue (y/n) ?:n

No comments :

Post a Comment