Gfrktyl

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 %dn", 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 foundn", 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>)