Singly linked list in pure C - follow-up

Question

This is an update for this post.

I fixed all style-issues from the comments, but still have a few questions left:

• Someone commented that my last post contained too many functions, which could be easily implemented by the user of the library himself. Is this a basic enough set of functions? Is anything missing? (I hid the SLNode struct on purpose, since the user doesn't have to know how this list is implemented).
• The user currently doesn't free elements by himself (since the SLNode struct isn't exposed - he should use SLList_remove. Thus if he adds the same data to the list twice (without an extra malloc call) and removes one of the two nodes from the list, the data is freed and the left node points to data, which is not there. How should I manage this? Should I expose the SLNode?
• The library handles wrong input (NULL as list or invalid list index) by returning failure codes (-1). Or is undefined behavior more C-Stylish? - The user has to check for valid input and it's not my job.

Updated SLList.h

#ifndef SINGLYLINKEDLIST_
#define SINGLYLINKEDLIST_
#include <stdlib.h>
typedef struct SLList SLList;
// Create SinglyLinkedList
SLList *SLList_create(void);
// Get information about SinglyLinkedList
size_t SLList_length(SLList *list);
// Get data from SinglyLinkedList element
void *SLList_get(SLList *list, size_t index);
// Insert/remove elements from SinglyLinkedList
int SLList_insert(SLList *list, void *data, size_t index);
int SLList_remove(SLList *list, size_t index);
// Clear/free SinglyLinkedList
void SLList_clear(SLList *list);
void SLList_free(SLList *list);
#endif /* ifdef SINGLYLINKEDLIST_ */

Updated SLList.c

#include "SLList.h"
/***************************
 * UNEXPOSED FUNCTIONS *
 ***************************/
typedef struct SLNode SLNode;
struct SLList {
 SLNode *head;
 size_t length; 
};
struct SLNode {
 SLNode *next;
 void *data;
};
SLNode *SLNode_create(void *data);
void SLNode_free(SLNode *node);
SLNode *SLNode_create(void *data) {
 SLNode *node = calloc(sizeof(SLNode), 1);
 if (node != NULL) node->data = data;
 return node;
}
void SLNode_free(SLNode *node) {
 if (node == NULL) return;
 free(node->data);
 free(node);
}
/***************************
 * EXPOSED FUNCTIONS *
 ***************************/
/**
 * createSLList: Creates an SLList with default-
 * values (head: 0x0, length: 0).
 *
 * @return Pointer to createsSLList.
 * NULL on allocation failure.
 */
SLList *SLList_create(void) {
 return calloc(sizeof(SLList), 1);
}
/**
 * SLList_length: Returns current number of nodes in
 * SLList.
 * 
 * @param list SLList to return length from.
 *
 * @return Number of nodes in SLList.
 */
size_t SLList_length(SLList *list) {
 if (list == NULL) return 0;
 else return list->length;
}
/**
 * SLList_get: Get data from list element
 * at specific index.
 *
 * @param list SLList to search in.
 * @param index Index of element to look for.
 *
 * @return Element-data on success.
 * NULL on invalid arguments.
 */
void *SLList_get(SLList *list, size_t index) {
 if (list == NULL) return NULL;
 if (list->length <= index) return NULL;
 size_t i;
 SLNode *node = list->head;
 for (i = 0; i < index; i++) { node = node->next; }
 return node->data;
}
/**
 * slAdd: Add data to SLList.
 *
 * @param list SLList to add data to.
 * @param data Pointer to data, which should
 * be added to SLList (should be
 * allocated with malloc/calloc/etc.).
 * @param index Position in LList to add data
 * (Range between 0 and list->length).
 *
 * @return 0 on success.
 * -1 on failure (invalid input, allocation failure).
 */
int SLList_insert(SLList *list, void *data, size_t index) {
 if (list == NULL) return -1;
 else if (list->length < index) return -1;
 SLNode *node = SLNode_create(data); 
 if (node == NULL) return -1;
 if (index == 0) {
 node->next = list->head;
 list->head = node;
 } else {
 SLNode *prev = list->head;
 size_t i;
 for (i = 1; i < index; i++) { prev = prev->next; };
 node->next = prev->next;
 prev->next = node;
 }
 list->length++;
 return 0;
}
/**
 * slRemove: Remove data from SLList.
 *
 * @param list SLList to remove from.
 * @param index Index of element to remove
 * (Range between 0 and list->length-1);
 *
 * @return 0 on success.
 * -1 on failure (invalid input).
 */
int SLList_remove(SLList *list, size_t index) {
 if (list == NULL) return -1;
 if (list->length <= index) return -1;
 SLNode *node;
 if (index == 0) {
 node = list->head;
 list->head = node->next;
 } else {
 size_t i;
 SLNode *prev = list->head;
 for (i = 1; i < index; i++) {prev = prev->next; };
 node = prev->next;
 prev->next = node->next;
 }
 SLNode_free(node);
 list->length--;
 return 0;
}
void SLList_clear(SLList *list) {
 if (list == NULL) return;
 SLNode *node, *tmp;
 node = list->head;
 while (node != NULL) {
 tmp = node->next; 
 SLNode_free(node);
 node = tmp;
 }
 list->head = NULL;
 list->length = 0;
}
void SLList_free(SLList *list) {
 SLList_clear(list);
 free(list);
}

Answer 1

How does your user iterate the list?

Currently looping over the items in your list takes O(N²), since randomly accessing a single element via SLList_get() takes O(N). Linked lists iteration via jumping to each next element will allow looping in O(N).

I'd add to SLList.h:

typedef struct SLNode SLNode;
// Fetch a list node
SLNode* SLList_node(SLList *list, size_t index);
// For a given node, return the next or NULL if end of list
SLNode* SLList_next(SLNode *node);
// For a given node, return the data it stores
void* SLList_data(SLNode *node);

And to SLList.c:

SLNode* SLList_node(SLList *list, size_t index)
{
 size_t i;
 SLNode *node = list->head;
 for (i = 0; i < index && node; i++) { node = node->next; }
 return node;
}
SLNode* SLList_next(SLNode *node)
{
 return node->next;
}
void* SLList_data(SLNode *node)
{
 return node->data;
}
// SLList_get can be simplified now:
void *SLList_get(SLList *list, size_t index) {
 SLNode *node = SLList_node(list, index);
 return node->data;
}

Now your user can iterate very easily with:

SLNode *n;
for(n = SLList_node(list, 0); n; n = SLList_next(n)) {
 void *data = SLList_data(n);
 // do something with data
}

Don't play nice with bad inputs

I'm not sure what the point of SLList_remove() returning -1 is. The user has to test the return value. They could have just ensured/tested that list != NULL && index < SLList_length(list). You are not removing any burden from the user and the return can be better used (see next section).

The only exception I'd make to this is the SLList_node() function I added, which checks if an index is out of bounds of the list and returns NULL. This is required so the user knows when they've iterated to the end of the list.

Don't free the user's data

Safely freeing and cleaning up the data stored in the list may be more complex than calling free(node->data). node->data could be a FILE* that needs closing or a complex data structure that contains memory to be freed. It could have been allocated with a non-standard allocator. Instead I'd have SLList_remove() return the data that was in the node for the user to clean up themselves:

void* SLList_remove(SLList *list, size_t index);

Example usage:

void *data = SLList_remove(list, idx);
free(data);

Example user code to free the list

Since the user must be responsible for destroying the data that they created, I would remove SLList_clear(). So SLNode_free() becomes:

void SLNode_free(SLNode *node) {
 free(node);
}

User code to clear and free the list them becomes:

void *data;
while(data = SLNode_remove(list, 0)) { /* clean up data e.g. free(data); */ }
SLList_free(list);

Add a fast insertion function

I'd recommend implementing a fast insert function to insert a node after an existing node in O(1) instead of having to use SLList_insert() which is O(N).

// Insert data after an existing node
SLNode* SLList_add_after(SLList *list, SLNode *after, void *data) {
 SLNode *node = SLNode_create(data);
 if(!node) return NULL;
 node->next = after->next;
 after->next = node;
 list->length++;
 return node;
}

Edit: Added example user code to clear the list

• LastSecondsToLive: Wow, thank you really much! I didn't think about the O(n^2) iteration over the list. First I was a little skeptical to expose SLNode, but it makes sense and the O(1) insert is a great idea. Also the handling of the data is simple and appropriate. I'll need to let go of the input-validation, which is somehow hard for me, but it seems more C-like and if I think about it, it would be awful if this was always the case (error checking on math-operators and every single std-function). The user has to care for himself.
• LastSecondsToLive: How should I handle SLList_clear without freeing the data? Should I return nothing or should I create an array of void ** and return it?
• LastSecondsToLive: I have the same thoughts about SLList_free. Should it free the data or not?
• Isaac Turner: I'ved added example user code to free the list, without using SLList_clear() and updated SLList_free(). You could also add a helper function that free'd all nodes and the list but didn't free the SLNode->data pointers.