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.