Mercurial > LinkedList

view src/LinkedList.c @ 0:5db060528d2b

find changesets by author, revision, files, or words in the commit message
Initial import
author Eris Caffee <discordia@eldalin.com>
date Wed, 29 Dec 2010 02:14:35 -0600
parents
children c6e339846527
line source
1 /*******************************************************************************
2 * LinkedList
3 *
4 * A simple doubly linked list class in C.
5 *
6 * Not thread safe.
7 *
8 ******************************************************************************/
9
10 #include "LinkedList.h"
11
12 #include <stdlib.h>
13
14 /*******************************************************************************
15 * "Private" inner class.
16 */
17 struct ll_node
18 {
19 ll_node * next;
20 ll_node * prev;
21 void * data;
22 };
23
24
25 /*******************************************************************************
26 * Insert an element at end of list.
27 * Sets curr and tail pointers to the new node.
28 * Returns data on success, NULL on error.
29 */
30 void * ll_push(LinkedList * this, void * data)
31 {
32 ll_node * new_node;
33
34 if ((!this) || (!data))
35 return NULL;
36
37 if (!(new_node = calloc(1, sizeof(ll_node))))
38 return NULL;
39
40 new_node->data = data;
41
42 if (!(this->Tail))
43 {
44 /* empty list */
45 this->Head = this->Tail = this->Curr = new_node;
46 }
47 else
48 {
49 new_node->prev = this->Tail;
50 this->Tail->next = new_node;
51 this->Tail = this->Curr = new_node;
52 }
53
54 this->Size++;
55 return this->Curr->data;
56 }
57
58
59 /*******************************************************************************
60 * Insert an element after the one pointed to by this->curr.
61 * Sets curr pointer to the new node (and tail if curr = tail when called).
62 * Returns data on success, NULL on error.
63 */
64 void * ll_insert(LinkedList * this, void * data)
65 {
66 ll_node * new_node;
67
68 if ((!this) || (!data))
69 return NULL;
70
71 if (this->Curr == this->Tail)
72 {
73 return ll_push(this, data);
74 }
75
76 if (!(new_node = calloc(1, sizeof(ll_node))))
77 return NULL;
78
79 new_node->data = data;
80 new_node->prev = this->Curr;
81 new_node->next = this->Curr->next;
82 this->Curr->next = new_node;
83 new_node->next->prev = new_node;
84 this->Curr = new_node;
85
86 this->Size++;
87 return this->Curr->data;
88 }
89
90
91 /*******************************************************************************
92 * Insert an element and make it the new head.
93 * Sets head and curr pointers to the new node.
94 * Returns data on success, NULL on error.
95 */
96 void * ll_insert_at_head(LinkedList * this, void * data)
97 {
98 ll_node * new_node;
99
100 if ((!this) || (!data))
101 return NULL;
102
103 if (!(new_node = calloc(1, sizeof(ll_node))))
104 return NULL;
105
106 new_node->data = data;
107 new_node->prev = NULL;
108 new_node->next = this->Head;;
109
110 if (this->Head)
111 this->Head->prev = new_node;
112 this->Head = this->Curr = new_node;
113
114 this->Size++;
115 return this->Curr->data;
116 }
117
118
119 /*******************************************************************************
120 * Remove the tail element from the list.
121 * Sets curr to tail.
122 * Return data, or NULL if the list is empty.
123 */
124 void * ll_pop(LinkedList * this)
125 {
126 void * data;
127 ll_node * tmp;
128
129 if (!this)
130 return NULL;
131
132 if (!(this->Tail))
133 return NULL;
134
135 tmp = this->Tail;
136 data = this->Tail->data;
137
138 if (!(this->Tail->prev))
139 {
140 /* Only element in list */
141 this->Head = this->Tail = this->Curr = NULL;
142 }
143 else
144 {
145 this->Tail->prev->next = NULL;
146 this->Tail = this->Curr = this->Tail->prev;
147 }
148
149 free(tmp);
150 this->Size--;
151
152 return data;
153 }
154
155
156 /*******************************************************************************
157 * Delete the element pointed to by this->curr.
158 * A pointer to the stored data is returned, or NULL is no list or an empty list
159 * is specified. It must be freed by the caller.
160 */
161 void * ll_remove(LinkedList * this)
162 {
163 void * data;
164 ll_node * tmp;
165
166 if (!this)
167 return NULL;
168
169 if (this->Curr == this->Tail)
170 return ll_pop(this);
171
172 tmp = this->Curr;
173 data = this->Curr->data;
174
175 if (this->Curr == this->Head)
176 {
177 this->Curr->next->prev = NULL;
178 this->Head = this->Curr = this->Head->next;
179 }
180 else
181 {
182 this->Curr->prev->next = this->Curr->next;
183 this->Curr->next->prev = this->Curr->prev;
184 }
185
186 free(tmp);
187 this->Size--;
188
189 return data;
190 }
191
192
193 /*******************************************************************************
194 * Return the size of the list, or -1 is list is null.
195 */
196 int ll_size(LinkedList * this)
197 {
198 if (!this) return -1;
199
200 return this->Size;
201 }
202
203
204 /*******************************************************************************
205 * Select the first element in the list if there is one.
206 * Return data pointer of new current element, or NULL is list is empty.
207 */
208 void * ll_head(LinkedList * this)
209 {
210 if (!this) return NULL;
211
212 this->Curr = this->Head;
213
214 if (this->Curr)
215 return this->Curr->data;
216 else
217 return NULL;
218 }
219
220
221 /*******************************************************************************
222 * Select the last element in the list if there is one.
223 * Return data pointer of new current element, or NULL is list is empty.
224 */
225 void * ll_tail(LinkedList * this)
226 {
227 if (!this) return NULL;
228
229 this->Curr = this->Tail;
230
231 if (this->Curr)
232 return this->Curr->data;
233 else
234 return NULL;
235 }
236
237
238 /*******************************************************************************
239 * Select the next element in the list if there is one.
240 * Return data pointer of new current element, or NULL is list is empty.
241 */
242 void * ll_next(LinkedList * this)
243 {
244 if (!this) return NULL;
245
246 if (this->Curr->next)
247 this->Curr = this->Curr->next;
248
249 if (this->Curr)
250 return this->Curr->data;
251 else
252 return NULL;
253 }
254
255
256 /*******************************************************************************
257 * Select previous element in the list if there is one.
258 * Return data pointer of new current element, or NULL is list is empty.
259 */
260 void * ll_prev(LinkedList * this)
261 {
262 if (!this) return NULL;
263
264 if (this->Curr->prev)
265 this->Curr = this->Curr->prev;
266
267 if (this->Curr)
268 return this->Curr->data;
269 else
270 return NULL;
271 }
272
273
274 /*******************************************************************************
275 * Return the data pointer of the current node, or NULL is list is empty.
276 */
277 void * ll_data(LinkedList * this)
278 {
279 if (!this) return NULL;
280
281 if (this->Curr)
282 return this->Curr->data;
283 else
284 return NULL;
285 }
286
287
288 /*******************************************************************************
289 * Constuctor. Call this when creating a new list.
290 */
291 void ll_init(LinkedList * this)
292 {
293 if (this)
294 {
295 this->push = ll_push;
296 this->pop = ll_pop;
297 this->insert = ll_insert;
298 this->remove = ll_remove;
299 this->insert_at_head = ll_insert_at_head;
300 this->size = ll_size;
301 this->head = ll_head;
302 this->tail = ll_tail;
303 this->next = ll_next;
304 this->prev = ll_prev;
305 this->data = ll_data;
306
307 this->Head = this->Tail = this->Curr = NULL;
308 this->Size = 0;
309 }
310 }
311
312