A linked list example with dynamic memory allocation, assumption that integer is the only value stored, no key. Tested with calls to each function as shown. Testing here is visual, not using any unit test logic or framework.
In the next articles of this series we will see some improvements, discussion and other versions.
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
#include <stdio.h>
#include <stdlib.h>
typedef struct node {
int val;
struct node *next;
} node_t;
typedef struct list_t {
node_t *head;
int numel;
} list_t;
list_t *list_init(void)
{
list_t *new = malloc(sizeof *new);
new->head = NULL;
new->numel = 0;
return new;
}
void list_insertAfter(list_t *list, int val, int index)
{
if (list == NULL) {
printf("Error: list is (null)\n");
return; // Can't do anything for a null list
}
if (index >= list->numel || index < -1) {
printf("Error: wrong insert index %d\n" \
"\tlast list index is %d\n", index, list->numel-1);
return;
}
node_t *new = malloc(sizeof(node_t));
new->next = NULL;
new->val = val;
list->numel++;
if (list->head == NULL || index == -1) {
list->head = new;
return;
}
node_t *i = list->head;
while (--index > -1) {
i = i->next;
}
new->next = i->next;
i->next = new;
}
int list_getAt(list_t *list, int index)
{
if (list == NULL) {
printf("Error: list is (null)\n");
return -1; // Can't do anything for a null list
}
if (index >= list->numel-1 || index < -1) {
printf("Error: wrong get index %d\n" \
"\tlast list index is %d\n", index, list->numel-1);
return -1;
}
node_t *h = list->head;
while (--index > -1) {
h = h->next;
}
return h->val;
}
int list_deleteAfter(list_t *list, int index)
{
if (list == NULL) {
printf("Error: list is (null)\n");
return -1; // Can't do anything for a null list
}
if (index >= list->numel-1 || index < -1) {
printf("Error: wrong remove index %d\n" \
"\tlast list index is %d\n", index, list->numel-1);
return -1;
}
// Actual removal procedure
node_t *h = list->head;
while (h && index-- > 0) {
h = h->next;
}
if (index == -2) {
// Remove head
list->head = h->next;
free(h);
} else {
node_t *r = h->next;
h->next = r->next;
free(r);
}
list->numel--;
return 0;
}
void list_free(list_t **list)
{
if (!(*list))
return; // Nothing to do
node_t *h = (*list)->head;
while (!h) {
node_t *n = h->next;
free(h);
h = n;
}
free(*list);
*list = NULL;
}
void printlist(list_t *list)
{
if (!list) {
printf("List is (null)\n");
return;
}
node_t *i = list->head;
while (i) {
printf("%d -> ", i->val);
i = i->next;
}
printf("END (%d elements)\n", list->numel);
}
int main(void)
{
list_t *mylist = list_init();
printlist(mylist);
// insert tests
list_insertAfter(mylist, 4, -1);
printlist(mylist);
list_insertAfter(mylist, 5, 0);
printlist(mylist);
list_insertAfter(mylist, 19, 1);
printlist(mylist);
list_insertAfter(mylist, 22, 3);
printlist(mylist);
list_insertAfter(mylist, 1, 0);
printlist(mylist);
list_insertAfter(mylist, 7, 0);
printlist(mylist);
// delete tests
list_deleteAfter(mylist, 0);
printlist(mylist);
list_deleteAfter(mylist, -1);
printlist(mylist);
list_deleteAfter(mylist, 1);
printlist(mylist);
list_insertAfter(mylist, 5, 0);
printlist(mylist);
list_insertAfter(mylist, 19, 1);
printlist(mylist);
list_insertAfter(mylist, 22, 3);
printlist(mylist);
list_insertAfter(mylist, 1, 0);
printlist(mylist);
list_insertAfter(mylist, 7, 0);
printlist(mylist);
int i;
// get tests
i = 2;
printf("element @ %d = %d\n", i, list_getAt(mylist, i));
i = 55;
printf("element @ %d = %d\n", i, list_getAt(mylist, i));
i = 4;
printf("element @ %d = %d\n", i, list_getAt(mylist, i));
// free list
list_free(&mylist);
printlist(mylist);
}