Doubly Linked List implementation with C

Question

I realized that after nearly five years of programming and one year of actual being employed as a programmer professionally that I have never actually sat down and implemented a linked list from scratch. I figured it would not hurt to brush up on "The Fundamentals" a little bit in my spare time. (I am primarily self taught with the exception of a handful of courses during college that were taken as electives during and non CS major). Any review, suggestions, etc... would be appreciated.

list.h

#ifndef __LIST_H__
#define __LIST_H__

#include <stdbool.h>

struct list_node;

typedef struct list_node *LIST_NODE_H;

// Create a list node
//
LIST_NODE_H list_node_create(void *data);

// Destroy a list node
//
void *list_node_destroy(LIST_NODE_H node);

// Insert a new node after an existing node
//
bool list_insert_after(LIST_NODE_H old, LIST_NODE_H new);

// Insert a new node before an existing node
//
bool list_insert_before(LIST_NODE_H old, LIST_NODE_H new);

// Remove a node from the list and return it
//
LIST_NODE_H list_remove(LIST_NODE_H node);

// Destroy a list and free all attached data using a supplied free     function
//
bool list_destroy(LIST_NODE_H node, void (*free_func)(void *));

// Get the next node in the list
//
LIST_NODE_H list_next(const LIST_NODE_H node);

// Get the previous node in the list
//
LIST_NODE_H list_prev(const LIST_NODE_H node);

// Get the first node in the list
//
LIST_NODE_H list_front(const LIST_NODE_H node);

// Get the last node in the list
//
LIST_NODE_H list_back(const LIST_NODE_H node);

// Get the data from a list node
//
void *list_data(LIST_NODE_H node);

// Find a the first node in the list that matched the provided "what" value using the supplied comparator
// Search Order:
//  - The supplied node
//  - Forwards from the supplied node
//  - Backwards from the supplied node
//
typedef bool (*list_comparator_t)(void *what, const void *value);
LIST_NODE_H list_find(const LIST_NODE_H node, const void *what,   list_comparator_t comparator);

// Iterate forwards over a list
// WARNING: does not support destructive list operations
//
#define list_foreach_forward(start, iter) \
for (iter = start; iter; iter = list_next(iter))
// Iterate backwards over a list
// WARNING: does not support destructive list operations
//
#define list_foreach_backward(start, iter) \
for (iter = start; iter; iter = list_prev(iter))

#endif //__LIST_H__

list.c

#include "list.h"
#include <stddef.h>
#include <stdlib.h>

struct list_node
{
    LIST_NODE_H next;
    LIST_NODE_H prev;
    void *data;
};

LIST_NODE_H list_node_create(void *data)
{
    LIST_NODE_H node = malloc(sizeof(struct list_node));
    if (node)
    {
        node->next = NULL;
        node->prev = NULL;
        node->data = data;
    }
    return node;
}

void *list_node_destroy(LIST_NODE_H node)
{
    if (node)
    {
        void *data = node->data;
        node->next = NULL;
        node->prev = NULL;
        free(node);
        return data;
    }
    return NULL;
}

bool list_insert_after(LIST_NODE_H old, LIST_NODE_H new)
{
    if (old && new)
    {
        if (old->next)
        {
            old->next->prev = new;
            new->next = old->next;
        }
        old->next = new;
        new->prev = old;
        return true;
    }
    return false;
}

bool list_insert_before(LIST_NODE_H old, LIST_NODE_H new)
{
    if (old && new)
    {
        if (old->prev)
        {
            old->prev->next = new;
            new->prev = old->prev;
        }
        old->prev = new;
        new->next = old;
        return true;
    }
    return false;
}

LIST_NODE_H list_remove(LIST_NODE_H node)
{
    if (node)
    {
        if (node->next)
        {
            node->next->prev = node->prev;
            node->next = NULL;
        }
        if (node->prev)
        {
            node->prev->next = node->next;
            node->prev = NULL;
        }
        return node;
    }
    return NULL;
}

void list_destroy_forward(LIST_NODE_H node, void (*free_func)(void *))
{
    LIST_NODE_H next = list_next(node);
    if (next)
        list_destroy_forward(next, free_func);
    free_func(list_node_destroy(list_remove(node)));
}

void list_destroy_backward(LIST_NODE_H node, void (*free_func)(void *))
{
    LIST_NODE_H prev = list_prev(node);
    if (prev)
        list_destroy_backward(prev, free_func);
    free_func(list_node_destroy(list_remove(node)));
}

bool list_destroy(LIST_NODE_H node, void (*free_func)(void *))
{
    if (node)
    {
        LIST_NODE_H prev = list_prev(node);
        list_destroy_forward(node, free_func);
        if (prev)
            list_destroy_backward(prev, free_func);
        return true;
    }
    return false;
}

LIST_NODE_H list_next(const LIST_NODE_H node)
{
    if (node && node->next)
        return node->next;
    return NULL;
}

LIST_NODE_H list_prev(const LIST_NODE_H node)
{
    if (node && node->prev)
        return node->prev;
    return NULL;
}

LIST_NODE_H list_front(const LIST_NODE_H node)
{
    LIST_NODE_H iter = node;
    LIST_NODE_H temp = NULL;
    while ((temp = list_prev(iter)))
        iter = temp;
    return iter;
}

LIST_NODE_H list_back(const LIST_NODE_H node)
{
    LIST_NODE_H iter = node;
    LIST_NODE_H temp = NULL;
    while ((temp = list_next(iter)))
        iter = temp;
    return iter;
}

void *list_data(const LIST_NODE_H node)
{
    if (node)
        return node->data;
    return NULL;
}

LIST_NODE_H list_find_forward(const LIST_NODE_H node, const void *what, list_comparator_t comparator)
{
    if (node)
    {
        if (comparator(list_data(node), what))
        {
            return node;
        }
        else
        {
            return list_find_forward(list_next(node), what, comparator);
        }
    }
    return NULL;
}

LIST_NODE_H list_find_backward(const LIST_NODE_H node, const void *what, list_comparator_t comparator)
{
    if (node)
    {
        if (comparator(list_data(node), what))
        {
            return node;
        }
        else
        {
            return list_find_backward(list_prev(node), what, comparator);
        }
    }
    return NULL;
}

LIST_NODE_H list_find(const LIST_NODE_H node, const void *what, list_comparator_t comparator)
{
    if (node && comparator)
    {
        LIST_NODE_H found = NULL;
        if (comparator(list_data(node), what))
        {
            return node;
        }
        else if ((found = list_find_forward(list_next(node), what, comparator)))
        {
            return found;
        }
        else if ((found = list_find_backward(list_prev(node), what, comparator)))
        {
            return found;
        }
        else
        {
            return found;
        }
    }
    return NULL;
}

Answer 1

LGTM. Few notes:

• A test for node->next in list_next is redundant. Ditto for node->prev in list_prev.

• list_node_destroy may only be called on a standalone node. Calling it on a node in the list corrupts the list. Consider not exposing node creation and destruction at all.

• A natural place to call free_func is list_node_destroy. In any case, consider testing for free_func != NULL before calling it.

• I do not endorse recursion when the iterative algorithm is readily available.

Answer 2

In my opinion, you can improve your coding style a lot. Here, you can give "{" just after the if statement like

if (node && comparator)
{

}
return NULL;

Normally any standard code follows style like if (node && comparator) { And if there is only one statement under the if condition then we can ignore "{", this will make your code more readable.