Linked list implementation

Question

I wrote some code for linked lists and would like to know what things could/should be done differently.

I'm using an index to keep track of the most important information and have 2 sets of functions, one to use the list just to point to data and the other to store the data in the list.

Here's the code so far:

#include <stdlib.h>
#include <string.h>

//Basic structure
typedef struct nNode Node;
struct nNode {
    void *content;
    Node *next;
    Node *previous;
};

//An index will make everything simpler
typedef struct {
    Node *first;
    Node *last;
    size_t node_count;
} List;

//Initialize list index with default values
void init_list(List *root)
{
    root->first = NULL;
    root->last = NULL;
    root->node_count = 0;
}

//Link new element and return pointer to it if successful or NULL
Node *add_node(List *root, void *content)
{
    Node *temp = malloc(sizeof(Node));
    if(temp == NULL){
        return NULL;
    }

    //Fill node    
    temp->content = content;
    temp->next = NULL;
    temp->previous = root->last; //NULL if first node

    //Handle first element insertion
    if(root->first == NULL){
        root->first = temp;
    }

    //Or update previous element
    else {
        root->last->next = temp;
    }

    //Update index
    root->last = temp;            
    ++root->node_count;

    return temp;    
}

//Unlink element, always successful
void delete_node(List *root, Node *node)
{
    //If it's the first, update index reference
    if(node->previous == NULL){
        root->first = node->next;
    }

    //Or it's safe to update previous node
    else {
        node->previous->next = node->next;
    }    

    //If it's the last, update index reference
    if(node->next == NULL){
        root->last = node->previous;
    }

    //Not the last? Safe to update next node
    else {
        node->next->previous = node->previous;
    }

    //Update count and free memory
    free(node);
    --root->node_count;
}

//Iterate through all nodes and call a function on every iteration
void iterate(const List *root, void(*function)(Node*))
{
    Node *next; //store in case the node changes
    for(Node *ite = root->first; ite != NULL; ite = next){
        next = ite->next;
        (*function)(ite);
    }
}

//Iterate through all nodes backwards and call a function on every iteration
void iterate_backwards(const List *root, void(*function)(Node*))
{
    Node *previous; //store in case the node changes
    for(Node *ite = root->last; ite != NULL; ite = previous){
        previous = ite->previous;
        (*function)(ite);
    }
}

//Delete all elements in the list
void delete_list(List *root)
{
    iterate(root, (void(*)(Node*))free);
    init_list(root);
}

////////////////
////// The following functions also store the content in the list
///// instead of just pointing to it. They should be used together
//// in order to avoid memory leaks.
/////////////

//Add node and store a copy of content
Node *add_node_store(List *root, const void *content, size_t content_size)
{
    //Allocate space
    void *copy = malloc(content_size);
    if(copy == NULL){
        return NULL;
    }

    //Copy content
    memcpy(copy, content, content_size);

    //Check if node insertion succeeded
    void *response = add_node(root, copy);
    if(response == NULL){
        free(copy);
    }

    return response;
}

//Unlink node and free stored content
void delete_node_store(List *root, Node *node)
{
    free(node->content);
    delete_node(root, node);
}

//Free node and its content
static void free_node_store(Node *node)
{
    free(node->content);
    free(node);
}

//Delete all nodes on the list, free them and their contents
void delete_list_store(List *root)
{
    iterate(root, free_node_store);
    init_list(root);
}

Answer 1

1. You use root as parameter name when you pass the list around but I think a better name would just be list. root implies that you pass the first node of the list around rather than the container.

2. ++root->node_count is correct but root->node_count += 1 reads nicer (imho).

3. I would consider changing the interface slightly:

   1. Have a List* new_list() method which creates the list (and initializes the object).
   2. delete_list should also delete the list object (probably needs signature change to delete_list(List **list))
   3. Add a method clear_list which just clears the contents of the list.

4. Right now the programmer has to remember whether a node was added via add_node or add_node_store in order to call the proper delete function. However this could be solved by having a flag in nNode which indicates whether the node owns the content or not. Delete could then automatically do the right thing.

Answer 2

Your code is nicely written. A few minor points:

1. Sometimes you are over-commenting (comments that add nothing).

2. When calling through a function pointer, instead of writing this:

   (*function)(ite);
   

   you can just write the much clearer

   function(ite);
   

3. I would call nNode just node

A more significant point is that your iterations can break the list. During iteration you allow list nodes to be deleted (or added I guess). But the callback has no access to the list's node-count, as it has no access to the list itself. One solution would be to pass the list to the iteration function as well as the node.

I'd also prefer to see your uses of iteration (delete_list, delete_list_store) use the list manipulation functions (eg delete_node) as callbacks.

Finally, I also think that having separate methods of adding to the list (one that copies the data and one that doesn't) is confusing. I think I would stick to one public add_node function and make the list itself (rather than each node) either a copying list or a non-copying list via an extra field in List and a call parameter in new_list (a function suggested by @ChrisWue).