5
\$\begingroup\$

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;
}
\$\endgroup\$

2 Answers 2

1
\$\begingroup\$

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.

\$\endgroup\$
0
\$\begingroup\$

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.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.