4
\$\begingroup\$

I'm a C Beginner and I am looking for feedback on my implementation of a singly linked list. The code is split between list.c and list.h.

list.h:

#ifndef LIST
#define LIST
#include <stddef.h>

typedef struct List {
    int val;
    struct List* next;
} List;
int list_len(List* head);
void list_insert(List* head, int val, int index);
void list_insert_end(List* head, int val);
void list_insert_all(List* head, int* vals, size_t size);
List* array_to_list(int* vals, size_t size);
int list_get(List* head, int index);
void list_set(List* head, int val, int index);
void list_remove(List* head, int index);
int list_indexof(List* head, int val);
int list_rindexof(List* head, int val);
void free_list(List* head);
void print_list(List* head);
#endif

list.c:

#include "list.h"

#include <assert.h>
#include <stddef.h>
#include <stdio.h>
#include <stdlib.h>

int list_len(List* head) {
    assert(head != NULL && "Empty List");
    List* curr = head;
    int i = 1;
    while (curr->next) {
        curr = curr->next;
        i++;
    }
    return i;
}
void list_insert_end(List* head, int val) {
    assert(head != NULL && "Empty List");
    List* item = malloc(sizeof(List));
    item->val = val;
    item->next = NULL;
    List* curr = head;
    while (curr->next) {
        curr = curr->next;
    }
    curr->next = item;
}
void list_insert(List* head, int val, int index) {
    assert(head != NULL && "Empty List");
    List* item = malloc(sizeof(List));
    item->val = val;
    if (index == 0) {
        item->next = head;
        head = item;
        return;
    }
    List* prev;
    List* curr = head;
    for (int i = 0; i < index; i++) {
        prev = head;
        assert(!curr->next && "Index Out of Bounds");
        curr = curr->next;
    }
    prev->next = item;
    item->next = curr;
    return;
}
void list_insert_all(List* head, int* vals, size_t size) {
    assert(head != NULL && "Empty List");
    for (size_t i = 0; i < size; i++) {
        list_insert_end(head, vals[i]);
    }
}
List* array_to_list(int* vals, size_t size) {
    List* list = malloc(sizeof(List));
    list->val = vals[0];
    list->next = NULL;
    list_insert_all(list, vals + 1, size - 1);
    return list;
}
int list_get(List* head, int index) {
    assert(head != NULL && "Empty List");
    List* curr = head;
    for (int i = 0; i < index; i++) {
        assert((curr->next) != 0 && "Index Out of Bounds");
        curr = curr->next;
    }
    printf("%i", curr->val);
    return curr->val;
}
void list_set(List* head, int val, int index) {
    assert(head != NULL && "Empty List");
    List* curr = head;
    for (int i = 0; i < index; i++) {
        assert((curr->next) != 0 && "Index Out of Bounds");
        curr = curr->next;
    }
    curr->val = val;
}
void list_remove(List* head, int index) {
    assert(head != NULL && "Empty List");
    List* curr = head;

    if (index == 0) {
        head = head->next;
        free(curr);
        return;
    }
    for (int i = 0; i < index - 1; i++) {
        assert((curr->next) != 0 && "Index Out of Bounds");
        curr = curr->next;
    }
    List* next = curr->next->next;
    free(curr->next);
    curr->next = next;
}
int list_indexof(List* head, int val) {
    assert(head != NULL && "Empty List");
    List* curr = head;
    int i = 0;
    while (curr->next) {
        if (curr->val == val) {
            return i;
        }
        i++;
        curr = curr->next;
    }
    return -1;
}
int list_rindexof(List* head, int val) {
    assert(head != NULL && "Empty List");
    List* curr = head;
    int i = 0, j = -1;
    while (curr->next) {
        if (curr->val == val) {
            j = i;
        }
        i++;
        curr = curr->next;
    }
    return j;
}
void free_list(List* head) {
    assert(head != NULL && "Empty List");
    List* curr = head;
    List* next;
    while (curr->next) {
        next = curr->next;
        free(curr);
        curr = next;
    }
    head = NULL;
}
void print_list(List* head) {
    assert(head != NULL && "Empty List");
    List* curr = head;
    fputs("[", stdout);
    printf("%i", curr->val);
    while (curr->next) {
        curr = curr->next;
        printf(", %i", curr->val);
    }
    fputs("]", stdout);
}
int main() {
    List list = *array_to_list((int[]){1, 2, 3, 4}, 4);
    list_insert_all(&list, (int[]){1, 2, 3, 4}, 4);
    list_set(&list, 10, 2);
    print_list(&list);
    list_remove(&list, 7);
    print_list(&list);
    printf("%i ", list_get(&list, 3));
    printf("%i", list_len(&list));
    printf(" %i", list_rindexof(&list, 1));
}
Improve this question
\$\endgroup\$
1

2 Answers 2

Reset to default
2
\$\begingroup\$

in this function:

void list_remove(List* head, int index)

there is the statement:

head = head->next;

is a problem as this changes the parameter on the stack, not the actual list

in function: main() this statement:

List list = *array_to_list((int[]){1, 2, 3, 4}, 4);

will result in the variable list containing the contents of the first instance of the struct, NOT a pointer to the head of the list

in function: main(), this function call:

list_insert_all(&list, (int[]){1, 2, 3, 4}, 4);

results in all the parameters being inserted into the list, however; the earlier call to:

List list = *array_to_list((int[]){1, 2, 3, 4}, 4);

also called: list_insert_all(), so the parameters are now in the list twice

in function: list_insert() in the for() loop, this statement:

prev = head;

is executed index number of times, however; when index is 0, then that statement is never executed, so the following code:

prev->next = item;

is working with an uninitialized variable prev

it is a very poor programming practice to name variables the same as a struct type with the only difference being capitalization. The compiler will not have a problem, but the humans reading the code will have a problem.

I have not examined the rest of the code, but the above should be enough to get you pointed in the right direction

EDIT:

in the function: free_list() the body of the function tries to free() the first entry in the list, however; that first entry is an actual instance of the list node, on the stack in the main() function. Trying to free() something on the stack will result in a crash. This is another good reason to have a 'head' pointer on the stack that points to the first list 'node'

Improve this answer
\$\endgroup\$
2
  • \$\begingroup\$ Isn't the 1st instance of the struct equal to the head of the list? Also, there is an if statement to handle index == 0. In OOP languages, I believe it is perfectly fine to have a variable named as the class lowercased. Does C have different naming conventions in this regard? \$\endgroup\$
    – SuperStormer
    Mar 13, 2020 at 16:48
  • \$\begingroup\$ in general, there will be a 'head' pointer of type 'your struct node name' which is initialized to NULL. When the first node is added, then the 'head' is modified to point to that first 'node' \$\endgroup\$
    – user3629249
    Mar 13, 2020 at 20:59
0
\$\begingroup\$

looking for feedback on my implementation of a singly linked list.

Not enough info in the .h

Consider that the .c file is opaque to the user - they cannot see it. The .h file is a good place to document and provide simply usage notes. Looking at this .h file, I do not know how to properly define a List variable.

const

Referenced data not changed is best as const. It allows for some additional uses, optimizations and conveys the code's intention.

// int list_len(List* head);
// List* array_to_list(int* vals, size_t size);
// void print_list(List* head);
int list_len(const List* head);
List* array_to_list(const int* vals, size_t size);
void print_list(const List* head);

What happens when ...

Some functions are self documented by name: list_insert_end(). Yet list_insert() deserves more detail. What happens when the index is much more than the list length?

This applies to a number of functions: what do they do?

IOWs, some light documentation in the .h file helps a lot.

int or size_t

Choose one type, recommend size_t, to handle list size.

vvv
int list_len(List* head);
List* array_to_list(int* vals, size_t size);
                               ^^^^^^

.c

Consider allocating to the size of the referenced type

Easier to write correctly, review and maintain.

// list = malloc(sizeof(List));
list = malloc(sizeof *list);

Good use of first #include is this file's .h 

#include "list.h"

Size 0

array_to_list(int* vals, size_t size) does not handle size == 0. Most (all?) of the code has trouble with an empty list. IMO, this is a fatal design flaw. A list should be allowed to be initially empty.

The List list = *array_to_list((int[]){1, 2, 3, 4}, 4); is a novel, yet unclear way to initialize.

main()

Better to have main() in another file than list.c.

Well formatted code

Improve this answer
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.