Data structures in C (doubly linked list)

Question

Continuing from my last question I have now implemented a Double Linked list. All the code (with tests) is also available on GitHub.

DobLinkedList.h

#include <stdio.h>
#include <stdbool.h>
#ifndef DobLINKEDLIST_H
#define DobLINKEDLIST_H
#ifdef __cplusplus
extern "C" {
#endif
 typedef struct DobLinkedListNode {
 void *data;
 struct DobLinkedListNode *prev;
 struct DobLinkedListNode *next;
 } DobLinkedListNode;
 typedef struct DobLinkedList {
 DobLinkedListNode *head;
 DobLinkedListNode *tail;
 unsigned int nodeCount;
 } DobLinkedList;
 DobLinkedList *DobLLInit();
 DobLinkedListNode *DobLLAddHead(DobLinkedList *, void *);
 DobLinkedListNode *DobLLAddTail(DobLinkedList *, void *);
 DobLinkedListNode *DobLLAdd(DobLinkedList *, void *);
 void *DobLLRemoveHead(DobLinkedList *);
 void *DobLLRemoveTail(DobLinkedList *);
 void *DobLLRemoveNode(DobLinkedList *, DobLinkedListNode *);
 DobLinkedListNode *DobLLFindNodeByData(DobLinkedList *, void *, bool (*comp)(const void *, const void *));
 DobLinkedListNode *DobLLFindNodeByNext(DobLinkedList *, DobLinkedListNode *);
 DobLinkedListNode *DobLLFindNodeByPrev(DobLinkedList *, DobLinkedListNode *);
#ifdef __cplusplus
}
#endif
#endif /* DobLINKEDLIST_H */

DobLinkedList.c

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include "DobLinkedList.h"
#include "../../../dbg.h"
/**
 * Initialize a linked list
 *
 * @return LinkedList *
 */
DobLinkedList *DobLLInit() {
 DobLinkedList *dobll = malloc(sizeof (DobLinkedList));
 check(dobll, "Unable to allocate memory for Double Linked List");
 dobll->head = NULL;
 dobll->tail = NULL;
 dobll->nodeCount = 0;
 return dobll;
error:
 return NULL;
}
//<editor-fold defaultstate="collapsed" desc="Add Functions">
enum AddStrategy {
 HEAD,
 TAIL
};
static DobLinkedListNode *NodeInit(void *data, DobLinkedListNode *prev, DobLinkedListNode *next) {
 DobLinkedListNode *doblln = malloc(sizeof (DobLinkedListNode));
 check(doblln, "Unable to allocate memory for linked list node");
 doblln->data = data;
 doblln->prev = prev;
 doblln->next = next;
 return doblln;
error:
 return NULL;
}
static DobLinkedListNode *DobLLAddBase(DobLinkedList *dobll, void *data, enum AddStrategy stype) {
 check(dobll, "LLAddBase received null pointer");
 DobLinkedListNode *node = NodeInit(data, NULL, NULL);
 if (dobll->head == NULL) {
 dobll->tail = dobll->head = node;
 } else {
 if (stype == HEAD) {
 node->next = dobll->head;
 dobll->head->prev = node;
 dobll->head = node;
 } else {
 dobll->tail->next = node;
 node->prev = dobll->tail;
 dobll->tail = node;
 }
 }
 dobll->nodeCount++;
 return node;
error:
 return NULL;
}
DobLinkedListNode *DobLLAddHead(DobLinkedList *dobll, void *data) {
 return DobLLAddBase(dobll, data, HEAD);
}
DobLinkedListNode *DobLLAddTail(DobLinkedList *dobll, void *data) {
 return DobLLAddBase(dobll, data, TAIL);
}
DobLinkedListNode *DobLLAdd(DobLinkedList *dobll, void *data) {
 return DobLLAddTail(dobll, data);
}
//</editor-fold>
//<editor-fold defaultstate="collapsed" desc="Remove functions">
void *DobLLRemoveHead(DobLinkedList *dobll) {
 return DobLLRemoveNode(dobll, dobll->head);
}
void *DobLLRemoveTail(DobLinkedList *dobll) {
 return DobLLRemoveNode(dobll, dobll->tail);
}
void *DobLLRemoveNode(DobLinkedList *dobll, DobLinkedListNode *node) {
 void *data = node->data;
 if (node == dobll->head) {
 dobll->tail = dobll->head = dobll->head->next;
 if (dobll->head) {
 dobll->head->prev = NULL;
 }
 } else {
 node->prev->next = node->next;
 if (node == dobll->tail) {
 dobll->tail = node->prev;
 }
 else {
 node->next->prev = node->prev;
 }
 }
 dobll->nodeCount--;
 free(node);
 return data;
}
//</editor-fold>
//<editor-fold defaultstate="collapsed" desc="Find functions">
DobLinkedListNode *DobLLFindNodeByData(DobLinkedList *dobll, void *data, bool(*comp)(const void *, const void *)) {
 DobLinkedListNode *current = dobll->head;
 while (current != NULL) {
 if (comp(data, current->data) == true) {
 break;
 }
 current = current->next;
 }
 return current;
}
//</editor-fold>

• cafe_: Consider using pointers to pointers when deleting nodes.
• AntonioCS: @xrthdsf Hey, could you please give more details on the approach you are suggesting? Thanks

Answer 1

Bug

In your node removal code, you have this:

if (node == dobll->head) {
 dobll->tail = dobll->head = dobll->head->next;

You should only be setting tail if tail and head are the same node.

Possible NULL dereference

Your DobLLRemoveHead() andDobLLRemoveTail() functions currently don't check if there are actually any nodes to remove. If the list is empty, calling those functions will result in a NULL dereference and crash.

Answer 2

I can't tell what check() is supposed to do (assuming it's part of dbg.h) nor can I tell if they have anything to do with the error: labels. Labels are usually used along with gotos, but there aren't any in the code. If code execution never reaches them, then you may have to use a conditional to determine whether or not the functions should return NULL.