This is a doubly-linked list implementation. A linked list allows easy insertion and removal at either end or in the middle. Being doubly-linked allows traversal in reverse as well as forwards.
Here is an example program:
#include <stdio.h> #include <string.h> #include <linkedlist.h> int main(void) { linkedlist * list = linkedlist_create(); char * elements[] = {"A", "B", "C", "D", "E", "F"}; const unsigned int n = sizeof(elements) / sizeof(const char*); unsigned int i; listnode * node; unsigned int found = 0; /* Populate the list with A, B, ..., F */ for (i = 0; i < n; i++) { linkedlist_add_tail(list, elements[i]); } /* Insert X and Y either side of C */ for (node = list->head; node != NULL && !found; node = node->next) { if (strcmp((const char*)node->data, "C") == 0) { linkedlist_insert_before(list, node, "X"); linkedlist_insert_after(list, node, "Y"); found = 1; } } /* Forward iteration */ for (node = list->head; node != NULL; node = node->next) { printf("%s\n", (const char*)node->data); } putchar('\n'); /* Reverse iteration */ for (node = list->tail; node != NULL; node = node->previous) { printf("%s\n", (const char*)node->data); } linkedlist_delete(list); return 0; }
The header file:
#ifndef LINKEDLIST_H #define LINKEDLIST_H struct listnode { struct listnode * next; struct listnode * previous; void * data; }; typedef struct listnode listnode; struct linkedlist { listnode * head; listnode * tail; unsigned int count; }; typedef struct linkedlist linkedlist; typedef void (*linkedlist_forfn)(void *); linkedlist * linkedlist_create(void); void linkedlist_empty(linkedlist * list); void linkedlist_delete(linkedlist * list); void linkedlist_add_head(linkedlist * list, void * data); void linkedlist_add_tail(linkedlist * list, void * data); void linkedlist_insert_before(linkedlist * list, listnode * node, void * data); void linkedlist_insert_after(linkedlist * list, listnode * node, void * data); void * linkedlist_remove_head(linkedlist * list); void * linkedlist_remove_tail(linkedlist * list); void * linkedlist_remove_node(linkedlist * list, listnode * node); void linkedlist_for_each(const linkedlist * list, linkedlist_forfn fun); unsigned int linkedlist_get_count(const linkedlist * list); #endif /* LINKEDLIST_H */
The implementation:
#include <stdlib.h> #include <linkedlist.h> listnode * listnode_create(void * data) { listnode * node = malloc(sizeof(listnode)); if (node) { node->next = NULL; node->previous = NULL; node->data = data; } return node; } linkedlist * linkedlist_create(void) { linkedlist * list = malloc(sizeof(linkedlist)); if (list) { list->head = NULL; list->tail = NULL; list->count = 0; } return list; } void linkedlist_empty(linkedlist * list) { while(list->head != NULL) { linkedlist_remove_tail(list); } } void linkedlist_delete(linkedlist * list) { if (list) { linkedlist_empty(list); free(list); } } void linkedlist_add_head(linkedlist * list, void * data) { listnode * node; node = listnode_create(data); if (list->head != NULL) { list->head->previous = node; node->next = list->head; list->head = node; } else { list->head = node; list->tail = node; } list->count++; } void linkedlist_add_tail(linkedlist * list, void * data) { listnode * node; node = listnode_create(data); if (list->tail != NULL) { list->tail->next = node; node->previous = list->tail; list->tail = node; } else { list->head = node; list->tail = node; } list->count++; } void linkedlist_insert_before(linkedlist * list, listnode * node, void * data) { listnode * newnode; if (node == list->head) { linkedlist_add_head(list, data); } else { newnode = listnode_create(data); newnode->next = node; newnode->previous = node->previous; node->previous->next = newnode; node->previous = newnode; list->count++; } } void linkedlist_insert_after(linkedlist * list, listnode * node, void * data) { listnode * newnode; if (node == list->tail) { linkedlist_add_tail(list, data); } else { newnode = listnode_create(data); newnode->previous = node; newnode->next = node->next; node->next->previous = newnode; node->next = newnode; list->count++; } } void * linkedlist_remove_head(linkedlist * list) { void * data = NULL; if (list->head != NULL) { listnode * temp = list->head; list->head = list->head->next; if (list->head == NULL) { list->tail = NULL; } else { list->head->previous = NULL; if (list->head->next != NULL) { list->head->next->previous = list->head; } else { list->tail = list->head; } } data = temp->data; free(temp); list->count--; } return data; } void * linkedlist_remove_tail(linkedlist * list) { void * data = NULL; if (list->tail != NULL) { listnode * temp = list->tail; list->tail = list->tail->previous; if (list->tail == NULL) { list->head = NULL; } else { list->tail->next = NULL; if (list->tail->previous != NULL) { list->tail->previous->next = list->tail; } else { list->head = list->tail; } } data = temp->data; free(temp); list->count--; } return data; } void * linkedlist_remove_node(linkedlist * list, listnode * node) { void * data; if (node == list->head) { data = linkedlist_remove_head(list); } else if (node == list->tail) { data = linkedlist_remove_tail(list); } else { node->previous->next = node->next; node->next->previous = node->previous; data = node->data; free(node); list->count--; } return data; } void linkedlist_for_each(const linkedlist * list, forfn fun) { listnode * node; for (node = list->head; node != NULL; node = node->next) { fun(node->data); } } unsigned int linkedlist_get_count(const linkedlist * list) { return list->count; }