Removing node from a linked list

Question

I'm implementing the singly linked list data structure and functions to work with it. In particular I'm concerned about prepending and removing nodes. Currently I defined linked list as follows:

typedef struct string_list_node{
    int id;
    const char *value;
    struct string_list_node *next;
} string_list_node_t;

string_list_node_t **string_list_alloc(int id, const char *value){
    string_list_node_t *string_list_ptr = malloc(sizeof(*string_list_ptr));
    string_list_node_t **list = malloc(sizeof(*list));
    string_list_ptr -> id = id;
    string_list_ptr -> value = value;
    string_list_ptr -> next = NULL;
    *list = string_list_ptr;
    return list;
}

The thing I'm concerned about is the following implementation of prepend and delete_first_by_id functions:

void prepend(int id, const char *value, string_list_node_t ** list_ptr){
    string_list_node_t *node_ptr = *list_ptr;
    string_list_node_t *prepended_node = malloc(sizeof(*prepended_node));
    prepended_node -> id = id;
    prepended_node -> value = value;
    prepended_node -> next = node_ptr;
    *list_ptr = prepended_node;
}

//returns 0 if not found, 1 if found and list changed
int delete_first_by_id(string_list_node_t **source, 
                       int id, 
                       string_list_node_t ** deleted_value_out){
    string_list_node_t *prev = NULL;
    string_list_node_t *current = *source;
    while(current && current -> id != id){
        prev = current;
        current = current -> next;
    }

    if(current){
        if(!prev){
            *source = current -> next;
            *deleted_value_out = current;
        } else {
            *deleted_value_out = current;
            prev -> next = current -> next;
        }
        return 1;
    } else {
        return 0;
    }
}

Is this code looks ok in terms of sort of common C style? Is the behavior of the code undefined? I created a live example of usage here:

LIVE DEMO

Answer 1

Style

• POSIX reserves type names ending with _t. This means that in the future, standard c may create standardized types with the same name as string_list_node_t, and your code would not compile. See https://stackoverflow.com/a/12727104 for more details. A common alternative is to use upper camel-case for typedefs, e.g. StringListNode.
• There is a strong case against typedefing structures. The major benefit of this is to save keystrokes, but it removes important information available to programmers. To see some opinions on this, here is another stack overflow question.
• I have never seen code that has spaces between -> when accessing struct members. Just use prepended_node->id instead. You wouldn't write prepended_node . id, would you?

Code Review

Use the bool type

A boolean type, bool, was introduced in C99. Unless you have really good reasons not to, you should use this for true/false values instead of an integer. This type is found in the <stdbool.h> header.

Multi-use functions

Finding nodes in a linked list is a relatively common procedure. If your list supports lookup, it is better to have a separate function that can handle all of your lookup cases:

static void _find_node_by_id(int id, str_node *head, 
                str_node **prev, str_node **node) {
  *prev = NULL;
  *node = head;
  while(node && (*node)->id != id) {
    *prev = *node;
    *node = (*node)->next;
  }
}

This way, you can use the search implementation in multiple places:

bool delete_first_by_id(string_list_node_t **source,
                       int id,
                       string_list_node_t ** deleted_value_out){
  string_list_node_t *prev = NULL;
  string_list_node_t *current = *source;

  _find_node_by_id(id, *source, &prev, &current);

  if(current){
    if(!prev){
      *source = current -> next;
      *deleted_value_out = current;
    } else {
      *deleted_value_out = current;
      prev -> next = current -> next;
    }
    return true;
  } else {
    return false;
  }
}

bool find_node_by_id(str_node *head, int id, str_node **return_ptr) {
  string_list_node_t *prev = NULL;
  *ret_ptr = head;

  _find_node_by_id(id, *source, &prev, return_ptr);

  if(*return_ptr) {
      return true;
  } else {
      return false;
  }
}

Note that I didn't test any of this code.

Try to avoid pointers to pointers

More specifically, don't use them when it's not necessary. There isn't a great reason for string_list_alloc to return string_list_node_t **. It makes much more sense to just return a pointer to the node. This does two things for you:

1. Non-destructive operations don't need a pointer to a pointer, so it avoids either you or the function from needing to deference them.
2. It makes destructive operations more explicit, as you need to take the address of the pointer to use the function.

Edit addressing question in comments:

In case I want to preserve it across different function calls I should not allocate it on the stack shouldn't I?

There seems to be some confusion on how malloced memory and pointers work, especially in the context of function return values.

First, remember that a variable holds a value. In this case, the variable contains a memory location, whose value could be any integer greater than or equal to 0. We really don't care about the variable itself, we care about its value.

Second, lets talk about return values. When you return a value from a function, it is copied so that the code calling the function has access to it. Here's a little program that illustrates this:

#include <stdio.h>

struct test_struct {
  int a;
  int b;
};

struct test_struct return_struct() {
  struct test_struct test = { .a = 1, .b = 2 };
  printf("The pointer in the function is: %p\n", &test);
  return test;
}

int main(void) {
  struct test_struct main_struct;
  main_struct = return_struct();
  printf("The pointer in main is: %p\n", &main_struct);
  return 0;
}

On my system, this program prints out

The pointer in the function is: 0x7fffef30f048
The pointer in main is: 0x7fffef30f070

Notice that the addresses are different. Since the value being returned is copied, we don't need to worry about manually manipulating memory, as the compiler takes care of that for us. It works the same way when returning a pointer from function: the value we care about is copied, so that we can access it when the variable that originally held it no longer exists.

Lets look at this in a different context.

// what your alloc function is doing:
int *malloc_add(int a, int b) {
    int *result = malloc(sizeof(result));
    *result = a + b;
    return result;
}
// what it should be doing:
int add(int a, int b) {
    int result;
    result = a + b;
    return result;
}

While we get the value we want in both cases, in the first we need to perform two extra steps: we need to dereference the pointer to get the value, and we need to free the memory allocated on the heap.