Doubly Linked List of integers

Question

I wrote a working linked list program in C. What can I improve in my code in your opinion? The first thing I think about is doing unit tests. I want to learn TDD. I'm not sure if it is a good idea to implement in the pop_front and pop_back functions handling empty list situations.

main.c

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

int main(void) {
    printf("initializing list");
    struct linked_list *list = ll_new();
    ll_push_back(list, 2);
    ll_push_back(list, 3);
    printf("data after ll_push_bash:\n");
    ll_print(list);

    int data;
    ll_pop_back(list, &data);
    ll_pop_back(list, &data);
    printf("data after 2x ll_pop_back: data=%d\n", data);
    ll_print(list);

    ll_push_front(list, 3);
    ll_push_front(list, 4);
    printf("data after ll_push_front:\n");
    ll_print(list);

    ll_pop_front(list, &data);
    ll_pop_front(list, &data);
    ll_print(list);
    printf("data after 2x ll_pop_front: %d\n", data);

    printf("inserting data into list:\n");
    ll_push_front(list, 1);
    ll_push_front(list, 2);
    ll_push_back(list, 3);
    ll_print(list);
    if (ll_contains(list, 3) > -1) {
        printf("list contains element 3\n");
    }
    int idx = ll_find(list, 1);
    if (idx > -1) {
        printf("list contains element 1 at position %d\n", idx);
    }
    ll_destroy(&list);
    return 0;
}

linked_list.h

#ifndef LINKED_LIST_H
#define LINKED_LIST_H

#include <stdlib.h>

struct ll_node {
    int data;
    struct ll_node *prev;
    struct ll_node *next;
};

struct linked_list {
    struct ll_node *head;
    struct ll_node *tail;
    size_t count;
};

struct linked_list *ll_new(void);
int ll_destroy(struct linked_list **list);

int ll_push_back(struct linked_list *list, int data);
int ll_pop_back(struct linked_list *list, int *data);
int ll_push_front(struct linked_list *list, int data);
int ll_pop_front(struct linked_list *list, int *data);

int ll_get(struct linked_list *list, int index, int *data);
int ll_set(struct linked_list *list, int index, int data);

int ll_is_index_valid(struct linked_list *list, int index);

int ll_find(struct linked_list *list, int data);
int ll_contains(struct linked_list *list, int data);

int ll_print(struct linked_list *list);

#endif //LINKED_LIST_H

linked_list.c

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

struct linked_list *ll_new(void) {
    struct linked_list *list = malloc(sizeof(*list));
    if (list == NULL) {
        return NULL;
    }
    list->head = NULL;
    list->tail = NULL;
    list->count = 0;
    return list;
}

int ll_destroy(struct linked_list **list) {
    if (list == NULL || *list == NULL) {
        return -1;
    }
    if ((*list)->head != NULL) {
        struct ll_node *node = (*list)->head;
        while (node->next != NULL) {
            node = node->next;
            free(node->prev);
            node->prev = NULL;
        }
        free(node);
    }
    free(*list);
    return 0;
}

int ll_push_back(struct linked_list *list, int data) {
    if (list == NULL) {
        return -1;
    }
    struct ll_node *node = malloc(sizeof(struct ll_node));
    if (node == NULL) {
        return -1;
    }
    node->prev = list->tail;
    node->next = NULL;
    node->data = data;
    if (list->count == 0) {
        list->head = node;
        list->tail = node;
    } else {
        list->tail->next = node;
        list->tail = list->tail->next;
    }
    ++(list->count);
    return 0;
}

int ll_pop_back(struct linked_list *list, int *data) {
    if (list == NULL) {
        return -1;
    }
    if (data != NULL) {
        *data = list->tail->data;
    }
    if (list->count > 1) {
        struct ll_node *prev = list->tail->prev;
        free(list->tail);
        list->tail = prev;
        list->tail->next = NULL;
    } else {
        free(list->tail);
        list->tail = NULL;
        list->head = NULL;
    }
    --(list->count);
    return 0;
}

int ll_push_front(struct linked_list *list, int data) {
    if (list == NULL) {
        return -1;
    }
    struct ll_node *node = malloc(sizeof(struct ll_node));
    node->data = data;
    node->prev = NULL;
    if (list->count == 0) {
        node->next = NULL;
        list->tail = node;
    } else {
        node->next = list->head;
    }
    list->head = node;
    ++(list->count);
    return 0;
}

int ll_pop_front(struct linked_list *list, int *data) {
    if (list == NULL) {
        return -1;
    }
    if (data != NULL) {
        *data = list->head->data;
    }
    if (list->count > 1) {
        struct ll_node *next = list->head->next;
        list->head = next;
        free(list->head->prev);
        list->head->prev = NULL;
    } else {
        free(list->head);
        list->head = NULL;
        list->tail = NULL;
    }
    --(list->count);
    return 0;
}

int ll_is_index_valid(struct linked_list *list, int index) {
    return index >= 0 && index < list->count ? 0 : -1;
}

int ll_get(struct linked_list *list, int index, int *data) {
    if (list == NULL || ll_is_index_valid(list, index) < 0) {
        return -1;
    }
    int result;
    if (index <= list->count / 2 - 1) {
        struct ll_node *node = list->head;
        for (int i = 0; i <= index && node != NULL; ++i) {
            result = node->data;
            node = node->next;
        }
    } else {
        struct ll_node *node = list->tail;
        for (int i = 0; i < list->count - index && node != NULL; ++i) {
            result = node->data;
            node = node->prev;
        }
    }
    *data = result;
    return 0;
}

int ll_set(struct linked_list *list, int index, int data) {
    if (list == NULL || ll_is_index_valid(list, index) < 0) {
        return -1;
    }
    if (index <= list->count / 2 - 1) {
        struct ll_node *node = list->head;
        for (int i = 0; i <= index && node->next != NULL; ++i) {
            node = node->next;
        }
        node->prev->data = data;
    } else {
        struct ll_node *node = list->tail;
        for (int i = 0; i < list->count - index - 1 && node->prev != NULL; ++i) {
            node = node->prev;
        }
        node->data = data;
    }
    return 0;
}

int ll_find(struct linked_list *list, int data) {
    int offset = 0;
    struct ll_node *node = list->head;
    while (node->next != NULL) {
        if (node->data == data) {
            return offset;
        }
        ++offset;
        node = node->next;
    }
    return -1;
}

int ll_contains(struct linked_list *list, int data) {
    return ll_find(list, data) >= 0;
}

int ll_print(struct linked_list *list) {
    if (list == NULL) {
        return -1;
    }
    if (list->head == NULL) {
        printf("list is empty\n");
        return 0;
    }
    int n = 0;
    struct ll_node *node = list->head;
    while (node != NULL) {
        printf("linked list node %d: %d\n", n, node->data);
        node = node->next;
        ++n;
    }
    return 0;
}

TDD starts with requirements definition to interface design. — greybeard
– greybeard, Commented Feb 21, 2023 at 5:06

Toby Speight · Accepted Answer · 2023-02-21 08:54:18Z

2

As you suggest, the best next step is to convert the demo program into a set of unit-tests. There's a pretty good start here; two things that need changing:

Instead of just printing the results, we should be actually testing them, and using that to determine the exit status (EXIT_SUCCESS or EXIT_FAILURE, from <stdlib.h>). Ideally, the tests should be silent when successful.
Each test should be independent, starting with a new empty list rather than relying on the state at the end of the previous test.

The header file has an include of <stdlib.h>, but doesn't need it for any of its declarations, so that can be dropped.

Some style issues here:

    struct ll_node *node = malloc(sizeof(struct ll_node));
    if (node == NULL) {
        return -1;
    }

Prefer sizeof *node rather than the type expression, like we did in ll_new().

Consider including <stdbool.h> and returning true/false to indicate success or failure.

Consider using a dummy head node, which can eliminate most of the cases where we need different code for adding/removing at the head or tail of the list to doing so in the middle, and never have to deal with null pointers:

struct linked_list {
    struct ll_node the_list;
    size_t count;
};

answered Feb 21, 2023 at 8:54

Toby Speight

88.4k14 gold badges104 silver badges327 bronze badges

\$\begingroup\$ Is it a good idea to use CMocka for unit tests? Should I use an external library or roll own my tool for unit tests? \$\endgroup\$

whiteman808
– whiteman808

2023-02-21 20:20:05 +00:00
Commented Feb 21, 2023 at 20:20
\$\begingroup\$ I used -1/0 to be consistent with stdlib but true/false is more readable for me. Should I suggest that stdlib things use -1/0 or use true/false? \$\endgroup\$

whiteman808
– whiteman808

2023-02-21 20:29:22 +00:00
Commented Feb 21, 2023 at 20:29
\$\begingroup\$ The only functions in standard library that return -1 on failure can return a range of non-negative values on success. I recommend true/false if you find that more readable, as I do. (Remember that <stdbool.h> wasn't around for most of the standard library's existence, so it can be excused!) \$\endgroup\$

Toby Speight
– Toby Speight

2023-02-22 08:06:04 +00:00
Commented Feb 22, 2023 at 8:06

Add a comment |

Stack Exchange Network

Doubly Linked List of integers

main.c

linked_list.h

linked_list.c

1 Answer 1

You must log in to answer this question.

Hot Network Questions

Doubly Linked List of integers

main.c

linked_list.h

linked_list.c

1 Answer 1

You must log in to answer this question.

Related

Hot Network Questions