# Data Structures in C (Single Linked List)

NOTE: Added a follow-up question with the reviewed code

I am trying to get back to basics with C, so I am doing some data structures in it.

The following is my implementation of a Single Linked List (The code is on github with tests).

/*
* Author: antoniocs
*
* Created on 26 de Setembro de 2015, 19:54
*/

#ifdef  __cplusplus
extern "C" {
#endif

};

void *data;
};

typedef int (*LLFindCompareFuncPtr)(void *, void *);

#ifdef  __cplusplus
}
#endif



#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include "../../../dbg.h"

TAIL
};

struct LLFindNodeBaseParams {

void *data;
LLFindCompareFuncPtr compareFunc;

};

struct FindResult {
};

static struct FindResult *FindNodeBase(struct LLFindNodeBaseParams *);

typedef bool(*findByFuncPtr)(struct LLFindNodeBaseParams *, struct FindResult *, LinkedListNode *);
static bool FindByData(struct LLFindNodeBaseParams *, struct FindResult *, LinkedListNode *);
//To the outside this function is not really necessary
static bool FindByNode(struct LLFindNodeBaseParams *, struct FindResult *, LinkedListNode *);
static bool FindByNextNode(struct LLFindNodeBaseParams *, struct FindResult *, LinkedListNode *);
static struct FindResult *InitFindResult(void);
static bool FindResultSetResult(bool, struct FindResult *, LinkedListNode *);
//static struct LLFindNodeBaseParams *InitLLFindNodeBaseParams();

check(ll, "Unable to allocate memory for linked list");

ll->tail = NULL;

return ll;

error:
return NULL;
}

/**
*
* @param ll
* @param data
* @param type
* @return int (will be 1 for failure and 0 for sucess)
*/

} else {
} else {
ll->tail->next = node;
ll->tail = ll->tail->next;
}
}

return node;
error:
return NULL;
}

/**
*
* @param ll
* @param data
* @return
*/
}

/**
*
* @param ll
* @param data
* @return
*/
}

/**
*
* @param ll
* @param data
* @return
*/
}

/**
*
* @param data
* @param next
* @return
*/
check(lln, "Unable to allocate memory for linked list node");

lln->data = data;
lln->next = next;

return lln;
error:
return NULL;
}

}

return LLRemoveNode(ll, ll->tail);
}

void *data = node->data;
struct FindResult *res = LLFindNode(ll, node);

} else {
}
} else {
if (node == ll->tail) {
res->prev->next = NULL;
ll->tail = res->prev;
} else {
res->prev->next = node->next;
}
}

free(node);
return data;

error:
return NULL;
}

struct LLFindNodeBaseParams fnbParams = {
.ll = ll,
.node = node
};
struct FindResult *res = FindNodeBase(&fnbParams);
return res;
}

struct LLFindNodeBaseParams fnbParams = {
.ll = ll,
.data = data,
.compareFunc = func
};
struct FindResult *res = FindNodeBase(&fnbParams);

free(res);

return node;
}

struct LLFindNodeBaseParams fnbParams = {
.ll = ll,
.next = nodeNext
};
struct FindResult *res = FindNodeBase(&fnbParams);

free(res);

return node;
}

struct FindResult *FindNodeBase(struct LLFindNodeBaseParams *params) {
findByFuncPtr fptr = NULL;

if (params->data != NULL && params->compareFunc != NULL) {
fptr = FindByData;
} else if (params->node != NULL) {
fptr = FindByNode;
} else if (params->next != NULL) {
fptr = FindByNextNode;
} else {
goto error;
}

struct FindResult *res = InitFindResult();

check(res, "Unable to allocate memory for FindResult structure");
bool foundNode = false;

while (node != NULL) {
if ((foundNode = fptr(params, res, node))) {
break;
}
node = node->next;
}

if (foundNode == false) {
res->node = NULL;
res->prev = NULL;
}

return res;

error:
return NULL;
}

bool FindByData(struct LLFindNodeBaseParams *params, struct FindResult *res, LinkedListNode *node) {
return FindResultSetResult(params->compareFunc(params->data, node->data) == 0, res, node);
}

bool FindByNode(struct LLFindNodeBaseParams *params, struct FindResult *res, LinkedListNode *node) {
return FindResultSetResult(params->node == node, res, node);
}

bool FindByNextNode(struct LLFindNodeBaseParams *params, struct FindResult *res, LinkedListNode *node) {
return FindResultSetResult(params->next == node->next, res, node);
}

bool FindResultSetResult(bool condition, struct FindResult *res, LinkedListNode *node) {
if (condition) {
res->node = node;
} else {
res->prev = node;
}

return condition;
}

struct FindResult *InitFindResult() {
struct FindResult *res = malloc(sizeof (struct FindResult));
check(res, "Unable to allocate memory for FindResult");

res->node = NULL;
res->prev = NULL;

return res;

error:
return NULL;
}


Please tell me if anything seems off.

I also thought about creating separate files for each of the functions and then having one header file that would just combine everything. What are your thoughts on that?

All the tests are passing (you can see the test file in the github link provided)

Thanks!

• Please add the definition for the check thing, whatever it is; I have a feeling people might want to comment on that. – Mat Oct 14 '15 at 11:06
• Re-run your code with valgrind. On my machine it reports memory leaks: definitely lost: 72 bytes in 9 blocks, indirectly lost: 136 bytes in 17 blocks. You probably miss a few free(). – Arkadiusz Drabczyk Oct 14 '15 at 12:19
• @Mat Its one of Zed Shaws debug helpers. Its on github. But basically if the condition fails it will go to the error label – AntonioCS Oct 14 '15 at 18:11

1. You are currently creating a typedef-name and a struct tag with the same name (so far, so good), and then defining the struct, in the same header-file but separately.
Consider merging them:

typedef struct LinkedList {
/* lots of members here */

2. Why do you define a typedef for the comparison-function?

3. Also, are you really sure the pointers given to the user-supplied comparison-function should not be const-qualified?
4. Finally, why don't you allow for a context-pointer?

Just make it the same as qsort and qsort_s in the standard library.

Next, the sourcefile:

DRY (Don't Repeat Yourself)

2. Avoid sizeof(SomeType), use sizeof expression instead.
Thus the types cannot get out-of-sync.

There are many more good points in the other reviews.

• Thanks for this: 1 - I have fixed this. 2 - Why not? 3 - Good point will change it. 4 - Can you explain this a bit more please? Source file points: 1 - Sorry I don't understand what you mean by this. 2 - Will change this. – AntonioCS Oct 14 '15 at 18:10
• header-2: Well, such an alias can only be justified if it makes things simpler, and more than it adds cost by adding things to keep in mind. I doubt that here, especially as the callback is quite simple. header-4: Conforming to well-known interfaces, unless there's a good reason to diverge, is always a good idea. And you want to allow a context-pointer so iff your comparator can be configured or whatever, that doesn't break reentrancy or concurrency. source-1: If you define your helper-functions before first use, you can dispense with forward-declarations. Pointless duplication is pointless. – Deduplicator Oct 14 '15 at 18:21
• Regarding 2 I use that alias in other places, for example, in the struct LLFindNodeBaseParams. 4 - I am sorry but I am just not understanding what context-pointer means. I have seen the link and noticed that qsort_s had a 5th parameter named context but don't really understand what it means or how to use it. Do you have additional reading material or example where I could maybe better understand what you mean? Thanks – AntonioCS Oct 14 '15 at 18:44
• The fact that you use it repeatedly in the implementation should not show in the public interface. Regarding context-pointer, let's say the data sorted is a name. Now when you sort it, which locales sorting-rules do you use? That's an example of "context" the comparison-function might need to work properly. – Deduplicator Oct 14 '15 at 19:01
• @AntonioCS: Just be sure to make it a follow-up-question instead of an edit. Optionally, if you don't want to ask for a re-review, adding as an answer is also good. – Deduplicator Oct 14 '15 at 21:20

if (node == ll->head) {
} else {
}


ll->head becomes ll->head->next regardless of its NULLness. Code could be streamlined:

if (node == ll->head) {
ll->tail = NULL;
}


Similarly, in a general case the res->prev->next is also well-defined:

} else {
res->prev->next = node->next;
if (node == ll->tail) {
ll->tail = res->prev;
}
}

• Thanks so much for this. The logic does look a lot cleaner! – AntonioCS Oct 14 '15 at 18:21
/**
*
* @param ll
* @param data
* @param type
* @return int (will be 1 for failure and 0 for sucess)
*/

} else {
} else {
ll->tail->next = node;
ll->tail = ll->tail->next;
}
}

return node;
error:
return NULL;
}


Your documentation here is wrong. You say I get int back, and what I get back is... a LinkedListNode*.

if (node == ll->head) {
} else {
}
} else {
if (node == ll->tail) {
res->prev->next = NULL;
ll->tail = res->prev;
} else {
res->prev->next = node->next;
}
}


Else statement containing only an if-else chain, can be merged.

FindNodeBase silently fails with goto error and returning NULL if you provide it with bad params. You might want to replace this with a check(fptr, "Bad params for FindNodeBase, can't determine find function").

• Thanks so much for your great points. I have fixed all of them! – AntonioCS Oct 14 '15 at 18:22