Linked list C implementation

Question

I'm reading a data structure and algorithm book in C. I have implemented a generic single linked list in the C programming language, and I want to know your opinion on my implementation:

linked_list.h

#ifndef LINKED_LIST_H_INCLUDED
#define LINKED_LIST_H_INCLUDED
#define list_size(list) (list->size) 
#define list_head(list) (list->head) 
#define list_tail(list) (list->tail)
#define list_is_head(list, element) (element == list_head(list))
#define list_is_tail(list, element) (element == list_tail(list))
#define list_append(list, data) list_ins_next(list, list->tail, data)
#define list_preprend(list, data) list_ins_next(list, NULL, data)
#define list_data(element) (element->data)
#define list_next(element) (element->nextElmt)
typedef struct ListElmt_{
 void *data;
 struct ListElmt_ *nextElmt;
} ListElmt;
typedef struct List_{
 ListElmt *head;
 ListElmt *tail;
 size_t size; 
 void (*destroy)(void *data);
 int (*cmp)(const void *fdata,const void *sdata);
}List;
List *list_init(void (*destroy)(void *data), 
 int (*cmp)(const void *fdata, const void *sdata));
void list_destroy(List *list);
int list_ins_off(List *list, size_t off, void *data); 
int list_ins_next(List *list, ListElmt *element, void *data); 
int list_drem_next(List *list, ListElmt *element);
int list_rem_next(List *list, ListElmt *element, void ** data);
ListElmt * list_find(List *list, void *data, ListElmt *sElmt);
#endif

linked_list.c

#include <stdlib.h>
#include "linked_list.h" 
List * list_init(void (*destroy)(void *data),
 int (*cmp)(const void *fdata, const void *data)) 
{ 
 List *rlist;
 if((rlist = malloc(sizeof *rlist)) != NULL) { 
 rlist->head = NULL; 
 rlist->tail = NULL; 
 rlist->size = 0; 
 rlist->destroy = destroy; 
 rlist->cmp = cmp;
 }
 return rlist;
} 
void list_destroy(List *list) {
 ListElmt * el;
 void *data;
 while( (el=list_head(list)) != NULL) {
 list_rem_next(list, NULL, &data);
 list->destroy(data);
 }
 free(list);
}
int list_ins_next(List *list, ListElmt *elmt, void *data) {
 ListElmt *addElmt = malloc(sizeof *addElmt);
 if(addElmt == NULL)
 return -1;
 addElmt->data = data;
 if(elmt == NULL) {
 addElmt->nextElmt = list->head;
 elmt = list->head = addElmt; // using elmt for checking list tail
 }
 else {
 addElmt->nextElmt = elmt->nextElmt;
 elmt->nextElmt = addElmt;
 }
 // updating list->tail if needed
 if(elmt == list->tail)
 list->tail = addElmt;
 list->size++;
 return 0;
}
int list_ins_off(List *list, size_t off, void *data) {
 if(off < 0 || off >= list->size)
 return list_append(list, data);
 size_t i;
 ListElmt *elmt = NULL;
 for(i = 0; i < off; ++i)
 elmt = elmt->nextElmt;
 list_ins_next(list, elmt, data);
 return 0;
}
int list_drem_next(List *list, ListElmt *element) {
 void *data;
 int ret = list_rem_next(list, element, &data);
 if(ret != 0)
 return ret;
 list->destroy(data);
 return 0;
}
int list_rem_next(List *list, ListElmt *element, void **data) {
 ListElmt *remElmt;
 // the list still not contain any element
 if(list->size == 0 || element->nextElmt == NULL) 
 return -1;
 *data = element->nextElmt->data;
 remElmt = element->nextElmt;
 element->nextElmt = element->nextElmt->nextElmt;
 if(remElmt == list->tail)
 list->tail = element;
 free(remElmt);
 list->size--;
 return 0;
}
ListElmt * find(List *list, void *data, ListElmt *sElmt) {
 if(list->size == 0 || list->cmp == NULL) 
 return NULL;
 sElmt = sElmt ? sElmt : list_head(list); 
 while(sElmt && list->cmp(sElmt->data, data))
 sElmt = sElmt->nextElmt;
 return sElmt;
} 

Answer 1

In order of appearance:

• list_init

  While destroy is definitely a property of the list, cmp is not; it is a property of a particular searc. Only find really cares of how to compare elements. It is better to pass a comparator to find directly.

• list_desroy

  may and should take advantage of knowing the list size. If perchance the list is corrupted, it is possible that the (el=list_head(list)) != NULL condition is never satisfied, and the loop becomes infinite. Counting iterations gives you an ability to fail gracefully.

• Insertions

  Naming is questionable. list_ins_next should be list_insert_after; list_ins_off should be list_insert_at. In any case, do not abbreviate insert.

• Removals

  The purpose of list_drem_next is quite unclear. Why to destroy data of the next element? It is much more straightforward to destroy data of this element. In any case, you must nullify the data pointer once data are destroyed.

  The name itself is also questionable. list_destroy_data sounds better.

• Missing functionality

  There is no way to remove the head element.

Answer 2

1. (削除) Your list_init contains a rather nasty bug: If malloc fails it will return rList unitialized which means the caller won't know that the list wasn't properly initialized and gets a pointer into lala land. If he is lucky it will crash the program if not it will start overwriting random memory which can lead to very hard to to debug crashes in totally unrelated and perfectly fine code. Granted if malloc fails then there is a good chance your program will die anyway but you should not return uninitialized variables (your compiler should actually warn you about this). If malloc fails either return NULL or abort(). (削除ここまで)

2. Your naming of variables and methods is a little bit terse and/or unconventional.

   • It won't hurt to properly name things. Abbreviating things like ins, drem etc. do not help readability.
   • ListElmt is typically called Node or ListNode. At least name it ListElement - again avoid abbreviations in type names. Modern IDEs do a pretty good job of code completion and any modern compiler can easily deal with the few extra characters.

3. The biggest issue is your interface. The header file should be the public interface to your data structure - anything which is private (helpers etc.) should not be in there.

   • You have defined all your operations to operate on a list - this is perfectly fine. This also means that your should consider using an opaque pointer hiding the implementation details from the user of your structure. The advantage is that you can change implementation details without worrying about breaking any existing code which might rely on some internals.

   • Your set of operations seem a bit strange. For example you have a method which finds an element and returns the pointer to it but you only have methods to remove the next element to the one you point to. So how do you find and element and delete it?

4. There is a bunch of helper macros defined (like list_head, list_tail, etc.) which you sometimes use sometimes not. This is inconsistent. If they are meant for the user of the list then see the point above: the user should not know about these kind of internals anyway.

• KarimS: ok thanks you, 1) if malloc fail it will return NULL that will be assigned to rlist anyway. 2)where can i put my helper so that there are hidden from the public interface??
• ChrisWue: @karim, good point, missed the =. You can simply move the method prototype into the .c file and mark the implementation static so it's not visible outside the .c file.

Answer 3

Personal suggestion: I don't really like using macros unless I have to, so I would suggest using inline functions for the short one-liner list methods that are currently implemented as macros. The main advantages would be actual type checking and better compiler error messages if you make a mistake when writing the code.

---

The function pointers cmp and destroy appear in a couple different places. It is a good idea to replace those with typedefs to avoid a typo in any of the repeated declarations and to simplify maintenance if you ever need to change the function signature:

typedef void (*func_destroy) (void *data);
typedef int (*func_compare) (const void *fdata, const void *sdata);

---

Integer return codes are pretty old school, in my opinion. Returning 0 on success and -1 on error is an invitation to confusion. A programmer that didn't bother reading the documentation or looking at the source code might just assume it is returning a boolean 0|1 value and call your function like this:

if ( list_rem_next(...) )
{
 // nice, it worked
}

And never realize that the if statement would not be executed at any point.

A better interface, in the simple case of a list, would be including <stdbool.h> and changing the return value of the functions to bool, returning true on success and false on error.

---

It is a good practice when using pointers to always validate them before accessing the pointed contents. You should at least assert in every function that the list pointers and others are not NULL.