-
Notifications
You must be signed in to change notification settings - Fork 3
/
linkedlist_pure.c
282 lines (249 loc) · 7.63 KB
/
linkedlist_pure.c
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
#include <stdio.h>
#include <stdlib.h>
//created by prathwik0
//feel free to modify or use this program in any way you desire
//
//In this linked list program, we define a custom datatype called data
//data is a structure which can have anything inside e.g. student details
//Currently data is a structure consisting of a just single integer named value
//The benefit of using this approach is that we wouldn't need to
//change the linked list program even if we change the data definition
//
//user of this program can change the code accordingly to use whatever data they prefer
//they would also change the following functions accordingly
//
// data getdata() -- this function asks the user for the data and returns it
// data getnull() -- this function is similar to the previous one but it returns data initialized as 0 or null
//
// void insertdata(data *d, data x) -- this function copies the data x to the location indicated by the pointer *d
// int datacmp(data x, data y) -- returns 1 if x and y are identical, else returns 0
// void printdata(data d) -- prints the data
//the following structure defines data
typedef struct
{
int value;
}data;
//this asks the user to input the data and return it
data getdata()
{
data d;
printf("Enter data : ");
scanf("%d", &d.value);
return d;
}
//this returns the data with all values set to null or zero
data getnull()
{
data d;
d.value = 0;
return d;
}
//this inserts the data x into location indicated by data pointer d
void insertdata(data *d, data x)
{
d->value = x.value;
}
//this function should return 1 if the given inputs are identical
//else return 0
int datacmp(data x, data y)
{
if (x.value == y.value)
{
return 1;
}
else
{
return 0;
}
}
//this prints the data as required
void printdata(data d)
{
printf("%d ", d.value);
}
//----------------------------------------------------------------------//
//below, linked list is implemented for the data (which was defined above)
// this defines node to be a pointer to a structure NODE which consists of data d and pointer to the next NODE
// note the following is defined opposite of the convention where NODE is the pointer and node is the structure
// here node represents the pointer and NODE represents the structure
typedef struct NODE
{
data d;
struct NODE *next;
}*node;
//this function allocates a NODE from heap to the node pointer *n
//note *n is a pointer to a pointer to the structure NODE
//this is how this function should be called : getnode(&n); where n is a pointer to NODE
void getnode(node *n)
{
*n = (struct NODE *)malloc(sizeof(struct NODE));
}
//this function prints each element of the linked list
//if there are no elements, it prints: no elements present
void display(node n);
//these are the functions that can be used adding a node to the linked list
//insert function inserts the element at the specified position pos
//if pos is negative it inserts at the end
//
//insertfront and insertend are selfexplanatory
void insert(node *n, int pos, data x);
void insertfront(node *n, data x);
void insertend(node *n, data x);
//these are the functions that can be used to delete a node in the linked list
//delete function deletes the element at the specified position pos and returns the deleted data
//if pos is negative the last element is deleted
//
//if there are no elements in the linked list, function returns data with all values set to NULL or zero
//
//deletevalue function deletes all instances of the input data x if it is present in the linked list
//it returns a count of number of elements deleted
//if there is not match, it doen't delete anything and returns a count of zero
data delete(node *n, int pos);
int deletevalue(node *n, data x);
//the following is the main function
int main()
{
//this is an implementation linked list
node a = NULL;
while (1)
{
int n;
printf("1 - insert, 2 - display, 3 - delete : ");
scanf("%d", &n);
if (n == 1)
{
data d = getdata();
//use the following to insert at the front
//insertfront(&a, d);
//use the following to insert at the end
//insertback(&a, d);
//use the following to insert in user input position
//for insert at front input pos = 0
//for end input pos = negative (or pos exceeds number of elements in the list)
int pos;
printf("Enter position : ");
scanf("%d", &pos);
printf("\n");
insert(&a, pos, d);
}
else if (n == 2)
{
display(a);
}
else if (n == 3)
{
//use the following to delete user input value(s) from the list
data d = getdata();
printf("%d elements deleted\n", deletevalue(&a, d));
//use the following to delete from the front
//delete(&a, 0);
//use the following to delete from the end
//delete(&a, -1);
//use the following to delete from user input position
//for delete at front input pos = 0
//for end input pos = negative (or pos exceeds number of elements in the list)
/* int pos;
printf("Enter position : ");
scanf("%d", &pos);
printf("\n");
delete(&a, pos);*/
}
else
{
return 0;
}
}
}
// NOTE: all the following functions other than display take node *n as one of the inputs
// be careful while using node *n
//
// inside the function n represents the local variable
// all changes to n affects only the local variable n, the linked list will not be affected
//
// **********************************************************************************
// but *n is not a local variable, all changes made to *n will modify the linked list
// **********************************************************************************
void insert(node *n, int pos, data x)
{
//if position is neg or exceeds the num of elements in list, insert end
while(*n != NULL && pos != 0)
{
n = &((*n)->next);
pos--;
}
node temp = *n;
getnode(n);
insertdata(&((*n)->d) ,x);
(*n)->next = temp;
}
void insertfront(node *n, data x)
{
node temp = *n;
getnode(n);
insertdata(&((*n)->d) ,x);
(*n)->next = temp;
}
void insertend(node *n, data x)
{
while(*n != NULL)
n = &((*n)->next);
node temp = *n;
getnode(n);
insertdata(&((*n)->d) ,x);
(*n)->next = temp;
}
void display(node n)
{
//this prints a message for empty linked-list
if(n == NULL)
{
printf("no elements present");
}
while(n != NULL)
{
printf("-> ");
printdata(n->d);
n = n->next;
}
printf("\n\n");
}
data delete(node *n, int pos)
{
//this checks for list empty condition
if(*n == NULL)
{
//the list is empty, cant delete
data d = getnull();
return d;
}
//if position is neg or exceeds the num of elements in list, deletes the last node
while ((*n)->next != NULL && pos != 0)
{
n = &((*n)->next);
pos--;
}
node temp = *n;
data temp2 = temp->d;
*n = (*n)->next;
free(temp);
return temp2;
}
int deletevalue(node *n, data x)
{
int count = 0;
while(*n != NULL)
{
if (datacmp(x, (*n)->d))
{
node temp = *n;
*n = (*n)->next;
free(temp);
count++;
}
else
{
n = &((*n)->next);
}
}
return count;
}