Doubly-linked list implementation

Question

I've made an implementation of a doubly-linked list, I spend quite some time trying to get it right. I used both gdb and valgrind to make sure there was no memory leaks or errors. There's not a lot of comments in there, so sorry about that. There's still some things that bothers me in the code, like checking if 'head->prev' is null before appending to it. I'm sure there's must be a better way to implement that, like keeping a pointer to the first node. Also, I've got a list_init() function because I thought it was easier and more clean, but I may be wrong. I may be wrong a lot, so correct me if I am. I'm still not done with the implementation as I still want to add more functions to it, like a list_sort() or reverse_list(), but I'll wait for more input, just to see that I'm on the right track. Thanks!

list.c

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

#include "list.h"

node *list_init()
{
    node *node_t = calloc(1, sizeof(node));
    if (!node_t) {
        fprintf(stderr, "Allocation failed on list_init().\n");
        return NULL;
    }
    return node_t;
}

void list_append(node *node_t, char *data)
{
    /*
     * If there's no previous entry, then we're at the first item of the list.
     */
    if (!node_t->prev) {
        node_t->data = malloc(strlen(data) + 1);
        if (!node_t->data) {
            fprintf(stderr, "Allocation failed on list_add().\n");
        }
        strncpy(node_t->data, data, strlen(data) + 1);
        node_t->prev = node_t;
        return;
    }
    while (node_t->next) {
        node_t = node_t->next;
    }
    node_t->next = malloc(sizeof(node));
    if (!node_t->next) {
        fprintf(stderr, "Allocation failed on list_add().\n");
        return;
    }
    (node_t->next)->prev = node_t;
    node_t->next->data = malloc(strlen(data) + 1);
    if (!node_t->next->data) {
        fprintf(stderr, "Allocation failed on list_add().\n");
        return;
    }
    strncpy(node_t->next->data, data, strlen(data) + 1);
    node_t->next->next = NULL;
}

void list_print(node *node_t) 
{
    while (node_t) {
        printf("Value: %s\n", node_t->data);
        node_t = node_t->next;
    }
}

void list_remove_last(node *node_t)
{
    if (!node_t->next) {
        free(node_t);
        node_t->data = NULL;
        return;
    }
    while (node_t->next->next) {
        node_t = node_t->next;
    }
    free(node_t->next->data);
    free(node_t->next);
    node_t->next = NULL;
}

bool list_find(node *node_t, char *data) 
{
    while (node_t) {
        if (!strcmp(node_t->data, data)) {
            return true;
        }
        node_t = node_t->next;
    }
    return false;
}

void list_destroy(node *node_t) 
{
    node *current = NULL;
    while ((current = node_t)) {
        node_t = node_t->next;
        free(current->data);
        free(current);
    }
}

list.h

#ifndef __LIST_H__
#define __LIST_H__

#include <stdbool.h>

typedef struct node {
    char *data;
    struct node *prev, *next;
} node;


node *list_init();
void list_append(node *head, char *data);
void list_print(node *head);
void list_remove_last(node *head);
bool list_find(node *head, char *data);
void list_destroy(node *head);


#endif /* __LIST_H__  */

Answer 1

list_init should initialize all the members of the allocated node before returning. This way the caller won't have to remember to NULL out the pointers it isn't explicitly setting.

One way a doubly linked list can be implemented is to use a fake node to hold the list head and tail pointers. In your case, that node would always have a NULL data pointer, and initially the next and prev nodes would point to itself (this could be set up in a new list_create function, which could either initialize an already allocated node, or allocate and return a new one).

This would simplify list_append, as you'd already have a pointer to the last node, and you wouldn't need any extra code to handle an empty list (your current error handling in this case doesn't return after the fprintf, which will result in a crash). 'list_remove_last` would also be simplified.

Walking the list when using that fake node (like you do in list_print and list_find) would need a slightly different end condition. You'd start at the head, walk to the first node, then stop when you find a node with a NULL data pointer (which would mean you're back at the head node).

Your current list_destroy has one problem, where the variable that is passed to it still points at the (now deleted) list when it returns, so the caller needs to handle this. Using the fake node scheme, this would leave just the fake head node (which can be cleaned up via a list_destroy function).