Revised C Doubly-Linked List

Question

I have revised the implementation I originally posted here. Thank you all who responded; I took your comments to heart. Please let me know if you have any additional feedback.

Here are some notes to make:

• I implemented all changes suggested by @vnp
• I implemented all by @chux, except for the "apply" function and the sample improvements (due to the improvements being fixed by changes suggested by @vnp)
• I implemented points (1), (5), (7) and (8) by Deduplicator

I am left with a couple questions, notably:

• Is it necessary to always include a header file even if the prototypes are not necessary? I noticed that in my case, it helped me catch a compile error because I did not originally forward declare the struct.
• It seems to me that it's possible to have undefined behavior even when using FAMs in a standard-compliant format ... though this likely wouldn't occur in my case due padding (on x86-64) not being needed within my structure
• Is it bad practice to use an _ at the end of internal functions (I even used this to overload a function name)?

I do not think there should be any bugs this time (hopefully) as I've taken care to modularize it heavily (which was the key advice in the other post -- due to lots of code repeat). Please let me know if you spot any. As before, I'm open to any and all advice -- whether it is general style, formatting or correctness.

I would appreciate any advice on how to unit test my data structures, as I am inexperienced when it comes to it, and might've caught the bug myself if I'd known how to in a structured format.

doubly-linked-list.h

#ifndef DOUBLY_LINKED_LIST
#define DOUBLY_LINKED_LIST
#include <stdbool.h>
struct dl_node_manager;
// Initialize the linked list.
void
dl_init(struct dl_node_manager *);
// Destroy the linked list.
void
dl_destoy(struct dl_node_manager *);
// Returns true if linked list is empty.
bool
dl_empty(struct dl_node_manager *);
// Insert node at head with value of @(const char *).
// May fail on allocation error.
bool
dl_insert_head(struct dl_node_manager *, const char *);
// Insert node at tail with value of @(const char *).
// May fail on allocation error.
bool
dl_insert_tail(struct dl_node_manager *, const char *);
// Return true if node with value of @(const char *) found.
// Will fail if node not found.
bool
dl_contains(struct dl_node_manager *, const char *);
// Remove node at head of linked list.
// Will fail if no nodes exist.
bool
dl_remove_head(struct dl_node_manager *);
// Remove node at tail of linked list.
// Will fail if no nodes exist.
bool
dl_remove_tail(struct dl_node_manager *);
// Remove first node found when traversing from head with value
// of @(const char*).
// Will fail if no nodes exist.
bool
dl_remove_node(struct dl_node_manager *, const char *);
#endif

doubly-linked-list.c

#include <string.h>
#include <stdlib.h>
#include <stdbool.h>
#include "doubly-linked-list.h"
// BEGIN: IMPLEMENTATION INTERNAL
struct dl_node
{
 char * str;
 struct dl_node * prev;
 struct dl_node * next;
};
struct dl_node_manager
{
 struct dl_node * head;
 struct dl_node * tail;
};
struct dl_node *
dl_create_node_(const char * str)
{
 struct dl_node * node = malloc(sizeof *node);
 if (!node)
 {
 return NULL;
 }
 node->str = strdup(str);
 if (!node->str)
 {
 free(node);
 return NULL;
 }
 return node;
}
bool
dl_remove_node_(struct dl_node_manager * manager, struct dl_node * node)
{
 if (!node)
 return false;
 if (node->next && node->prev)
 {
 // Middle node.
 node->prev->next = node->next;
 node->next->prev = node->prev;
 }
 else if (node->next)
 {
 // Head node with a node after.
 node->next->prev = NULL;
 manager->head = node->next;
 }
 else if (node->prev)
 {
 // Tail with a node before.
 node->prev->next = NULL;
 manager->tail = node->prev;
 }
 else
 {
 // Only node.
 manager->tail = NULL;
 manager->head = NULL;
 }
 free(node->str);
 free(node);
 return true;
}
// END: IMPLEMENTATION INTERNAL
void
dl_init(struct dl_node_manager * manager)
{
 manager->head = NULL;
 manager->tail = NULL;
}
void
dl_destroy(struct dl_node_manager * manager)
{
 for (struct dl_node * tmp = manager->head;
 tmp;
 tmp = tmp->next)
 dl_remove_node_(manager, tmp);
}
bool
dl_empty(struct dl_node_manager * manager)
{
 return !manager->head;
}
bool
dl_insert_head(struct dl_node_manager * manager, const char * str)
{
 struct dl_node * node = dl_create_node_(str);
 if (!node)
 return false;
 node->next = manager->head;
 if (!manager->head)
 manager->tail = node;
 else
 manager->head->prev = node;
 manager->head = node;
 return node;
}
bool
dl_insert_tail(struct dl_node_manager * manager, const char * str)
{
 struct dl_node * node = dl_create_node_(str);
 if (!node)
 return false;
 node->prev = manager->tail;
 if (!manager->tail)
 manager->head = node;
 else
 manager->tail->next = node;
 manager->tail = node;
 return node;
}
bool
dl_contains(struct dl_node_manager * manager, const char * str)
{
 for (struct dl_node * tmp = manager->head;
 tmp;
 tmp = tmp->next)
 if (strcmp(tmp->str, str) == 0)
 return true; 
 return false;
}
bool
dl_remove_head(struct dl_node_manager * manager)
{
 if (!manager->head)
 return false;
 return dl_remove_node_(manager, manager->head);
} 
bool
dl_remove_tail(struct dl_node_manager * manager)
{
 if (!manager->tail)
 return false;
 return dl_remove_node_(manager, manager->tail);
}
 
bool
dl_remove_node(struct dl_node_manager * manager, const char * str)
{
 for (struct dl_node *tmp = manager->head;
 tmp;
 tmp = tmp->next)
 if (strcmp(tmp->str, str) == 0)
 return dl_remove_node_(manager, tmp);
 return false;
}

Answer 1

1. Manager is a bad word, because it means everything and nothing.
   Case in point, your particular node_manager is a doubly-linked-list, though from the name it could be singly linked, a tree, an arbitrary graph, ...

2. Your data-structure currently consists of a chain of nodes, and pointers to the first and last (if existing).

   The problem with this is that the first, last, and only node must be special-cased for inserting and deleting.

   1 Element 0 Elements 2+ Elements
   | # List # | | 0 0 List | | # List # |
    | | | |
    +----+ | +-+ +----------+
    | | | |
    v v v v
   0 <-> Node_1 <-> 0 0 <-> Node_1 <-> ... <-> Node_n <-> 0
   

   If you used a full circular list instead, there would be no special cases.

   1 Element 0 Elements 2+ Elements
   +--> List <--+ +--> List <--+ +--> List <-> Node_1 <----------+
   | | | | | |
   +-> Node_1 <-+ +------------+ +-> Node_n <-..(-> Node_2 <-)..-+
   

   To avoid dummy-payloads, your node would need to use a flexible array member for the payload, or you would have to create a new type to encapsulate just the links, and have it as a member for list and nodes, preferably first for easy casting.

3. Separate finding a node from removing it. They are different tasks, and there might be many diffent useful criteria for the former.

4. A const char* is a pointer, a simple data type. A 0-terminated string (often just string) is a data structure, specifically a 0-terminated sequence of non-0 characters, something much more complex. Even though to use the latter you generally point at it with the former, they are distinctly different.

5. If someone wants to use dl_init(), they need to define a dl_node_manager, which means they need the definition. That definition is currently hidden in the implementation file.

   Either remove the init-function and replace it with a create-function which allocates it dynamically, or move the definition.

• user129393192: (5) I will allocate for them and destruct it, thanks for noticing. (4) You mean this to say I should simply call it a "string" in my comments? (2) that sounds like a different implementation, but I will likely do it also for practice. (3) What do you mean by separate, if you mean the dl_remove_node function? For (1) I stated dl_node_manager, what would you suggest for the name? (X) I notice you didn't mention me overloading dl_remove_node with dl_remove_node_ internally, so I take that as that is fine.
• Deduplicator: 4) yes. 2) It is significantly different. 3) Yes, but currently it isn't part of the API, nor are helpers for freely iterating. 1) dl_list seems appropriate. X) That is not in itself bad, though following 3 would change it anyway.
• user129393192: (X) I followed (3) and created a dl_find_node_ function, but that did not change dl_remove_node_, that was still a needed function. Thanks for your help. I think the code is significantly better. The most complex was definitely the dl_remove_node_ function. Also, (3) I didn't make it a part of API because I thought the nodes in the list should be transparent to the programmer. Maybe that's just a design decision?
• Deduplicator: How then would you remove the 2nd of 3 nodes with value x? The good thing about having an iterator-interface isn't the interface itself, but that it can be used to build whatever you want on top.