Doubly-linked list functions

Question

This is my first time implementing a doubly-linked list. I would like some feedback on my code. Any comment would be appreciated regarding the quality of the code, bad implementation, memory management, memory leaks, etc.

This is the API:

#include "linked_list.h"

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>

void ll_create(linked_list_p list) {
    list->head = NULL;
    list->tail = NULL;
    list->size = 0;
}

static bool is_list_empty (linked_list_p list) {
    if (list->head == NULL && list->tail == NULL && list->size == 0) {
        return true;
    }
    return false;
}

int ll_destroy(linked_list_p list) {
    if (is_list_empty(list) || list == NULL) {
        return -1;
    }

    linked_list_node_p node_ptr = list->tail;

    for(int i = list->size-1; i > 0; i--) {
        node_ptr = node_ptr->previous;

        node_ptr->next->previous = NULL;
        node_ptr->next->next = NULL;

        free(node_ptr->next);
        node_ptr->next = NULL;
    }

    free(list->head);
    list->head = NULL;
    list->tail = NULL;

    list->size = 0;
    return 0;
}

int ll_get(linked_list_p list, uint32_t index, uint8_t *data){
    if (is_list_empty(list) || index >= list->size || list == NULL) {
        return -1;
    }

    linked_list_node_p node_ptr = list->head;

    for (int i = 0; i < index; i++){
        if (node_ptr == NULL) {
            return -1;
        }
        node_ptr = node_ptr->next;
    }

    *data = node_ptr->data.data;

    return 0;
}

int ll_remove_first(linked_list_p list) {
    if (is_list_empty(list) || list == NULL) {
        return -1;
    }

    if (list->size == 1) {
        free(list->head);
        list->head = NULL;
        list->tail = NULL;
        list->size --;
        return 0;
    }

    linked_list_node_p node_to_remove = list->head;

    list->head = list->head->next;
    free(node_to_remove);
    node_to_remove = NULL;

    list->size --;
    return 0;
}

int ll_remove_last(linked_list_p list) {
    if (is_list_empty(list) || list == NULL) {
        return  -1;
    }

    if (list->size == 1) {
        return (ll_remove_first(list));
    }

    linked_list_node_p node_to_remove = list->tail;
    list->tail->previous->next = NULL;
    list->tail = list->tail->previous;

    node_to_remove->previous = NULL;
    free(node_to_remove);
    node_to_remove = NULL;

    list->size --;
    return 0;
}

int ll_remove(linked_list_p list, uint32_t index) {

    if (is_list_empty(list) || index >= list->size || list == NULL) {
        return -1;
    }

    linked_list_node_p node_to_delete;

    if (index == 0) {
        return (ll_remove_first(list));
    }

    if (index == list->size-1) {
        return (ll_remove_last(list));
    }

    linked_list_node_p node_ptr = list->head;
    for (int i = 0; i < index-1; i++) {
        node_ptr = node_ptr->next;
    }
    node_to_delete = node_ptr->next;

    node_ptr->next->next->previous = node_ptr;
    node_ptr->next = node_ptr->next->next;

    node_to_delete->next = NULL;
    node_to_delete->previous = NULL;
    free(node_to_delete);
    node_to_delete = NULL;

    list->size--;
    
    return 0;
}

int ll_insert(linked_list_p list, uint8_t data, uint32_t index) {
    if (list == NULL || index >= list->size)  {
        return -1;
    }

    if (is_list_empty(list) || index == 0) {
        return (ll_add_first(list, data));
    }

    linked_list_node_p node_to_add = calloc(1, sizeof(linked_list_node_t));
    node_to_add->data.data = data;

    linked_list_node_p node_ptr = list->head;

    for (int i = 0; i < index-1; i++) {
        node_ptr = node_ptr->next;
    }

    node_to_add->next = node_ptr->next;
    node_to_add->previous = node_ptr;

    node_ptr->next->previous = node_to_add;
    node_ptr->next = node_to_add;

    list->size++;

    return 0;
}

int ll_add_last(linked_list_p list, uint8_t data) {
    if (list == NULL) {
        return -1;
    }

    linked_list_node_p new_node = calloc(1, sizeof(linked_list_t));
    if (new_node == NULL) {
        return -1;
    }
    new_node->data.data = data;

    if (is_list_empty(list)){
        list->head = new_node;
        list->tail = new_node;

        list->size++;
        return 0;
    }

    new_node->previous = list->tail;
    list->tail->next = new_node;
    list->tail = new_node;

    list->size++;
    return 0;
}

int ll_add_first(linked_list_p list, uint8_t data) {
    if (list == NULL) {
        return -1;
    }

    linked_list_node_p new_node = calloc(1, sizeof(linked_list_t));
    if (new_node == NULL) {
        return -1;
    }
    new_node->data.data = data;

    if (is_list_empty(list)) {
        list->head = new_node;
        list->tail = new_node;

        list->size++;
        return 0;
    }

    list->head->previous = new_node;
    new_node->next = list->head;
    list->head = new_node;

    list->size++;
    return 0;
}

ssize_t ll_size(linked_list_p list) {
    if (is_list_empty(list) || list == NULL) {
        return -1;
    }
    return list->size;
}

int ll_contains(linked_list_p list, uint8_t data) {
    if (is_list_empty(list) || list == NULL) {
        return -1;
    }

    linked_list_node_p node_ptr = list->head;

    for (int i = 0; i < list->size; i++) {
        if (node_ptr == NULL)
            return -1;
        if (data == node_ptr->data.data) {
            return 1;
        }
        node_ptr = node_ptr->next;
    }
    return 0;
}

int ll_first_index(linked_list_p list, uint8_t data) {
    if (is_list_empty(list) || list == NULL) {
        return -1;
    }

    linked_list_node_p node_ptr = list->head;

    for (int i = 0; i < list->size; i++) {
        if (node_ptr == NULL)
            return -1;
        if (data == node_ptr->data.data) {
            return i;
        }
        node_ptr = node_ptr->next;
    }
    return -1;
}

int ll_indexes(linked_list_p list, uint8_t data, uint32_t **indexes, uint32_t *indexes_size) {
    if (is_list_empty(list) || list == NULL) {
        return -1;
    }

    if (indexes_size == NULL) {
        indexes_size = calloc(1, sizeof(uint32_t));
    }
    else {
        *indexes_size = 0;
    }

    linked_list_node_p node_ptr = list->head;

    for (int i = 0; i < list->size; i++) {
        if (data == node_ptr->data.data) {
            (*indexes_size) ++;

            *indexes = (uint32_t *)realloc(*indexes, (*indexes_size) * sizeof(uint32_t));
            (*indexes)[*indexes_size -1] = i;
        }
        node_ptr = node_ptr->next;
    }

    return 0;
}

void ll_print(linked_list_p list) {
    linked_list_node_p node_ptr = list->head;

    for (int i = 0; i < list->size; i++) {
        printf("[%d] --> %d\n", i, node_ptr->data.data);
        node_ptr = node_ptr->next;
    }

    printf("\n");
}

void ll_print_backward(linked_list_p list) {
    linked_list_node_p node_ptr = list->tail;

    for (int i = list->size-1; i >= 0; i--) {
        printf("[%d] --> %d\n", i, node_ptr->data.data);
        node_ptr = node_ptr->previous;
    }
    printf("\n");
}

This is the main used to test the API for errors :

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "linked_list.h"

int main(int argc, char *argv[]){
    static linked_list_t list;

    ll_create(&list);

    ll_remove(&list, 10);
    ll_add_last(&list, 2);
    ll_remove_last(&list);
    ll_insert(&list, 13, 0);
    ll_remove(&list, 32);
    ll_add_last(&list, 3);
    ll_add_last(&list, 4);
    ll_print(&list);
    ll_destroy(&list);
    ll_print(&list);
    ll_add_last(&list, 5);
    ll_add_last(&list, 6);
    ll_add_first(&list, 7);
    ll_print(&list);
    ll_print_backward(&list);
    ll_insert(&list, 8, 4);
    printf("list size : %ld\n", list.size);
    ll_insert(&list, 8, list.size);
    ll_print(&list);

    //TODO use every API functions

    // ll_get
    uint8_t get_data = 0;
    ll_get(&list, 95, &get_data);
    printf("got data : %d\n\n", get_data);

    // ll_remove
    ll_remove(&list, 5);
    ll_print(&list);

    // ll_insert
    ll_remove(&list, 0);
    ll_insert(&list, 10, 2);
    ll_print(&list);
    // ll_contains
    uint8_t data_to_find = 96;
    printf("The data %d is in the list : %s", data_to_find, ll_contains(&list, data_to_find) ? "true\n" : "false\n");
    data_to_find = 10;
    printf("The data %d is in the list : %s", data_to_find, ll_contains(&list, data_to_find) ? "true\n" : "false\n");
    printf("\n");

    // ll_first_index
    data_to_find = 10;
    printf("The data %d is at node [%d]\n", data_to_find, ll_first_index(&list, data_to_find));
    data_to_find = 96;
    printf("The data %d is at node [%d]\n", data_to_find, ll_first_index(&list, data_to_find));


    // ll_indexes
    ll_add_last(&list, 25);
    ll_add_first(&list, 25);
    ll_insert(&list, 25, list.size);
    ll_insert(&list, 25, 2);


    ll_print(&list);
    uint32_t *indexes = NULL;
    uint32_t indexes_size = 0;

    if (ll_indexes(&list, 25, &indexes, &indexes_size) == 0) {
        for (int i = 0; i < indexes_size; i++) {
            printf("%d ", indexes[i]);
        }
        printf("\n");
        free(indexes);
        indexes = NULL;
    }

    if (ll_indexes(&list, 6, &indexes, &indexes_size) == 0) {
        for (int i = 0; i < indexes_size; i++) {
            printf("%d ", indexes[i]);
        }
        printf("\n");
        free(indexes);
        indexes = NULL;
    }


    if (ll_indexes(&list, 7, &indexes, &indexes_size) == 0) {
        for (int i = 0; i < indexes_size; i++) {
            printf("%d ", indexes[i]);
        }
        printf("\n");
        indexes = NULL;
    }



    ll_destroy(&list);

    return 0;
}

This is the header structs and typedefs :

/**
 * No modification required here
 */
typedef struct data_s{
    uint8_t data;
} data_t;

/**
 * To be implemented : double linked list
 */

struct linked_list_s;
struct linked_list_node_s;

typedef struct linked_list_s linked_list_t;
typedef linked_list_t *linked_list_p;

typedef struct linked_list_node_s linked_list_node_t;
typedef linked_list_node_t *linked_list_node_p;

struct linked_list_node_s{
    linked_list_node_p next;
    linked_list_node_p previous;
    data_t data;
};

struct linked_list_s{
    linked_list_node_p head;
    linked_list_node_p tail;
    size_t size;

    void (*print_data)(uint8_t);
};

Answer 1

The provided main() exercises the API, but doesn't actually test it. It always returns a zero (success) exit status, even if the functions fail, or don't behave as advertised.

Worse than that, it misrepresents how the functions should be used, because it fails to check for run-time error conditions they report. E.g. it blindly assumes that ll_add_last() always succeeds, instead of inspecting its return value.

Instead of the functions returning 0 for success and -1 for failure, a more intuitive interface would be to use true for success and false for failure (both values are defined in <stdbool.h>, which we have already included).

---

I see several problems when I attempt to compile with GCC. To begin with, we're missing <stdint.h> needed for uint8_t and stddef.h> needed for size_t. Once that's fixed, we still have a large number of warnings and errors:

gcc-12 -std=c17 -fPIC -gdwarf-4 -g -Wall -Wextra -Wwrite-strings -Wno-parentheses -Wpedantic -Warray-bounds -Wmissing-braces -Wconversion  -Wstrict-prototypes -fanalyzer       284860.c    -o 284860
284860.c: In function ‘ll_destroy’:
284860.c:66:17: warning: conversion from ‘size_t’ {aka ‘long unsigned int’} to ‘int’ may change value [-Wconversion]
   66 |     for(int i = list->size-1; i > 0; i--) {
      |                 ^~~~
284860.c: In function ‘ll_get’:
284860.c:91:23: warning: comparison of integer expressions of different signedness: ‘int’ and ‘uint32_t’ {aka ‘unsigned int’} [-Wsign-compare]
   91 |     for (int i = 0; i < index; i++){
      |                       ^
284860.c: In function ‘ll_remove’:
284860.c:164:23: warning: comparison of integer expressions of different signedness: ‘int’ and ‘uint32_t’ {aka ‘unsigned int’} [-Wsign-compare]
  164 |     for (int i = 0; i < index-1; i++) {
      |                       ^
284860.c: In function ‘ll_insert’:
284860.c:188:17: warning: implicit declaration of function ‘ll_add_first’ [-Wimplicit-function-declaration]
  188 |         return (ll_add_first(list, data));
      |                 ^~~~~~~~~~~~
284860.c:196:23: warning: comparison of integer expressions of different signedness: ‘int’ and ‘uint32_t’ {aka ‘unsigned int’} [-Wsign-compare]
  196 |     for (int i = 0; i < index-1; i++) {
      |                       ^
284860.c: At top level:
284860.c:238:5: error: conflicting types for ‘ll_add_first’; have ‘int(linked_list_t *, uint8_t)’ {aka ‘int(struct linked_list_s *, unsigned char)’}
  238 | int ll_add_first(linked_list_p list, uint8_t data) {
      |     ^~~~~~~~~~~~
284860.c:238:1: note: an argument type that has a default promotion cannot match an empty parameter name list declaration
  238 | int ll_add_first(linked_list_p list, uint8_t data) {
      | ^~~
284860.c:188:17: note: previous implicit declaration of ‘ll_add_first’ with type ‘int()’
  188 |         return (ll_add_first(list, data));
      |                 ^~~~~~~~~~~~
284860.c:265:1: error: unknown type name ‘ssize_t’; did you mean ‘size_t’?
  265 | ssize_t ll_size(linked_list_p list) {
      | ^~~~~~~
      | size_t
284860.c: In function ‘ll_size’:
284860.c:269:16: warning: conversion from ‘size_t’ {aka ‘long unsigned int’} to ‘int’ may change value [-Wconversion]
  269 |     return list->size;
      |            ~~~~^~~~~~
284860.c: In function ‘ll_contains’:
284860.c:279:23: warning: comparison of integer expressions of different signedness: ‘int’ and ‘size_t’ {aka ‘long unsigned int’} [-Wsign-compare]
  279 |     for (int i = 0; i < list->size; i++) {
      |                       ^
284860.c: In function ‘ll_first_index’:
284860.c:297:23: warning: comparison of integer expressions of different signedness: ‘int’ and ‘size_t’ {aka ‘long unsigned int’} [-Wsign-compare]
  297 |     for (int i = 0; i < list->size; i++) {
      |                       ^
284860.c: In function ‘ll_indexes’:
284860.c:322:23: warning: comparison of integer expressions of different signedness: ‘int’ and ‘size_t’ {aka ‘long unsigned int’} [-Wsign-compare]
  322 |     for (int i = 0; i < list->size; i++) {
      |                       ^
284860.c:327:44: warning: conversion to ‘uint32_t’ {aka ‘unsigned int’} from ‘int’ may change the sign of the result [-Wsign-conversion]
  327 |             (*indexes)[*indexes_size -1] = i;
      |                                            ^
284860.c: In function ‘ll_print’:
284860.c:338:23: warning: comparison of integer expressions of different signedness: ‘int’ and ‘size_t’ {aka ‘long unsigned int’} [-Wsign-compare]
  338 |     for (int i = 0; i < list->size; i++) {
      |                       ^
284860.c: In function ‘ll_print_backward’:
284860.c:349:18: warning: conversion from ‘size_t’ {aka ‘long unsigned int’} to ‘int’ may change value [-Wconversion]
  349 |     for (int i = list->size-1; i >= 0; i--) {
      |                  ^~~~
284860.c: In function ‘main’:
284860.c:383:29: warning: conversion from ‘size_t’ {aka ‘long unsigned int’} to ‘uint32_t’ {aka ‘unsigned int’} may change value [-Wconversion]
  383 |     ll_insert(&list, 8, list.size);
      |                         ~~~~^~~~~
284860.c:418:30: warning: conversion from ‘size_t’ {aka ‘long unsigned int’} to ‘uint32_t’ {aka ‘unsigned int’} may change value [-Wconversion]
  418 |     ll_insert(&list, 25, list.size);
      |                          ~~~~^~~~~
284860.c:427:27: warning: comparison of integer expressions of different signedness: ‘int’ and ‘uint32_t’ {aka ‘unsigned int’} [-Wsign-compare]
  427 |         for (int i = 0; i < indexes_size; i++) {
      |                           ^
284860.c:436:27: warning: comparison of integer expressions of different signedness: ‘int’ and ‘uint32_t’ {aka ‘unsigned int’} [-Wsign-compare]
  436 |         for (int i = 0; i < indexes_size; i++) {
      |                           ^
284860.c:446:27: warning: comparison of integer expressions of different signedness: ‘int’ and ‘uint32_t’ {aka ‘unsigned int’} [-Wsign-compare]
  446 |         for (int i = 0; i < indexes_size; i++) {
      |                           ^
284860.c:361:14: warning: unused parameter ‘argc’ [-Wunused-parameter]
  361 | int main(int argc, char *argv[]){
      |          ~~~~^~~~
284860.c:361:26: warning: unused parameter ‘argv’ [-Wunused-parameter]
  361 | int main(int argc, char *argv[]){
      |                    ~~~~~~^~~~~~

---

ll_remove_first() fails to null out the previous pointer of the new head node - the equivalent action in ll_remove_last() is present (though here, we wrongly assign to node_to_remove just after we free it).

---

This test looks to be in the wrong order:

    if (is_list_empty(list) || index >= list->size || list == NULL) {

If list is a null pointer, then we must not call is_list_empty() or access list->size - so we should have the list == NULL test on the left side of those || operators.

Also the is_list_empty() test is redundant. If the list is empty, then list->size is zero, which cannot be greater than the (unsigned) index.

However, we're using the wrong type for index - if the list length is a size_t, then we need to be using the same type for indexing.

---

We're over-testing in is_list_empty():

    if (list->head == NULL && list->tail == NULL && list->size == 0) {

Our invariant requires that head and tail pointers are null if the size is zero, so we only need to test the size:

static bool is_list_empty (linked_list_p list)
{
    return list->size == 0;
}

---

Why do we have the print_data member in the list? It's never assigned or used, so it's just wasting space in the structure.

---

There's a lot of near-duplicate code, mainly due to having to treat first and last elements differently to other nodes. Consider using a dummy head node to simplify the implementation.

---

The type linked_list_p is harmful, as it hides a pointer. It makes it harder to write const-correct code (as we have no typedef for a linked_list_t const*). It's better to be open and transparent than to hide indirection.