Singly-linked list library

This is sort of a follow-up to a post I created about 10 days ago, but I have completed the implementation: Designing function prototypes for a singly-linked list API in C.

As I began to work on the implementation, I chose to change some of the functions and to move things around a little. This post includes source for the header, followed by the source code for the implementation.

There are 10 API functions.

Here is my number one concern: if I run Valgrind on a test file that does a lot of operations, I don't have any noticeable memory leaks, but Valgrind complains that sllist_destroy() performs an invalid free(). That is, it attempts to free something that is either already freed or not at the beginning of a heap block. This saddens me, as I cannot figure out why this is occurring. So please take careful notice of the sllist_destroy() function.

I'm also interested in opinions on opaque versus non-opaque. I have left the structs visible in the header for now, but I'm open to suggestions.

The third thing I'd like to have some feedback on is return points. I don't know how sane my choices are there, as I know some people advocate single exit points for functions.

Header: Please note that I am using Doxygen for documentation, so if you see something unfamiliar in my comments, it is because it is Doxygen syntax.

sllist.h

```
#ifndef SLLIST_H
#define SLLIST_H

/**
* @file sllist.h
* @brief Stuctures and functions for a singly-linked list API.
*
* The user is provided with several different functions to manipulate lists
* and associated data.
*/

/**
* The node structure.
*
* The purpose of this structure is to actually hold the data or "payload" to be
* stored in the list. The nodes are connected sequentially, and thus each node
* requires a second field to store the address of the next node.
*/
struct lnode {
void *data;
struct lnode *next;
};
/**
* The list structure.
*
* Metadata is contained here. A pointer to the firs

This is a clean and well documented API: There is little reason to have to read to the code to know how to use it. The only thing I see missing from the comment is any mention of what happens to the cursor (sllist.current) when the list is modified.

The memory error is because your code is pushing the same node onto the list twice:

sllist_push_front(nums, number);
sllist_push_back(nums, number);

In order for that to work, the second push will need its own malloc.

Multiple return points are only a problem if a function is too large for them to be easy to spot. The solution: Don't write large functions. Your functions are not too large, so it's not a problem.

The only suggestion I have would be not minor surgery, but a complete redesign. I'll mention it here not because it has anything to do with your question, but because you may not have considered it. Below the fold:

If you are able to switch to a doubly linked with with a dummy (root) node to serve as the head/tail, then linked list code can be simplified considerably, and most operations--such as insertion before or after an arbitrary node, or removing a node from a list--can be done very efficiently without any linear searches over the list, and with very little conditional logic.

struct Node {
  struct void *data;
  struct Node *prev;
  struct Node *next;
};

A special node is the "dummy" node, which serves as both the head and tail of the list (in this sketch I will ignore dynamic allocation). The root node is initialized like so:

void init_list(Node * node) {
  node->prev = node;
  node->next = next;
  node->data = NULL;     
}

The dummy/root node always has a NULL data pointer. A non-dummy node always has a non-NULL data pointer.

insertion after an arbitrary node is trivial:

void insert_after(Node * pred, Node * node) {
  node->pred = pred;
  node->next = pred->next;
  pred->next->pred = node;
  pred->next = node;
}

insertion before an arbitrary node:

void insert_before(Node * next, Node * node) {
  insert_after(next->pred, node);
}

The node being inserted before or after can be the dummy (root) node--the same logic works. Whether inserting at the head or tail, or before or after an arbitrary node, no list traversal is needed.

Return true if the node is a dummy (root) node. This is used to detect the end of list:

bool dummy_node(Node * node) {
  node->data == NULL;
}

One advantage of this structure is that no separate cursor (current node) is needed. Every node pointer is automatically a cursor.

Node * next_node(Node * node) {return node->next;}
Node * prev_node(Node * node) {return node->prev;}

Node * node = next_node(dummy);
while(!dummy_node(node))
  node = next_node(node);

The big disadvantage of this approach, compared to yours, is that a cursor is not integrated into the list. That means a cursor cannot be automatically invalidated when the list changes, as your code does. In every other way, I believe this approach to be simpler and more efficient to implement. It is, however, necessarily a complete redesign of the API. That's why it is out of scope in answering your original question.

StackExchange Code Review Q#26732, answer score: 4