1// Aim: Program to perform Double Linked List operations (Insertion, Deletion).
2#include<stdio.h>
3#include<stdlib.h>
4
5struct node {
6    int data;
7    struct node *Llink,*Rlink;
8};
9
10struct node *head = NULL;
11
12void insertfront(int x){
13    struct node *newnode = (struct node*)malloc(sizeof(struct node));
14    newnode->data = x;
15    newnode->Llink = NULL;
16    newnode->Rlink = NULL;
17    if(head == NULL){
18        head = newnode;
19    }
20    else{
21        newnode->Rlink = head;
22        head->Llink = newnode;
23        head = newnode;
24    }
25}
26
27void insertend(int x){
28    struct node *newnode = (struct node*)malloc(sizeof(struct node));
29    newnode->data = x;
30    newnode->Llink = NULL;
31    newnode->Rlink = NULL;
32    if(head == NULL){
33        head = newnode;
34    }
35    else{
36        struct node *ptr = head;
37        while(ptr->Rlink != NULL){
38            ptr = ptr->Rlink;
39        }
40        ptr->Rlink = newnode;
41        newnode->Llink = ptr;
42    }
43}
44
45void insertkey(int x,int key){
46    if(head == NULL){
47        printf("List is empty\n");
48        return;
49    }
50    struct node *ptr = head;
51    while(ptr->data != key && ptr->Rlink != NULL){
52        ptr = ptr->Rlink;
53    }
54    if(ptr->data != key){
55        printf("Key not found\n");
56    }
57    else{
58        struct node *newnode = (struct node*)malloc(sizeof(struct node));
59        newnode->data = x;
60        newnode->Llink = ptr;
61        newnode->Rlink = ptr->Rlink;
62        if(ptr->Rlink != NULL){
63            ptr->Rlink->Llink = newnode;
64        }
65        ptr->Rlink = newnode;
66    }
67}
68
69void deletefront(){
70    if(head == NULL){
71        printf("List is empty\n");
72    }
73    else if(head->Rlink == NULL){
74        struct node *temp = head;
75        head = NULL;
76        free(temp);
77    }
78    else{
79        head = head->Rlink;
80        free(head->Llink);
81        head->Llink = NULL;
82    }
83}
84
85void deleteend(){
86    if(head == NULL){
87        printf("List is empty\n");
88    }
89    else if(head->Rlink == NULL){
90        struct node *temp = head;
91        head = NULL;
92        free(temp);
93    }
94    else{
95        struct node *ptr = head;
96        while(ptr->Rlink != NULL){
97            ptr = ptr->Rlink;
98        }
99        ptr->Llink->Rlink = NULL;
100        free(ptr);
101    }
102}
103
104void deletekey(int key){
105    if(head == NULL){
106        printf("List is empty\n");
107    }
108    else if(head->Rlink == NULL){
109        if(head->data == key){
110            struct node *temp = head;
111            head = NULL;
112            free(temp);
113        }
114        else{
115            printf("Key not found\n");
116        }
117    }
118    else if(head->data == key){
119        head = head->Rlink;
120        free(head->Llink);
121        head->Llink = NULL;
122    }
123    else{
124        struct node *ptr = head;
125        while(ptr->data != key && ptr->Rlink != NULL){
126            ptr = ptr->Rlink;
127        }
128        if(ptr->data != key){
129            printf("Key not found\n");
130        }
131        else{
132            ptr->Llink->Rlink = ptr->Rlink;
133            if(ptr->Rlink != NULL){
134                ptr->Rlink->Llink = ptr->Llink;
135            }
136            free(ptr);
137        }
138    }
139}
140
141void display(){
142    if(head == NULL){
143        printf("List is empty\n");
144    }
145    else{
146        struct node *ptr = head;
147        while(ptr != NULL){
148            printf("%d ",ptr->data);
149            ptr = ptr->Rlink;
150        }
151        printf("\n");
152    }
153}
154
155void main(){
156    int ch,x,key;
157    while(1){
158        printf("1.Insert front\n2.Insert end\n3.Insert key\n4.Delete front\n5.Delete end\n6.Delete key\n7.Display\n8.Exit\n");
159        printf("Enter your choice: ");
160        scanf("%d",&ch);
161        switch(ch){
162            case 1:
163                printf("Enter the element to insert: ");
164                scanf("%d",&x);
165                insertfront(x);
166                break;
167            case 2:
168                printf("Enter the element to insert: ");
169                scanf("%d",&x);
170                insertend(x);
171                break;
172            case 3:
173                printf("Enter the element to insert: ");
174                scanf("%d",&x);
175                printf("Enter the key: ");
176                scanf("%d",&key);
177                insertkey(x,key);
178                break;
179            case 4:
180                deletefront();
181                break;
182            case 5:
183                deleteend();
184                break;
185            case 6:
186                printf("Enter the key: ");
187                scanf("%d",&key);
188                deletekey(key);
189                break;
190            case 7:
191                display();
192                break;
193            case 8:
194                exit(0);
195            default:
196                printf("Invalid choice\n");
197        }
198    }
199}