blob: 7c0706b21798b155481a52ea4d47554f22787c69 (
plain)
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
|
#include <stdio.h>
#include <stdlib.h>
#include "linked_list.h"
int count_ll(struct node* ptr){
/*
Count the number of nodes in a linked list.
*/
int count = 0;
while (ptr != NULL){
count++;
ptr = ptr->next;
}
return count;
}
struct node* init_ll(int value){
// can make this create node
// and then let other function call this
// since this is a repeated function in prepend append
struct node* ptr = malloc(sizeof(struct node));
ptr->value = value;
ptr->next = NULL;
return ptr;
}
void prepend_ll(struct node **ptr, int value){
/*
Add a node to the front of the linked list
Push
*/
struct node* new = malloc(sizeof(struct node));
new->value = value;
new->next = *ptr;
*ptr = new;
}
void append_ll(struct node* ptr, int value){
/*
Add a node to the end of the linked list
*/
struct node* new = malloc(sizeof(struct node));
while (ptr->next != NULL){
ptr = ptr->next;
}
new->value = value;
new->next = NULL;
ptr->next = new;
}
void print_ll(struct node* ptr){
/*
Print out the linked list
*/
while (ptr != NULL){
printf("%d", ptr->value);
ptr = ptr->next;
if (ptr == NULL){
break;
}
printf(" - ");
}
printf("\n");
}
void free_ll(struct node* ptr){
/*
Safely free all nodes inside linked list.
*/
if (ptr == NULL){
// if head is NULL then the list must be empty
// no memory to free
return;
}
struct node* next;
while (ptr->next != NULL){
next = ptr->next;
free(ptr);
ptr = next;
}
}
int update_node(struct node* ptr, int index, int value){
/*
Update value of a node inside linked list
*/
// TODO:: What if the index is out of range?
if (index >= count_ll(ptr)){
// index out of range
return 1;
}
int count = 0;
while (count < index){
ptr = ptr->next;
count++;
}
ptr->value = value;
return 0;
}
int delete_node(struct node **ptr, int index){
/*
Delete a node given the index
*/
// TODO:: What if the node doesn't exist?
struct node* prev;
if (index == 0){
prev = *ptr;
*ptr = (*ptr)->next;
free(prev);
return 0;
}
struct node* root = *ptr;
for (int i = 0; i <= index; i++){
if (i == index){
prev->next = root->next;
free(root);
return 0;
}
prev = root;
root = root->next;
}
printf("Node not found\n");
exit(-1);
}
int get_value(struct node *ptr, int index){
/*
Get the value of a specific node given the index
*/
// TODO:: What if the index is out of range??
for (int i = 0; i < index; i++){
ptr = ptr->next;
}
return ptr->value;
}
struct node* search_node(struct node *ptr, int value){
/*
Search for a node given the value and returns it
*/
while (1){
if (ptr == NULL){
fprintf(stderr, "Value doesn't exitst in linked list\n");
exit(-1);
}
if (ptr->value == value){
break;
}
ptr = ptr->next;
}
return ptr;
}
void reverse_ll(struct node** ptr){
struct node *prev, *cur, *next;
int n = count_ll(*ptr);
if (n == 0){
return;
}
if (n == 1){
return;
}
prev = *ptr;
cur = prev->next;
next = cur->next;
prev->next = NULL;
cur->next = prev;
for (int i = 0; i < n-2; i++){
prev = cur;
cur = next;
next = next->next;
cur->next = prev;
}
*ptr = cur;
}
|
