A Generic Approach To Doubly Linked Lists

I've written a small implementation for doubly linked lists. While actually intended to be only used by me in subsequent projects, I wrote it as generically as possible. Maybe this'll be advantageous.

I tested the implementation and resolved as many bugs as possible but maybe there are more lurking somewhere in the code.

Also, the implementation is supposed to be usable for different lists at the same time but operations cannot be performed on one list simultaneously. I'll have to add a spinlock to the list and alter the code a bit for that.

The list works as follows:

the first (head) node has the prev field set to NULL, the last (tail) node has the next field set to NULL. A size field counts the number of nodes in the list. If size == 1, prev and next of this lonely node contain NULL and head == tail == node. If size == 0, head and tail are indeterminate.

Code

Header (dll.h):

``
#ifndef DOUBLY_LINKED_LIST_H
#define DOUBLY_LINKED_LIST_H

/* When reading through this code, you may encounter functions not being
* strictly const-correct. This is because I wanted to make const-correctness
* to depict the CONCEPTUAL const-ness, not const-ness due to some random
* implementation-detail.
*/

/* From this implementation's perspective, this is not a pointer to the data
* but really the data itsself.
*/
typedef void* data_t;

/* I second that the name "dll" for "doubly-linked list" is ambiguous
* with the Windows DLL (Dynamic Link Library) but I don't think this'll
* lead to any serious confusion.
*/

typedef struct dll_node {
struct dll_node* prev;
struct dll_node* next;

data_t data;
} dll_node_t;

typedef int (cleanup_op_t)(dll_node_t node);

typedef struct dll {
dll_node_t* head;
dll_node_t* tail;

cleanup_op_t cleanup_op;

size_t size;
} dll_t;

/* Initializes a list with zero nodes.
* list' - The list to initialize
* `cleanup_op' - The operation to apply to every datum when it is
*

Data storage

If you change your data_t typedef to be anything other than void*, your linked list implementation has to be copied and modified to handle multiple types (so it's less generic); on the other hand, you get better type safety. The tradeoff is probably in how you're going to use it.

One thought: I would suggest looking at how the linux kernel does linked lists: they have a list_head struct, which is then included inside the data types that you want to put into a list. So it looks something like (e.g., if you had a linked list of strings):

struct list_head {
    struct list_head *next, *prev;
};

struct element {
    char *s;
    struct list_head list;
};

Then, you have a bunch of linked-list functions which operate on list_head pointers, and use an offsetof macro to get back from the list_head to the enclosing structure.

Not to say that this is better, but it's arguably a more type-safe way to get 'generic' linked lists in C. Both approaches are valid, though (and yours is more 'classic').

Const correctness

I would generally say that things should be const whenever possible, because it makes programs easier to reason about. I generally encounter the opposite problem to the one you're describing, though: something is conceptually const, but for incidental implementation reasons it needs to be mutable.

DLL naming

Well, 'dll' isn't the clearest name, because of the conceptual collision with Windows libraries. It probably isn't a big deal unless you're writing software on Windows and using dlls. I would be tempted to just call this module "list", or "ll", though.

The only real constraint on the include guard macro is that it not collide with any other names in your program. I suspect that DOUBLY_LINKED_LIST_H is probably fine. (Obviously, if you have some style guide or standard, that probably specifies a convention).

Implementation

This is pretty nice code overall. If I were feeling picky:

• Names ending in _t are strictly reserved for the standard, iirc. Struct tags are in a different namespace, so it's totally reasonable to do typedef struct foo {} foo;.

• I'd be inclined to prefer consistency of bracing at least within a particular control structure (so if () {} else {} rather than if () ; else {} even if one branch has only one statement).

-
I'd be inclined to break section up the files a little with comments---while I'm not a fan of those huge ASCII-art comment headers, I find files easier to read if they have little headers like

/* --- type declarations --- */

...

/* --- function declarations --- */

...

/* --- function definitions --- */

Just a little extra stuff to help find your way around the file, and separate things which are conceptually different. It may be that not everyone agrees with me on that, though.

StackExchange Code Review Q#119298, answer score: 4