# Functional-style linked list written in C

For my Operating Systems class, I needed a linked list data structure and didn't have one already written. During the course of thinking about how to implement a linked list again (it had been a while..), I decided that a lot of the most common functions used on linked lists can be implemented based on applying or composing a few core functions.

First, I wrote a function that iterates over the list starting from list->head while applying a function to each element. After each iteration, if the function returned false, then stop iterating and return a pointer to the node which terminated the loop. Otherwise, iterate until list->tail had the function applied to it.

Basically all of the rest of my functions fall from this one function. I was able to quickly implement map by calling the iteration function and always returning true (and therefore the iteration will never end prematurely). I was also able to implement a general iterative "test" function, which requires a function parameter that accepts two node arguments and produces a boolean. The point of the iterative test function is to implement things like sorting or testing for equality in a composable way.

I think my attempt isn't half bad, given that I was writing in C without any anonymous functions or closures (of which my knowledge is limited). That being said, I'm glad to hear what criticisms the community has on the implementation on a whole or nit-picking.

llist.h

#ifndef LLIST_H
#define LLIST_H

/* Fields */
typedef struct _node {
struct _node *next, *prev;
void *data;
} node;

typedef struct {
node *head, *tail;
size_t size;
} llist;

typedef enum {FALSE, TRUE} bool;

typedef void (*nodefunc)(node *);
typedef bool (*nodeiter)(node *);
typedef bool (*nodetest)(void *, void *);

/* Methods */
void llist_init(llist *l);
void llist_node_init(node *n);

void map(llist *l, nodefunc f);
void *llist_iter(llist *l, nodeiter f);
void *llist_test(llist *l, void *q, nodetest t);

void llist_append(llist *l, node *n);
void llist_remove(llist *l, node *n);
void llist_destroy(llist *l, nodefunc node_free);

#endif


llist.c

#include <stdlib.h>
#include "llist.h"

void llist_init(llist *l) {
l->head = NULL;
l->tail = NULL;
l->size = 0;
}

void llist_node_init(node *n) {
n->data = NULL;
n->next = NULL;
n->prev = NULL;
}

void *llist_iter(llist *l, nodeiter f) {
node *n = l->head, *next = NULL;
void *result = 0;

while (n != NULL && result == 0) {
next = n->next;
if (!f(n))
result = (void*)n;
n = next;
}

return result;
}

void *llist_test(llist *l, void *q, nodetest t) {
bool iter_test(node *n) {
return !( t((void*)n->data, q) );
}
return llist_iter(l, iter_test);
}

// not a true map since f can have side effects
void map(llist *l, nodefunc f) {
bool iter_true(node *n) {
f(n);
return TRUE;
}
llist_iter(l, iter_true);
}

void llist_append(llist *l, node *n) {
if (l->size == 0) {
l->head = n;
l->tail = n;
} else {
n->prev = l->tail;
l->tail->next = n;
l->tail = n;
}

l->size++;
}

void llist_remove(llist *l, node *n) {
if (n) {
if (n->prev)
n->prev->next = n->next;
else
l->head = n->next;

if (n->next)
n->next->prev = n->prev;
else
l->tail = n->prev;

l->size--;
}
}

void llist_destroy(llist *l, nodefunc node_free) {
void iter_remove(node *n) {
llist_remove(l, n);
node_free(n);
}
map(l, iter_remove);
}


From this, I'm able to implement in a program, for example, a print function based on the type of data that is stored in the linked list:

llist_test.c

#include <stdio.h>
#include <stdlib.h>
#include "llist.h"

void llist_print(llist *l) {
void iter_print(node *n) {
printf("value: %d\n", *(int*)n->data);
}
map(l, iter_print);
}

void node_free(node *n) { free(n); }

node *alloc_node(int *data) {
node *n = malloc(sizeof(node));
llist_node_init(n);
n->data = data;
return n;
}

int main() {
llist *l = malloc(sizeof(llist));
llist_init(l);

int x = 4, y = 8;
llist_append(l, alloc_node(&x));

// ...

llist_destroy(l, node_free);
free(l);

return 0;
}


## 2 Answers

C Standard doesn't allow nested functions. A strictly conforming compiler must fail to compile llist_test and friends. If you are OK with deviating from Standard, take a look at blocks, which are considered much more secure and have a chance (unlike nested functions) to eventually get into Standard.

• Oof. Thanks for the information. This is actually really important for me because my instructor might be compiling with clang, not gcc. That didn't even occur to me until now. – itsjareds Feb 11 '15 at 15:14
• Linked lists come in all sorts of flavors--singly linked, doubly linked, circularly linked, .... Instead of using 'll' as the prefix (presumably for linked list), I would suggest using 'dll' for doubly linked list.
• Watch your namespace pollution. 'node' and '_node' are fairly generic names and it is not unreasonable to expect that a module that includes this header file could define structures of that type. Minimize the expected namespace collision by naming this structure type as '_dllnode' or 'dllnode'.
• If you want a 'bool' type, I would suggest including 'stdbool.h' instead of defining your own. stdbool.h defines 'true' and 'false'. If memory serves, this is something that is for C99 and later.
• If you are going to typedef the function pointers, it may be beneficial to change the names to make it easier to identify that these are function pointer typedefs.
• The name 'map()' appears out of place. All the other routines that operate on a list have a 'llist_' prefix. Consistency is important.
• As a user of this, I would have expected to see a routine named 'llist_insert' for inserting a node into an arbitrary point in the linked list.
• This may be a matter of preference, but for a general linked list implementation, I don't think the linked list node should have any references to the data (pointer or otherwise). If you want a node with data ...
struct my_node {
dll_node  node;
<data>
};

• Following the previous, llist_destroy() should be implemented at a higher level. There are going to be lots of times when the user of this module may want the benefits of a linked list, but do not want to dynamically allocate the elements.
• llist_node_init() should initialize the structure fields in the same order as they were declared. This makes it easier to ensure that items were not missed.
• As a personal preference, I like to see one variable defined per line. (This is highly subjective).
• In llist_iter(), 'result' is a pointer and should be initialized to NULL, not 0. Similarly, it should be compared against NULL in the loop.
• Better yet, rewrite llist_iter() to eliminate the need for 'result' and some unnecessary assignments of 'n' when leaving the loop.
while (n != NULL) {
if (!f(n)) {
return (void *)n;
}
n = n->next;
}
return NULL;

• Someone else has already mentioned nested functions, so I won't go into more on that.
• What is meant by a 'true map'? What is meant by 'map'?
• In llist_remove(), I would suggest that you avoid one level of indentation by returning early if 'n' is NULL.

Hope this helps.