C Singly Linked List Implementation

Question

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));
}

• Sᴀᴍ Onᴇᴌᴀ: Please see What to do when someone answers. I have rolled back Rev 3 → 2

Answer 1

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'

• SuperStormer: 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?
• user3629249: 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'

Answer 2

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