这里实现的单链表，可以存储任意数据类型，支持增、删、改、查找、插入等基本操作。（本文提供的是完整代码，可能有些长。）
下面是头文件：
1 #ifndef SLIST_H 2 #define SLIST_H 3 4 #ifdef __cplusplus 5 extern "C" { 6 #endif 7 8 #define NODE_T(ptr, type) ((type*)ptr) 9 10 struct slist_node { 11 struct slist_node * next; 12 }; 13 14 typedef void (*list_op_free_node)(struct slist_node *node); 15 /* 16 * return 0 on hit key, else return none zero 17 */ 18 typedef int (*list_op_key_hit_test)(struct slist_node *node, void *key); 19 20 struct single_list { 21 /* all the members must not be changed manually by callee */ 22 struct slist_node * head; 23 struct slist_node * tail; 24 int size; /* length of the list, do not change it manually*/ 25 26 /* free method to delete the node 27 */ 28 void (*free_node)(struct slist_node *node); 29 /* 30 * should be set by callee, used to locate node by key(*_by_key() method) 31 * return 0 on hit key, else return none zero 32 */ 33 int (*key_hit_test)(struct slist_node *node, void *key); 34 35 struct single_list *(*add)(struct single_list * list, struct slist_node * node); 36 struct single_list *(*insert)(struct single_list * list, int pos, struct slist_node *node); 37 /* NOTE: the original node at the pos will be freed by free_node */ 38 struct single_list *(*replace)(struct single_list *list, int pos, struct slist_node *node); 39 struct slist_node *(*find_by_key)(struct single_list *, void * key); 40 struct slist_node *(*first)(struct single_list* list); 41 struct slist_node *(*last)(struct single_list* list); 42 struct slist_node *(*at)(struct single_list * list, int pos); 43 struct slist_node *(*take_at)(struct single_list * list, int pos); 44 struct slist_node *(*take_by_key)(struct single_list * list, void *key); 45 struct single_list *(*remove)(struct single_list * list, struct slist_node * node); 46 struct single_list *(*remove_at)(struct single_list *list, int pos); 47 struct single_list *(*remove_by_key)(struct single_list *list, void *key); 48 int (*length)(struct single_list * list); 49 void (*clear)(struct single_list * list); 50 void (*deletor)(struct single_list *list); 51 }; 52 53 struct single_list * new_single_list(list_op_free_node op_free, list_op_key_hit_test op_cmp); 54 55 #ifdef __cplusplus 56 } 57 #endif 58 59 #endif // SLIST_H
struct single_list 这个类，遵循我们前面介绍的基本原则，不再一一细说。有几点需要提一下：
- 我们定义了 slist_node 作为链表节点的基类，用户自定义的节点，都必须从 slist_node 继承
- 为了支持节点（ node ）的释放，我们引入一个回调函数 list_op_free_node ，这个回调需要在创建链表时传入
- 为了支持查找，引入另外一个回调函数 list_op_key_hit_test
好了，下面看实现文件：
1 #include "slist.h" 2 #include <malloc.h> 3 4 static struct single_list * _add_node(struct single_list *list, struct slist_node *node) 5 { 6 7 if(list->tail) 8 { 9 list->tail->next = node; 10 node->next = 0; 11 list->tail = node; 12 list->size++; 13 } 14 else 15 { 16 list->head = node; 17 list->tail = node; 18 node->next = 0; 19 list->size = 1; 20 } 21 22 return list; 23 } 24 25 static struct single_list * _insert_node(struct single_list * list, int pos, struct slist_node *node) 26 { 27 if(pos < list->size) 28 { 29 int i = 0; 30 struct slist_node * p = list->head; 31 struct slist_node * prev = list->head; 32 for(; i < pos; i++) 33 { 34 prev = p; 35 p = p->next; 36 } 37 if(p == list->head) 38 { 39 /* insert at head */ 40 node->next = list->head; 41 list->head = node; 42 } 43 else 44 { 45 prev->next = node; 46 node->next = p; 47 } 48 49 if(node->next == 0) list->tail = node; 50 list->size++; 51 } 52 else 53 { 54 list->add(list, node); 55 } 56 57 return list; 58 } 59 60 static struct single_list * _replace(struct single_list * list, int pos, struct slist_node *node) 61 { 62 if(pos < list->size) 63 { 64 int i = 0; 65 struct slist_node * p = list->head; 66 struct slist_node * prev = list->head; 67 for(; i < pos; i++) 68 { 69 prev = p; 70 p = p->next; 71 } 72 if(p == list->head) 73 { 74 /* replace at head */ 75 node->next = list->head->next; 76 list->head = node; 77 } 78 else 79 { 80 prev->next = node; 81 node->next = p->next; 82 } 83 84 if(node->next == 0) list->tail = node; 85 86 if(list->free_node) list->free_node(p); 87 else free(p); 88 } 89 90 return list; 91 } 92 93 static struct slist_node * _find_by_key(struct single_list *list, void * key) 94 { 95 if(list->key_hit_test) 96 { 97 struct slist_node * p = list->head; 98 while(p) 99 { 100 if(list->key_hit_test(p, key) == 0) return p; 101 p = p->next; 102 } 103 } 104 return 0; 105 } 106 107 static struct slist_node *_first_of(struct single_list* list) 108 { 109 return list->head; 110 } 111 112 static struct slist_node *_last_of(struct single_list* list) 113 { 114 return list->tail; 115 } 116 117 static struct slist_node *_node_at(struct single_list * list, int pos) 118 { 119 if(pos < list->size) 120 { 121 int i = 0; 122 struct slist_node * p = list->head; 123 for(; i < pos; i++) 124 { 125 p = p->next; 126 } 127 return p; 128 } 129 130 return 0; 131 } 132 133 static struct slist_node * _take_at(struct single_list * list, int pos) 134 { 135 if(pos < list->size) 136 { 137 int i = 0; 138 struct slist_node * p = list->head; 139 struct slist_node * prev = p; 140 for(; i < pos ; i++) 141 { 142 prev = p; 143 p = p->next; 144 } 145 if(p == list->head) 146 { 147 list->head = p->next; 148 if(list->head == 0) list->tail = 0; 149 } 150 else if(p == list->tail) 151 { 152 list->tail = prev; 153 prev->next = 0; 154 } 155 else 156 { 157 prev->next = p->next; 158 } 159 160 list->size--; 161 162 p->next = 0; 163 return p; 164 } 165 166 return 0; 167 } 168 169 static struct slist_node * _take_by_key(struct single_list * list, void *key) 170 { 171 if(list->key_hit_test) 172 { 173 struct slist_node * p = list->head; 174 struct slist_node * prev = p; 175 while(p) 176 { 177 if(list->key_hit_test(p, key) == 0) break; 178 prev = p; 179 p = p->next; 180 } 181 182 if(p) 183 { 184 if(p == list->head) 185 { 186 list->head = p->next; 187 if(list->head == 0) list->tail = 0; 188 } 189 else if(p == list->tail) 190 { 191 list->tail = prev; 192 prev->next = 0; 193 } 194 else 195 { 196 prev->next = p->next; 197 } 198 199 list->size--; 200 201 p->next = 0; 202 return p; 203 } 204 } 205 return 0; 206 } 207 208 static struct single_list *_remove_node(struct single_list * list, struct slist_node * node) 209 { 210 struct slist_node * p = list->head; 211 struct slist_node * prev = p; 212 while(p) 213 { 214 if(p == node) break; 215 prev = p; 216 p = p->next; 217 } 218 219 if(p) 220 { 221 if(p == list->head) 222 { 223 list->head = list->head->next; 224 if(list->head == 0) list->tail = 0; 225 } 226 else if(p == list->tail) 227 { 228 prev->next = 0; 229 list->tail = prev; 230 } 231 else 232 { 233 prev->next = p->next; 234 } 235 236 if(list->free_node) list->free_node(p); 237 else free(p); 238 239 list->size--; 240 } 241 return list; 242 } 243 244 static struct single_list *_remove_at(struct single_list *list, int pos) 245 { 246 if(pos < list->size) 247 { 248 int i = 0; 249 struct slist_node * p = list->head; 250 struct slist_node * prev = p; 251 for(; i < pos ; i++) 252 { 253 prev = p; 254 p = p->next; 255 } 256 if(p == list->head) 257 { 258 list->head = p->next; 259 if(list->head == 0) list->tail = 0; 260 } 261 else if(p == list->tail) 262 { 263 list->tail = prev; 264 prev->next = 0; 265 } 266 else 267 { 268 prev->next = p->next; 269 } 270 271 if(list->free_node) list->free_node(p); 272 else free(p); 273 274 list->size--; 275 } 276 277 return list; 278 } 279 280 static struct single_list *_remove_by_key(struct single_list *list, void *key) 281 { 282 if(list->key_hit_test) 283 { 284 struct slist_node * p = list->head; 285 struct slist_node * prev = p; 286 while(p) 287 { 288 if(list->key_hit_test(p, key) == 0) break; 289 prev = p; 290 p = p->next; 291 } 292 293 if(p) 294 { 295 if(p == list->head) 296 { 297 list->head = list->head->next; 298 if(list->head == 0) list->tail = 0; 299 } 300 else if(p == list->tail) 301 { 302 prev->next = 0; 303 list->tail = prev; 304 } 305 else 306 { 307 prev->next = p->next; 308 } 309 310 if(list->free_node) list->free_node(p); 311 else free(p); 312 313 list->size--; 314 } 315 } 316 317 return list; 318 } 319 320 static int _length_of(struct single_list * list) 321 { 322 return list->size; 323 } 324 325 static void _clear_list(struct single_list * list) 326 { 327 struct slist_node * p = list->head; 328 struct slist_node * p2; 329 while(p) 330 { 331 p2 = p; 332 p = p->next; 333 334 if(list->free_node) list->free_node(p2); 335 else free(p2); 336 } 337 338 list->head = 0; 339 list->tail = 0; 340 list->size = 0; 341 } 342 343 static void _delete_single_list(struct single_list *list) 344 { 345 list->clear(list); 346 free(list); 347 } 348 349 struct single_list * new_single_list(list_op_free_node op_free, list_op_key_hit_test op_cmp) 350 { 351 struct single_list *list = (struct single_list *)malloc(sizeof(struct single_list)); 352 list->head = 0; 353 list->tail = 0; 354 list->size = 0; 355 list->free_node = op_free; 356 list->key_hit_test = op_cmp; 357 358 list->add = _add_node; 359 list->insert = _insert_node; 360 list->replace = _replace; 361 list->find_by_key = _find_by_key; 362 list->first = _first_of; 363 list->last = _last_of; 364 list->at = _node_at; 365 list->take_at = _take_at; 366 list->take_by_key = _take_by_key; 367 list->remove = _remove_node; 368 list->remove_at = _remove_at; 369 list->remove_by_key = _remove_by_key; 370 list->length = _length_of; 371 list->clear = _clear_list; 372 list->deletor = _delete_single_list; 373 374 return list; 375 }
上面的代码就不一一细说了，下面是测试代码：
1 /* call 1 or N arguments function of struct */ 2 #define ST_CALL(THIS,func,args...) ((THIS)->func(THIS,args)) 3 4 /* call none-arguments function of struct */ 5 #define ST_CALL_0(THIS,func) ((THIS)->func(THIS)) 6 7 struct int_node { 8 struct slist_node node; 9 int id; 10 }; 11 12 struct string_node { 13 struct slist_node node; 14 char name[16]; 15 }; 16 17 18 static int int_free_flag = 0; 19 static void _int_child_free(struct slist_node *node) 20 { 21 free(node); 22 if(!int_free_flag) 23 { 24 int_free_flag = 1; 25 printf("int node free "); 26 } 27 } 28 29 static int _int_slist_hittest(struct slist_node * node, void *key) 30 { 31 struct int_node * inode = NODE_T(node, struct int_node); 32 int ikey = (int)key; 33 return (inode->id == ikey ? 0 : 1); 34 } 35 36 static int string_free_flag = 0; 37 static void _string_child_free(struct slist_node *node) 38 { 39 free(node); 40 if(!string_free_flag) 41 { 42 string_free_flag = 1; 43 printf("string node free "); 44 } 45 } 46 47 static int _string_slist_hittest(struct slist_node * node, void *key) 48 { 49 struct string_node * sn = (struct string_node*)node; 50 return strcmp(sn->name, (char*)key); 51 } 52 53 void int_slist_test() 54 { 55 struct single_list * list = new_single_list(_int_child_free, _int_slist_hittest); 56 struct int_node * node = 0; 57 struct slist_node * bn = 0; 58 int i = 0; 59 60 printf("create list && nodes: "); 61 for(; i < 100; i++) 62 { 63 node = (struct int_node*)malloc(sizeof(struct int_node)); 64 node->id = i; 65 if(i%10) 66 { 67 list->add(list, node); 68 } 69 else 70 { 71 list->insert(list, 1, node); 72 } 73 } 74 printf("create 100 nodes end ---- "); 75 printf("first is : %d, last is: %d ---- ", 76 NODE_T( ST_CALL_0(list, first), struct int_node )->id, 77 NODE_T( ST_CALL_0(list, last ), struct int_node )->id); 78 79 assert(list->size == 100); 80 81 printf("list traverse: "); 82 for(i = 0; i < 100; i++) 83 { 84 if(i%10 == 0) printf(" "); 85 bn = list->at(list, i); 86 node = NODE_T(bn, struct int_node); 87 printf(" %d", node->id); 88 } 89 printf(" ----- "); 90 91 printf("find by key test, key=42: "); 92 bn = list->find_by_key(list, (void*)42); 93 assert(bn != 0); 94 node = NODE_T(bn, struct int_node); 95 printf("find node(key=42), %d ------ ", node->id); 96 97 printf("remove node test, remove the 10th node: "); 98 bn = list->at(list, 10); 99 node = NODE_T(bn, struct int_node); 100 printf(" node 10 is: %d ", node->id); 101 printf(" now remove node 10 "); 102 list->remove_at(list, 10); 103 printf(" node 10 was removed, check node 10 again: "); 104 bn = list->at(list, 10); 105 node = NODE_T(bn, struct int_node); 106 printf(" now node 10 is: %d ------ ", node->id); 107 108 printf("replace test, replace node 12 with id 1200: "); 109 bn = list->at(list, 12); 110 node = NODE_T(bn, struct int_node); 111 printf(" now node 12 is : %d ", node->id); 112 node = (struct int_node*)malloc(sizeof(struct int_node)); 113 node->id = 1200; 114 list->replace(list, 12, node); 115 bn = list->at(list, 12); 116 node = NODE_T(bn, struct int_node); 117 printf(" replaced, now node 12 is : %d ---- ", node->id); 118 119 printf("test remove: "); 120 ST_CALL(list, remove, bn); 121 bn = ST_CALL(list, find_by_key, (void*)1200); 122 assert(bn == 0); 123 printf("test remove ok ---- "); 124 printf("test remove_by_key(90): "); 125 ST_CALL(list, remove_by_key, (void*)90); 126 bn = ST_CALL(list, find_by_key, (void*)90); 127 assert(bn == 0); 128 printf("test remove_by_key(90) end ---- "); 129 printf("test take_at(80): "); 130 bn = ST_CALL(list, take_at, 80); 131 printf(" node 80 is: %d ", NODE_T(bn, struct int_node)->id); 132 free(bn); 133 printf("test take_at(80) end "); 134 135 int_free_flag = 0; 136 printf("delete list && nodes: "); 137 list->deletor(list); 138 printf("delete list && nodes end "); 139 printf(" test add/insert/remove/delete/find_by_key/replace... "); 140 } 141 142 void string_slist_test() 143 { 144 struct single_list * list = new_single_list(_string_child_free, _string_slist_hittest); 145 } 146 147 void slist_test() 148 { 149 int_slist_test(); 150 string_slist_test(); 151 }
测试代码里主要演示了：
- 自定义链表节点类型
- 定义释放回调
- 定义用于查找的 hit test 回调
- 如何创建链表
- 如何使用（ add 、remove 、 take 、find 、 insert 等）
相信到这里，单链表的使用已经不成问题了。
以单链表为基础，可以进一步实现很多数据结构，比如树（兄弟孩子表示法），比如 key-value 链表等等。接下来根据例子的需要，会择机进行展示。