Linked list implementation

Question

I wrote some code for linked lists and would like to know what things could/should be done differently.

I'm using an index to keep track of the most important information and have 2 sets of functions, one to use the list just to point to data and the other to store the data in the list.

Here's the code so far:

#include <stdlib.h>
#include <string.h>
//Basic structure
typedef struct nNode Node;
struct nNode {
 void *content;
 Node *next;
 Node *previous;
};
//An index will make everything simpler
typedef struct {
 Node *first;
 Node *last;
 size_t node_count;
} List;
//Initialize list index with default values
void init_list(List *root)
{
 root->first = NULL;
 root->last = NULL;
 root->node_count = 0;
}
//Link new element and return pointer to it if successful or NULL
Node *add_node(List *root, void *content)
{
 Node *temp = malloc(sizeof(Node));
 if(temp == NULL){
 return NULL;
 }
 //Fill node 
 temp->content = content;
 temp->next = NULL;
 temp->previous = root->last; //NULL if first node
 //Handle first element insertion
 if(root->first == NULL){
 root->first = temp;
 }
 //Or update previous element
 else {
 root->last->next = temp;
 }
 //Update index
 root->last = temp; 
 ++root->node_count;
 return temp; 
}
//Unlink element, always successful
void delete_node(List *root, Node *node)
{
 //If it's the first, update index reference
 if(node->previous == NULL){
 root->first = node->next;
 }
 //Or it's safe to update previous node
 else {
 node->previous->next = node->next;
 } 
 //If it's the last, update index reference
 if(node->next == NULL){
 root->last = node->previous;
 }
 //Not the last? Safe to update next node
 else {
 node->next->previous = node->previous;
 }
 //Update count and free memory
 free(node);
 --root->node_count;
}
//Iterate through all nodes and call a function on every iteration
void iterate(const List *root, void(*function)(Node*))
{
 Node *next; //store in case the node changes
 for(Node *ite = root->first; ite != NULL; ite = next){
 next = ite->next;
 (*function)(ite);
 }
}
//Iterate through all nodes backwards and call a function on every iteration
void iterate_backwards(const List *root, void(*function)(Node*))
{
 Node *previous; //store in case the node changes
 for(Node *ite = root->last; ite != NULL; ite = previous){
 previous = ite->previous;
 (*function)(ite);
 }
}
//Delete all elements in the list
void delete_list(List *root)
{
 iterate(root, (void(*)(Node*))free);
 init_list(root);
}
////////////////
////// The following functions also store the content in the list
///// instead of just pointing to it. They should be used together
//// in order to avoid memory leaks.
/////////////
//Add node and store a copy of content
Node *add_node_store(List *root, const void *content, size_t content_size)
{
 //Allocate space
 void *copy = malloc(content_size);
 if(copy == NULL){
 return NULL;
 }
 //Copy content
 memcpy(copy, content, content_size);
 //Check if node insertion succeeded
 void *response = add_node(root, copy);
 if(response == NULL){
 free(copy);
 }
 return response;
}
//Unlink node and free stored content
void delete_node_store(List *root, Node *node)
{
 free(node->content);
 delete_node(root, node);
}
//Free node and its content
static void free_node_store(Node *node)
{
 free(node->content);
 free(node);
}
//Delete all nodes on the list, free them and their contents
void delete_list_store(List *root)
{
 iterate(root, free_node_store);
 init_list(root);
}

Answer 1

1. You use root as parameter name when you pass the list around but I think a better name would just be list. root implies that you pass the first node of the list around rather than the container.

2. ++root->node_count is correct but root->node_count += 1 reads nicer (imho).

3. I would consider changing the interface slightly:

   1. Have a List* new_list() method which creates the list (and initializes the object).
   2. delete_list should also delete the list object (probably needs signature change to delete_list(List **list))
   3. Add a method clear_list which just clears the contents of the list.

4. Right now the programmer has to remember whether a node was added via add_node or add_node_store in order to call the proper delete function. However this could be solved by having a flag in nNode which indicates whether the node owns the content or not. Delete could then automatically do the right thing.

Answer 2

Your code is nicely written. A few minor points:

1. Sometimes you are over-commenting (comments that add nothing).

2. When calling through a function pointer, instead of writing this:

   (*function)(ite);
   

   you can just write the much clearer

   function(ite);
   

3. I would call nNode just node

A more significant point is that your iterations can break the list. During iteration you allow list nodes to be deleted (or added I guess). But the callback has no access to the list's node-count, as it has no access to the list itself. One solution would be to pass the list to the iteration function as well as the node.

I'd also prefer to see your uses of iteration (delete_list, delete_list_store) use the list manipulation functions (eg delete_node) as callbacks.

Finally, I also think that having separate methods of adding to the list (one that copies the data and one that doesn't) is confusing. I think I would stick to one public add_node function and make the list itself (rather than each node) either a copying list or a non-copying list via an extra field in List and a call parameter in new_list (a function suggested by @ChrisWue).

• 2013Asker: +1 Thanks for your feedback, I didn't know it was possible to call function pointers like that and didn't really think about the struct name, I already changed those. Your other points also look right. But why use the functions delete_list and delete_list_store instead of free() if the memory will be free'd anyway and the entire list deleted?
• William Morris: Just that the way you currently do it breaks the list (wrong node count) for the duration of the iteration. And I think it is best of only one function needs to know how to delete an entry from the list.
• user61611: Can you give an example of where in this code, the author is "over-commenting"?
• William Morris: @franklin How many comments can you find that tell you something you didn't already know (from the code that follows)? Some are worse than others - saying "allocate memory" before a malloc call clearly adds something only for a reader who doesn't recognize malloc. For everyone else it is just noise.