Linked List written in C

Question

I have been learning data structures and dynamic memory allocation in C. As a learning experience, I have written this linked list implementation. I really appreciate the feedback I've received on the previous code I've posted here and would love to hear any suggestions you all have on improvements I can make to this.

I have abstracted the design to practice the use of "opaque pointers", and have thoroughly commented and described each function in the code. Tests for all functions are in main.c

Below are the source files and the CMakeLists file (which includes many runtime Clang sanitizers enabled). Alternatively, the code can be easily compiled with the following: cc *.c -o linkedlist && ./linkedlist

linkedlist.h

#ifndef DATASTRUCTURES_LINKEDLIST_H
#define DATASTRUCTURES_LINKEDLIST_H

// Incomplete type used for "opaque pointer"
struct Node;

/*
 * I typedef this struct for ease of use in the header file.
 * There are both benefits and harms from assigning a typedef
 * to a struct but in this scenario I see more benefits.
 */
typedef struct Node Node;

/**
 * Get node value (caller is responsible for ensuring node isn't NULL)
 * @param node
 * @return int value
 */
int get_node_val(const Node *node);

/**
 * Set node value (caller is responsible for ensuring node isn't NULL)
 * @param node
 * @param val - int value
 */
void set_node_val(Node *node, int val);

/***
 * Allocates memory for a node, and assigns data to the new node
 * @param data - integer to store in the new node
 * @return newly allocated node
 */
Node *create_node(int data);

/**
 * Appends a node to the end of the linked list
 * @param head - first node
 * @param to_add - node to add
 * @return head node
 */
Node *append_node(Node *head, Node *to_add);

/**
 * Prepends a node to the beginning of the linked list
 * @param head  - first node
 * @param to_add - node to add (becomes the new first node)
 * @return head node - should be reassigned to head
 */
Node *prepend_node(Node *head, Node *to_add);

/**
 * Searches for a value in the linked list
 * @param head - first node
 * @param search_val - value to search for
 * @return instance of node if it exists, or NULL if it doesn't exist
 */
Node *search_node(const Node *head, int search_val);

/**
 * Deletes the first occurence of "delete_val" from the linked list
 * @param head - first node
 * @param delete_val - value to delete from the linked list (may be head node)
 * @return head node - should be reassigned to head in case of first node being deleted
 */
Node *delete_node(Node *head, int delete_val);

/**
 * Prints each node in the linked list
 * @param head - first node to start traversing from
 */
void print_all(const Node *head);

/**
 * Frees all member of the linked list
 * @param head - first node to start traversing from
 */
void free_all(Node *head);

#endif //DATASTRUCTURES_LINKEDLIST_H

linkedlist.c

#include <malloc.h>
#include "linkedlist.h"
#include "utils.h"

struct Node {
    int value;
    struct Node *next;
};

int get_node_val(const Node *node) {
    return node->value;
}

void set_node_val(Node *node, int val) {
    node->value = val;
}

static size_t node_size(void) {
    return sizeof(struct Node);
}

static void *allocate_node(void) {
    return malloc(node_size());
}

Node *create_node(int data) {
    Node *new_node;
    if ((new_node = allocate_node()) == NULL) {
        gracefully_handle_failure();
    }
    new_node->value = data;
    new_node->next = NULL;
    return new_node;
}

Node *append_node(Node *head, Node *to_add) {
    if (head == NULL) {
        return NULL;
    }
    Node *current = head;
    while (current->next) {
        current = current->next;
    }
    // At the end, now let's add our new node
    current->next = to_add;
    to_add->next = NULL;
    return head;
}

Node *prepend_node(Node *head, Node *to_add) {
    to_add->next = head;
    head = to_add;
    return head;
}

Node *search_node(const Node *head, int search_val) {
    for (const Node *current = head; current != NULL; current = current->next) {
        if (current->value == search_val) {
            return (Node *) current;
        }
    }
    return NULL;
}

Node *delete_node(Node *head, int delete_val) {
    // Taken from "Linus Torvalds - The mind behind Linux" Ted Talk
    // https://youtu.be/qrYt4bbEUrU
    Node **indirect = &head;
    while ((*indirect)->value != delete_val)
        indirect = &(*indirect)->next;

    *indirect = (*indirect)->next;
    return head;
}

void print_all(const Node *head) {
    for (const Node *current = head; current != NULL; current = current->next) {
        printf("%d -> ", current->value);
    }
    puts("NULL");
}

void free_all(Node *head) {
    for (Node *current = head; current != NULL; current = current->next) {
        free(head);
    }
}

main.c

#include <stdio.h>
#include <stdlib.h>
#include "linkedlist.h"

int main() {
    // These are simply tests for the Linked List
    Node *head = create_node(12);
    // Add 20 after head node (12)
    append_node(head, create_node(20));
    // 12 -> 20 -> NULL
    // Prepend 30 before head node (12)
    head = prepend_node(head, create_node(30));
    printf("Head is %d\n", get_node_val(head));
    set_node_val(head, 32);
    // 32 -> 12 -> 20 -> NULL
    print_all(head);
    head = delete_node(head, 32);
    // 12 -> 20 -> NULL
    if (search_node(head, 20)) {
        printf("%d found\n", 20);
    }
    print_all(head);
    free_all(head);
    return EXIT_SUCCESS;
}

CMakeLists.txt

# Improved version adapted from https://codereview.stackexchange.com/a/210770/78786
cmake_minimum_required(VERSION 3.13)
project(DataStructures C)

add_executable(${CMAKE_PROJECT_NAME} main.c linkedlist.c linkedlist.h utils.c utils.h)

set(CMAKE_C_COMPILER clang)
target_compile_features(${CMAKE_PROJECT_NAME} PRIVATE c_std_99)
target_compile_options(${CMAKE_PROJECT_NAME} PRIVATE
        $<$<C_COMPILER_ID:Clang>:
        -Weverything
        -fsanitize=undefined,integer,implicit-conversion,nullability,address,leak,cfi
        -flto
        -fvisibility=default>)
target_link_options(${CMAKE_PROJECT_NAME} PRIVATE
        $<$<C_COMPILER_ID:Clang>:
        -fsanitize=undefined,integer,implicit-conversion,nullability,address,leak,cfi
        -flto>)

Answer 1

My review is focused on linkedlist.c:

• Some functions don't check for null pointer (get_node_val, set_node_val). While it's documented, other functions do check for null pointer.
• The functions to append and prepend nodes require the caller to call the function to create a node. It might be a better idea to create the node in the function and to return the newly-created node.
• The function append does not return the new node while the function prepend does.
• The data can only be an integer; having a void pointer on the listed data allows to have any type of data. However, this change would make your search function unusable.
• Printing the data is a way of handling the data. It seems that this is the role of the caller.
• You may want to consider having a function to return the length of the list.

Answer 2

The data can only be an integer; having a void pointer on the listed data allows to have any type of data. ...

I think the suggestion to move to void* is a very good one. It's a great next step to take if you want to keep working on your codebase.

... However, this change would make your search function unusable.

To make the search function usable with void*, it makes the most sense to offload the comparison functionality to a consumer-supplied function. This is how posix's bsearch funcitonality works:

int (*compar)(const void *, const void *)

The man page explains that

The compar routine is expected to have two arguments which point to the key object and to an array member, in that order, and should return an integer less than, equal to, or greater than zero if the key object is found, respectively, to be less than, to match, or be greater than the array member

The approach makes sense. If you don't know the type of the objects in your list, you can't compare them, and this is something that the consumer will have to do for you. Passing a function pointer is a pretty standard way to do so; qsort works the same way.

Answer 3

Instead of using void* or function pointers, I would say a tagged union would also offer a safe way to allow for more flexible node data.

Using a tagged union would ensure only the size of the largest element is allocated plus any needed padding to raise the length to an alignment boundary (Ref: C: A Reference Manual, 5th Ed., Sec. 5.7.2, p.162). Using the corresponding enum, appropriate data can be accessed when traversing the linked list. Searching can be implemented with separate functions for each supported type.

A simple example to illustrate with 3 types:

enum Tag {
    INT_TYPE, FLOAT_TYPE, STRING_TYPE
};

struct Node {
    enum Tag tag;
    union {
        int int_val;
        float float_val;
        char* string_val;
    };
    struct Node *next;
};

/* Searching methods which would take an argument and traverse the list,
accessing data based on the type specified in the enum */