Jonathan said:
Just finished a new IBM DeveloperWorks article on linked lists, and
thought you all might be interested. It's not an introduction -- it
instead covers some of the more interesting aspects of linked lists.
http://www.ibm.com/developerworks/linux/library/l-listproc/
You have:
Listing 4. Linked list using generic nodes
struct generic_node {
data the_data;
struct generic_node *next;
};
.... but
struct generic_node {
void *data;
struct generic_node *next;
};
is really more generic.
It's especially useful if data points to a structure
which has pointers to lists with different types of data.
struct generic_node *list_rev(struct generic_node *head)
{
struct generic_node *previous, *next_node;
if (head != NULL) {
next_node = NULL;
while (head -> next != NULL) {
previous = head;
head = previous -> next;
previous -> next = next_node;
next_node = previous;
}
head -> next = next_node;
}
return head;
}
void list_free(struct generic_node *node, void (*free_data)(void *))
{
struct generic_node *next_node;
while (node != NULL) {
next_node = node -> next;
free_data(node -> data);
free(node);
node = next_node;
}
}
struct generic_node *list_sort(struct generic_node *head,
int (*compar)(const struct generic_node *,
const struct generic_node *))
{
return node_sort(head, list_count(head), compar);
}
size_t list_count(struct generic_node *head)
{
size_t count;
for (count = 0; head != NULL; head = head -> next) {
++count;
}
return count;
}
struct generic_node *node_sort(struct generic_node *head, size_t count,
int (*compar)(const struct generic_node *,
const struct generic_node *))
{
size_t half;
struct generic_node *tail;
if (count > 1) {
half = count / 2;
tail = list_split(head, half);
tail = node_sort(tail, count - half, compar);
head = node_sort(head, half, compar);
head = list_merge(head, tail, compar);
}
return head;
}
struct generic_node *list_split(struct generic_node *head, size_t count)
{
struct generic_node *tail;
while (count-- > 1) {
head = head -> next;
}
tail = head -> next;
head -> next = NULL;
return tail;
}
struct generic_node *list_merge(struct generic_node *head, struct
generic_node *tail,
int (*compar)(const struct generic_node *,
const struct generic_node *))
{
struct generic_node *list, *sorted, **node;
node = compar(head, tail) > 0 ? &tail : &head;
sorted = list = *node;
*node = sorted -> next;
while (*node != NULL) {
node = compar(head, tail) > 0 ? &tail : &head;
sorted -> next = *node;
sorted = sorted -> next;
*node = sorted -> next;
}
sorted -> next = head != NULL ? head : tail;
return list;
}
int list_sorted(struct generic_node *list,
int (*compar)(const struct generic_node *,
const struct generic_node *))
{
if (list != NULL) {
while (list -> next != NULL) {
if (compar(list, list -> next) > 0) {
break;
}
list = list -> next;
}
}
return list == NULL || list -> next == NULL;
}
