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