Mercurial > LinkedList

view src/LinkedList.c @ 3:34f1d2f54d37

find changesets by author, revision, files, or words in the commit message
cleanup
author Eris Caffee <discordia@eldalin.com>
date Tue, 10 May 2011 19:48:12 -0500
parents c6e339846527
children c9e6f5c0a9b2
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 at end of list or list is empty or list has only one element */
72 if (this->Curr == this->Tail)
73 {
74 return ll_push(this, data);
75 }
76
77 if (!(new_node = calloc(1, sizeof(ll_node))))
78 return NULL;
79
80 new_node->data = data;
81 new_node->prev = this->Curr;
82 new_node->next = this->Curr->next;
83 this->Curr->next = new_node;
84 new_node->next->prev = new_node;
85 this->Curr = new_node;
86
87 this->Size++;
88 return this->Curr->data;
89 }
90
91
92 /*******************************************************************************
93 * Insert an element and make it the new head.
94 * Sets head and curr pointers to the new node.
95 * Returns data on success, NULL on error.
96 */
97 void * ll_insert_at_head(LinkedList * this, void * data)
98 {
99 ll_node * new_node;
100
101 if ((!this) || (!data))
102 return NULL;
103
104 if (!(new_node = calloc(1, sizeof(ll_node))))
105 return NULL;
106
107 new_node->data = data;
108 new_node->prev = NULL;
109 new_node->next = this->Head;;
110
111 if (this->Head)
112 this->Head->prev = new_node;
113 this->Head = this->Curr = new_node;
114
115 this->Size++;
116 return this->Curr->data;
117 }
118
119
120 /*******************************************************************************
121 * Remove the tail element from the list.
122 * Sets curr to tail.
123 * Return data, or NULL if the list is empty.
124 */
125 void * ll_pop(LinkedList * this)
126 {
127 void * data;
128 ll_node * tmp;
129
130 if (!this)
131 return NULL;
132
133 if (!(this->Tail))
134 return NULL;
135
136 tmp = this->Tail;
137 data = this->Tail->data;
138
139 if (!(this->Tail->prev))
140 {
141 /* Only element in list */
142 this->Head = this->Tail = this->Curr = NULL;
143 }
144 else
145 {
146 this->Tail->prev->next = NULL;
147 this->Tail = this->Curr = this->Tail->prev;
148 }
149
150 free(tmp);
151 this->Size--;
152
153 return data;
154 }
155
156
157 /*******************************************************************************
158 * Delete the element pointed to by this->curr.
159 * A pointer to the stored data is returned, or NULL is no list or an empty list
160 * is specified. It must be freed by the caller.
161 */
162 void * ll_remove(LinkedList * this)
163 {
164 void * data;
165 ll_node * tmp;
166
167 if (!this)
168 return NULL;
169
170 if (this->Curr == this->Tail)
171 return ll_pop(this);
172
173 tmp = this->Curr;
174 data = this->Curr->data;
175
176 if (this->Curr == this->Head)
177 {
178 this->Head->next->prev = NULL;
179 this->Head = this->Curr = this->Head->next;
180 }
181 else
182 {
183 this->Curr->prev->next = this->Curr->next;
184 this->Curr->next->prev = this->Curr->prev;
185 }
186
187 free(tmp);
188 this->Size--;
189
190 return data;
191 }
192
193
194 /*******************************************************************************
195 * Return the size of the list, or -1 is list is null.
196 */
197 int ll_size(LinkedList * this)
198 {
199 if (!this) return -1;
200
201 return this->Size;
202 }
203
204
205 /*******************************************************************************
206 * Select the first element in the list if there is one.
207 * Return data pointer of new current element, or NULL is list is empty.
208 */
209 void * ll_head(LinkedList * this)
210 {
211 if (!this) return NULL;
212
213 this->Curr = this->Head;
214
215 if (this->Curr)
216 return this->Curr->data;
217 else
218 return NULL;
219 }
220
221
222 /*******************************************************************************
223 * Select the last element in the list if there is one.
224 * Return data pointer of new current element, or NULL is list is empty.
225 */
226 void * ll_tail(LinkedList * this)
227 {
228 if (!this) return NULL;
229
230 this->Curr = this->Tail;
231
232 if (this->Curr)
233 return this->Curr->data;
234 else
235 return NULL;
236 }
237
238
239 /*******************************************************************************
240 * Return NULL if the list is empty or we are already at the tail, otherwise
241 * set Curr to the next element and return its data pointer.
242 */
243 void * ll_next(LinkedList * this)
244 {
245 if (!this) return NULL;
246
247 if (this->Curr && this->Curr->next)
248 {
249 this->Curr = this->Curr->next;
250 return this->Curr->data;
251 }
252 else
253 return NULL;
254
255 }
256
257
258 /*******************************************************************************
259 * Return NULL if the list is empty or we are already at the head, otherwise
260 * set Curr to the prev element and return its data pointer.
261 */
262 void * ll_prev(LinkedList * this)
263 {
264 if (!this) return NULL;
265
266 if (this->Curr && this->Curr->prev)
267 {
268 this->Curr = this->Curr->prev;
269 return this->Curr->data;
270 }
271 else
272 return NULL;
273 }
274
275
276 /*******************************************************************************
277 * Return the data pointer of the current node, or NULL is list is empty.
278 */
279 void * ll_data(LinkedList * this)
280 {
281 if (!this) return NULL;
282
283 if (this->Curr)
284 return this->Curr->data;
285 else
286 return NULL;
287 }
288
289
290 /*******************************************************************************
291 * Constuctor. Call this when creating a new list.
292 */
293 void ll_init(LinkedList * this)
294 {
295 if (this)
296 {
297 this->push = ll_push;
298 this->pop = ll_pop;
299 this->insert = ll_insert;
300 this->remove = ll_remove;
301 this->insert_at_head = ll_insert_at_head;
302 this->size = ll_size;
303 this->head = ll_head;
304 this->tail = ll_tail;
305 this->next = ll_next;
306 this->prev = ll_prev;
307 this->data = ll_data;
308
309 this->Head = this->Tail = this->Curr = NULL;
310 this->Size = 0;
311 }
312 }
313
314