list.c

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

// NULL: a special value we can store
// in a pointer that indicates that
// it refers to nothing

// helper function prototypes
struct node *new_node(int data, struct node *next);


// Task 1
struct node *create_list() {
    return NULL;
}

// Task 1.5
int sum_list_values(struct node *list) {
    int sum = 0;

    // Step 1: make a `current` to keep track of where we are in the list
    struct node *current = list;

    // Step 2: iterate through the list using a loop (NULL is at the end)
    while (current != NULL) {

        // Step 3: reassign current to increment the loop
        sum += current->data;
        current = current->next;
    }

    return sum;
}

// Task 2
struct node *prepend(struct node *list, int data) {

    // Empty list case
    if (list == NULL) {
        return new_node(data, NULL);
    }

    struct node *temp = list;  // to avoid loosing the rest of the list
    list = new_node(data, temp);  // create a new node and attach the rest

    return list;
}

// Task 3
struct node *append(struct node *list, int data) {

    // Empty list case
    if (list == NULL) {
        return new_node(data, NULL);
    }

    // Step 1: make a `current` to keep track of where we are in the list
    struct node *current = list;

    // Step 2: iterate through the list using a loop (NULL is at the end)
    while (current->next != NULL) {

        // Step 3: reassign current to increment the loop
        current = current->next;
    }

    // If control reaches here, it means we are at the end of the list
    current->next = new_node(data, NULL);

    return list;
}

// Task 4
struct node *sorted_insert(struct node *list, int data) {

    // Empty list case
    if (list == NULL) {
        return new_node(data, NULL);
    }

    // Beginning of list case
    if (data <= list->data) {
        return prepend(list, data);
    }

    // Step 1: make a `current` to keep track of where we are in the list
    struct node *current = list;

    // Step 2: iterate through the list using a loop (NULL is at the end)
    while (current->next != NULL) {

        // Stop one element before the target position
        if (data <= current->next->data) {
            struct node *temp = current->next;
            current->next = new_node(data, temp);
            return list;
        }

        // Step 3: reassign current to increment the loop
        current = current->next;
    }

    // If control reaches here, `data` is the biggest value
    list = append(list, data);

    return list;
}

// Task 5
struct node *delete(struct node *list, int position) {
    int count = 0;

    // Empty list case
    if (list == NULL) {
        return list;  // behaviour not defined by the interface
    }

    // First element list case
    if (position == 0) {
        struct node *temp = list->next;
        free(list);
        return temp;
    }

    // Step 1: make a `current` to keep track of where we are in the list
    struct node *current = list;

    // Step 2: iterate through the list using a loop (NULL is at the end)
    while (current->next != NULL) {

        // Stop one element before the target position
        if (count == position - 1) {
            struct node *temp = current->next->next;
            free(current->next);
            current->next = temp;
            return list;
        }

        // Step 3: reassign current to increment the loop
        current = current->next;
        count++;
    }

    // If control reaches here it means the index wasn't found in the list
    printf("Invalid index to list: %d\n", position);
    abort();
}

// Task 6
struct node *delete_all(struct node *list) {
    // delete elements from the front until none remain
    while (list != NULL) {
        list = delete(list, 0);
    }

    return list;  // guaranteed to be NULL
}

void show_list(struct node *list) {
    printf("->");

    // Step 1: make a `current` to keep track of where we are in the list
    struct node *current = list;

    // Step 2: iterate through the list using a loop (NULL is at the end)
    while (current != NULL) {

        printf("[%d]->", current->data);

        // Step 3: reassign current to increment the loop
        current = current->next;
    }
    printf("(x)\n");
}

struct node *new_node(int data, struct node *next) {
    struct node *new = malloc(sizeof (struct node));
    new->data = data;
    new->next = next;
    return new;
}

list.h

// List.h

struct node {
    struct node *next;
    int data;
};

// creates a new linked list and returns a pointer
// must be called before using list functions
struct node *create_list(void);

// sum all values in the list
int sum_list_values(struct node *list);

// add an element to the front of the list
struct node *prepend(struct node *list, int data);

// add an element to the end of the list
struct node *append(struct node *list, int data);

// given a sorted list, insert a new element
// so that the resulting list remains sorted
struct node *sorted_insert(struct node *list, int data);

// delete an element at a given index
struct node *delete(struct node *list, int position);

// delete all elements in the list
struct node *delete_all(struct node *list);

// print out a representation of the given list
void show_list(struct node *list);

test_list.c

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


#include "list.h"


void test_sum_list(void);
void test_sorted_insert(void);

int main() {

    test_sum_list();
    test_sorted_insert();
    printf("All tests passed.\n");

    return EXIT_SUCCESS;
}

void test_sum_list(void) {

    // create a test list
    struct node *test_list = create_list();

    // check the sum is correct (for an empty list)
    assert(sum_list_values(test_list) == 0);

    // add elements to the list
    test_list = append(test_list, 3);
    test_list = append(test_list, 1);
    test_list = append(test_list, 4);
    test_list = append(test_list, 1);
    test_list = append(test_list, 5);
    test_list = append(test_list, 9);
    test_list = append(test_list, 2);

    // check the elements sum correctly
    assert(sum_list_values(test_list) == 25);

    // add more elements to the list
    test_list = prepend(test_list, 3);
    test_list = prepend(test_list, 1);
    test_list = prepend(test_list, 4);
    test_list = prepend(test_list, 1);
    test_list = prepend(test_list, 5);
    test_list = prepend(test_list, 9);
    test_list = prepend(test_list, 2);

    // check the elements sum correctly
    assert(sum_list_values(test_list) == 50);

    // removing elements from the list
    test_list = delete(test_list, 1);
    test_list = delete(test_list, 0);
    test_list = delete(test_list, 11);

    // check the elements sum correctly
    assert(sum_list_values(test_list) == 37);

    // clean up list
    test_list = delete_all(test_list);
}

void test_sorted_insert(void) {

    // create a test list
    struct node *test_list = create_list();

    // test insertion into an empty list
    test_list = sorted_insert(test_list, 42);
    assert(sum_list_values(test_list) == 42);


    test_list = sorted_insert(test_list, 42);
    assert(sum_list_values(test_list) == 84);


    test_list = sorted_insert(test_list, 41);
    assert(sum_list_values(test_list) == 125);


    test_list = sorted_insert(test_list, 43);
    assert(sum_list_values(test_list) == 168);


    test_list = delete(test_list, 0);
    test_list = delete(test_list, 0);
    test_list = delete(test_list, 0);
    test_list = delete(test_list, 0);

    // add elements to the list so that it is sorted
    test_list = append(test_list, 1);
    test_list = append(test_list, 1);
    test_list = append(test_list, 2);
    test_list = append(test_list, 3);
    test_list = append(test_list, 4);
    test_list = append(test_list, 5);
    test_list = append(test_list, 9);

    // check the elements sum correctly
    assert(sum_list_values(test_list) == 25);


    // add more elements to the list
    test_list = sorted_insert(test_list, 3);
    assert(sum_list_values(test_list) == 28);

    test_list = sorted_insert(test_list, 1);
    assert(sum_list_values(test_list) == 29);

    test_list = sorted_insert(test_list, 4);
    assert(sum_list_values(test_list) == 33);

    test_list = sorted_insert(test_list, 1);
    assert(sum_list_values(test_list) == 34);

    test_list = sorted_insert(test_list, 5);
    assert(sum_list_values(test_list) == 39);

    test_list = sorted_insert(test_list, 9);
    assert(sum_list_values(test_list) == 48);

    test_list = sorted_insert(test_list, 2);

    // check the elements sum correctly
    assert(sum_list_values(test_list) == 50);


    // clean up list
    test_list = delete_all(test_list);
}