COMP1511 Week 13 Laboratory Sample Solutions

Objectives

In these revision lab exercises you will revise topics relevant to the week 13/14 exam.

Computation over linked lists.
Changing linked lists.

Preparation

Before the lab you should re-read the relevant lecture slides and their accompanying examples. You should also have read the lab assessment guidelines.

Getting Started

One member of your programming pair should login and run the following commands inside a Linux terminal

Create a new directory for this lab called lab13 by typing:

mkdir lab13

Change to this directory by typing:

cd lab13

Introduction

These revision exercises are designed to prepare you for the mid-session exam.

These revision exercises are not assessable.

They do not get marked.

There is no need to submit them with give.

The file lab13.c is the starting point for the revision exercises.

It contains struct node, which is used to store a sequence of integers. This is the same data representation you have seen in lectures.

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

Start by copying lab13.c:

cp /import/chopin/1/cs1511/public_html/17s1/tlb/13/lab13.c .

lab13.c contains five functions which have not been implemented. Your task is to implement these five functions.

Revision Exercise: Count List Elements Containing Value

lab13.c contains a function with this prototype:

int count(int value, struct node *list)

Implement count.

count should return the number of nodes in the list containing value.

As usual autotest is available to test your code:

 ~cs1511/bin/autotest lab13 count

An iterative solution for count

int count(int value, struct node *head) {
    int how_many = 0;

    struct node *p = head;
    while (p != NULL) {
        if (p->data == value) {
            how_many++;
        }
        p = p->next;
    }

    return how_many;
}

A recursive solution for count

int count(int value, struct node *head) {
    if (head == NULL) {
        return 0;
    }

    if (head->data == value) {
        return 1 + count(value, head->next);
    } else {
        return count(value, head->next);
    }
}

Less readable but more concise recursive solution for count. Check your understanding of C by figuring out how it works.

int count1(int value, struct node *head) {
    if (head == NULL) {
        return 0;
    } else {
        return ((head->data == value) + count(value, head->next));
    }
}

Very concise version that uses C's ternary operator. Much less readable.

int count2(int value, struct node *head) {
   return (head == NULL) ? 0 : ((head->data == value) + count(value, head->next));
}

Revision Exercise: Get n-th List element

lab13.c contains a function with this prototype:

struct node *get_nth(int n, struct node *head)

Implement get_nth.

get_nth should return a pointer to the node in position n in the list.

Position 0 is the first node in the list.

get_nth should return NULL if the list has no n-th node.

As usual autotest is available to test your code:

 ~cs1511/bin/autotest lab13 get_nth

An iterative solution for get_nth

struct node *get_nth(int n, struct node *head) {
    int position = 0;
    struct node *p = head;

    while (p != NULL) {
        if (position == n) {
            return p;
        }
        p = p->next;
        position++;
    }

    return NULL;
}

A recursive solution for get_nth

struct node *get_nth(int n, struct node *head) {
    if (head == NULL) {
        return NULL;
    }
    if (n == 0) {
        return head;
    }
    return get_nth(n - 1, head->next);
}

Revision Exercise: Delete n-th List element

lab13.c contains a function with this prototype:

struct node *delete_nth(int n, struct node *head)

Implement delete_nth.

delete_nth should delete the node in position n in the list.

delete_nth should free the deleted node.

delete_nth should make no changes if there is no position n in the list.

delete_nth should return the (possibly changed) head of the list.

As usual autotest is available to test your code:

 ~cs1511/bin/autotest lab13 delete_nth

An iterative solution for delete_nth

struct node *delete_nth(int n, struct node *head) {
    if (head == NULL) {
        return NULL;
    }

    if (n == 0) {
        struct node *new_head = head->next;
        free(head);
        return new_head;
    }

    int position = 0;
    struct node *p = head;

    // find node in position n - 1
    while (p->next != NULL) {
        if (position == n - 1) {
            struct node *new_next = p->next->next;
            free(p->next);
            p->next = new_next;
            return head;
        }
        p = p->next;
        position++;
    }

    return head;
}

A recursive solution for delete_nth

struct node *delete_nth(int n, struct node *head) {
    if (head == NULL) {
        return NULL;
    }
    if (n == 0) {
        struct node *new_head = head->next;
        free(head);
        return new_head;
    }
    head->next = delete_nth(n - 1, head->next);
    return head;
}

Revision Exercise: Delete Odd List elements

lab13.c contains a function with this prototype:

struct node *delete_odd(struct node *head)

Implement delete_odd.

delete_odd should delete all nodes in the list containing odd numbers.

delete_odd should free any deleted nodes.

delete_odd should return the (possibly changed) head of the list.

As usual autotest is available to test your code:

An iterative solution for delete_odd

struct node *delete_odd(struct node *head) {
    if (head == NULL) {
        return NULL;
    }
    if (head->data % 2 == 1) {
        struct node *new_head = delete_odd(head->next);
        free(head);
        return new_head;
    }

    struct node *p = head;
    while (p->next != NULL) {
        if (p->next->data % 2 == 1) {
            struct node *new_next = p->next->next;
            free(p->next);
            p->next = new_next;
        } else {
            p = p->next;
        }
    }

    return head;
}

A recursive solution for delete_odd

struct node *delete_odd(struct node *head) {
    if (head == NULL) {
        // list is empty no node to delete
        return NULL;
    }
    if (head->data % 2 == 1) {
        struct node *new_head = delete_odd(head->next);
        free(head);
        return new_head;
    }
    head->next = delete_odd(head->next);
    return head;
}

 ~cs1511/bin/autotest lab13 delete_odd

Revision Exercise: Insert n-th List element

lab13.c contains a function with this prototype:

struct node *insert_nth(int n, struct node *new_node, struct node *head)

Implement insert_nth.

insert_nth should insert new_node before position n in the list.

Given a position immediately after the last element in the list (n == length of the list) insert_nth should append new_node to the list.

insert_nth should otherwise make no changes if there is no position n in the list.

insert_nth should return the (possibly changed) head of the list.

As usual autotest is available to test your code:

 ~cs1511/bin/autotest lab13 insert_nth

An iterative solution for insert_nth

struct node *insert_nth(int n, struct node *new_node, struct node *head) {

    // insert node at start of list
    if (n == 0) {
        new_node->next = head;
        return new_node;
    }

    if (head == NULL) {
        return NULL;
    }

    int position = 0;
    struct node *p = head;

    // find node in position n - 1
    while (p->next != NULL) {
        if (position == n - 1) {
            // insert new_node after node in position n -1
            new_node->next = p->next;
            p->next = new_node;
            return head;
        }
        p = p->next;
        position++;
    }

    // append node to end of list
    if (position == n - 1) {
        p->next = new_node;
        new_node->next = NULL;
    }
    return head;
}

A recursive solution for insert_nthh

struct node *insert_nth(int n, struct node *new_node, struct node *head) {
    if (n == 0) {
        new_node->next = head;
        return new_node;
    }
    if (head == NULL) {
        return NULL;
    }
    head->next = insert_nth(n - 1, new_node, head->next);
    return head;
}

Requirements

Your functions must not create any new nodes. Your functions must not call malloc. Your functions must not call create_node.

Your functions must not change the data field of any node.

Your functions may change the next field of nodes.

Memory must be freed for nodes removed from the list.

Hints

If you change the first item in a list either by deleting or inserting a new item, you will need to return a new value for the head of a list.

Positions are numbered like array indices. The first node in the list is regarded as being in position 0. The last node in a list of length n is regarded as being in position n - 1.

Testing Your Functions

The main function in lab13.c contains code which allows you to test your functions.

The examples below demonstrate how to use the testing code.

These examples also indicate how your functions should behave.

dcc lab13.c -o lab13
./lab13
list = []
> append 4
list = [4]
> append 5
list = [4, 5]
> append 6
list = [4, 5, 6]
> append 7
list = [4, 5, 6, 7]
> append 6
list = [4, 5, 6, 7, 6]
> count 42
count(42) returns 0
list = [4, 5, 6, 7, 6]
> count 5
count(5) returns 1
list = [4, 5, 6, 7, 6]
> count 6
count(6) returns 2
list = [4, 5, 6, 7, 6]
> get_nth 0
get_nth(0) returned a pointer to a node containing 4
list = [4, 5, 6, 7, 6]
> get_nth 42
get_nth(42) returned NULL
list = [4, 5, 6, 7, 6]
> get_nth -1
get_nth(-1) returned NULL
list = [4, 5, 6, 7, 6]
> delete_nth 2
list = [4, 5, 7, 6]
> delete_nth 0
list = [5, 7, 6]
> delete_nth 0
list = [7, 6]
> insert_nth 0
list = [42, 7, 6]
> insert_nth 2
list = [42, 7, 42, 6]
> insert_nth 4
list = [42, 7, 42, 6, 42]
> delete_odd
list = [42, 42, 6, 42]

Note the test of insert_nth always insert a node containing 42.

A complete iterative solutions for lab13.c

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

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

// Return number of nodes in the list containing value.

int count(int value, struct node *head) {
    int how_many = 0;

    struct node *p = head;
    while (p != NULL) {
        if (p->data == value) {
            how_many++;
        }
        p = p->next;
    }

    return how_many;
}

// Return a pointer to the node in position n in the list.
// Position 0 is the first node in the list.
// Return NULL if the list has no n-th node.

struct node *get_nth(int n, struct node *head) {
    int position = 0;
    struct node *p = head;

    while (p != NULL) {
        if (position == n) {
            return p;
        }
        p = p->next;
        position++;
    }

    return NULL;
}

// Delete the node in position  n in the list.
// the deleted node is freed.
// The first node in the list is in position 0.
// Do nothing if there is no position n in the list.
// The head of the list is returned.

struct node *delete_nth(int n, struct node *head) {
    if (head == NULL) {
        return NULL;
    }

    if (n == 0) {
        struct node *new_head = head->next;
        free(head);
        return new_head;
    }

    int position = 0;
    struct node *p = head;

    // find node in position n - 1
    while (p->next != NULL) {
        if (position == n - 1) {
            struct node *new_next = p->next->next;
            free(p->next);
            p->next = new_next;
            return head;
        }
        p = p->next;
        position++;
    }

    return head;
}

// Delete all nodes in the list containing odd numbers.
// Any deleted nodes are freed.
// The head of the list is returned.

struct node *delete_odd(struct node *head) {
    if (head == NULL) {
        return NULL;
    }
    if (head->data % 2 == 1) {
        struct node *new_head = delete_odd(head->next);
        free(head);
        return new_head;
    }

    struct node *p = head;
    while (p->next != NULL) {
        if (p->next->data % 2 == 1) {
            struct node *new_next = p->next->next;
            free(p->next);
            p->next = new_next;
        } else {
            p = p->next;
        }
    }

    return head;
}

// Insert new_node before position n in the list.
// The first node in the list is in position 0.
// If n == length of the list, new_node is appended to list.
// Otherwise do nothing if there is no position n in the list.
// The head of the list is returned.

struct node *insert_nth(int n, struct node *new_node, struct node *head) {

    // insert node at start of list
    if (n == 0) {
        new_node->next = head;
        return new_node;
    }

    if (head == NULL) {
        return NULL;
    }

    int position = 0;
    struct node *p = head;

    // find node in position n - 1
    while (p->next != NULL) {
        if (position == n - 1) {
            // insert new_node after node in position n -1
            new_node->next = p->next;
            p->next = new_node;
            return head;
        }
        p = p->next;
        position++;
    }

    // append node to end of list
    if (position == n - 1) {
        p->next = new_node;
        new_node->next = NULL;
    }
    return head;
}

// THE CODE BELOW HERE IS TO TEST YOUR FUNCTIONS
// DO NOT CHANGE IT

void print_list(struct node *head);
struct node *reverse(struct node *list);
struct node *create_node(int data, struct node *next);
int length(struct node *head);
struct node *last(struct node *head);
struct node *append(struct node *head, int value);
void free_list(struct node *head);
static void check_list(struct node *head, char *name, int original_list_length, struct node *original_nodes[], int original_data_fields[]);

#define MAX_LINE 4096

// simple main function to test delete_first, delete_last, delete_contains, reverse

int
main(int argc, char *argv[]) {
    char line[MAX_LINE];
    struct node *list_head = NULL;

    while (1) {
        // save state of of list so we can check student functions
        // only perform permitted operations
        int list_length = length(list_head);
        struct node *nodes[list_length+1]; // ensure non-zero length for VLA
        int data[list_length+1];
        int j = 0;
        struct node *n = list_head;
        while (n != NULL) {
            nodes[j] = n;
            data[j] = n->data;
            n = n->next;
            j++;
        }

        printf("list = ");
        print_list(list_head);
        printf("\n");

        printf("> ");
        if (fgets(line, MAX_LINE, stdin) == NULL) {
            // free memory even though program is exiting
            // so we can check for memory not freed by other functions
            // by running dcc --leak-check
            free_list(list_head);
            return 0;
        }

        int i = 0;
        while (isalpha(line[i]) || line[i] == '_') {
            i++;
        }
        int argument = atoi(&line[i]);
        line[i] = '\0';

        if (strcmp(line, "append") == 0) {
            list_head = append(list_head, argument);
            continue; // need to skip check_list
        } else if (strcmp(line, "count") == 0) {
            printf("count(%d) returns %d\n", argument, count(argument, list_head));
        } else if (strcmp(line, "get_nth") == 0) {
            struct node *n = get_nth(argument, list_head);
            if (n == NULL) {
                printf("get_nth(%d) returned NULL\n", argument);
            } else {
                printf("get_nth(%d) returned a pointer to a node containing %d\n", argument, n->data);
            }
        } else if (strcmp(line, "delete_nth") == 0) {
            list_head = delete_nth(argument, list_head);
        } else if (strcmp(line, "insert_nth") == 0) {
            // insert a node containing 42
            struct node *new_node = create_node(42, NULL);
            list_head = insert_nth(argument, new_node, list_head);
            // include new node in nodes given to check_list
            nodes[list_length] = new_node;
            data[list_length] = new_node->data;
            list_length++;
        } else if (strcmp(line, "delete_odd") == 0) {
            list_head = delete_odd(list_head);
        } else if (strcmp(line, "") != 0) {
            printf("Unknown command: '%s'\n", line);
        }

        check_list(list_head, "returned list", list_length, nodes, data);
    }
}


// print contents of list in Python syntax

void print_list(struct node *head) {
    printf("[");
    for (struct node *n = head; n != NULL; n = n->next) {
        printf("%d", n->data);
        if (n->next != NULL) {
            printf(", ");
        }
    }
    printf("]");
}

// return pointer to last node in list
// NULL is returned if list is empty

struct node *last(struct node *head) {
    if (head == NULL || head->next == NULL) {
        return head;
    }
    return last(head->next);
}

int length(struct node *head) {
    int len = 0;
    for (struct node *n = head; n != NULL; n = n->next) {
        len++;
    }
    return len;
}

// create a new list node containing value
// and append it to end of list

struct node *append(struct node *head, int value) {
    // new node will be last in list, so next field is NULL
    struct node *n =  create_node(value, NULL);
    if (head == NULL) {
        // new node is now  head of the list
        return n;
    } else {
        // change next field of last list node
        // from NULL to new node
        last(head)->next = n;  /* append node to list */
        return head;
    }
}

// Create a new struct node containing the specified data,
// and next fields, return a pointer to the new struct node.

struct node *create_node(int data, struct node *next) {
    struct node *n;

    n = malloc(sizeof (struct node));
    if (n == NULL) {
        fprintf(stderr, "out of memory\n");
        exit(1);
    }
    n->data = data;
    n->next = next;
    return n;
}

void free_list(struct node *head) {
    if (head != NULL) {
        free_list(head->next);
        free(head);
    }
}

// You are not expected to understand the following code.
// It uses complex internal compiler features to
// print informative messages for student errors.

// detect clang address-sanitizer
#ifdef __has_feature
#if __has_feature(address_sanitizer)
// clang address-sanitizer
#define HAVE_ASAN
#endif
#endif

// detect gcc address-sanitizer
#ifdef __SANITIZE_ADDRESS__
#define HAVE_ASAN
#endif

#ifdef HAVE_ASAN
#include <sanitizer/asan_interface.h>
#include <stdint.h>
#include <string.h>

// return NULL if p appears to be a valid pointer to a malloc'ed region of size size
// otherwise return string describing pointer

static char *check_address_is_heap_pointer(void *p, size_t size) {
    if (!p)
        return NULL;
    if ((sizeof(p) == 8 && (uintptr_t)p == 0xbebebebebebebebe) || (sizeof(p) == 4 && (uintptr_t)p == 0xbebebebe))
        return "uninitialized";
    if (__asan_region_is_poisoned(p, size))
        return "invalid";
    char name[8]; // unused but required by __asan_locate_address
    void *region_address;
    size_t region_size;
    if (strcmp(__asan_locate_address(p, name, sizeof name, &region_address, &region_size), "heap") != 0)
        return "invalid (not from malloc)";
    return NULL;
}

// Use address-sanitizer and other methods to detect invalid pointers in a malloc'ed linked list
// name should be a string describing the list
// If original_nodes != NULL then every node is checked to ensure it is the array original_nodes
// If original_data_fields != NULL then every data field is checked to see if matches the element
// of original_data_fields at the same index as it node appears in original_nodes
// original_nodes and original_data_fields should be of length original_list_length

static void check_list(struct node *head, char *name, int original_list_length, struct node *original_nodes[], int original_data_fields[]) {
    char *pointer_description;
    if ((pointer_description = check_address_is_heap_pointer(head, sizeof *head))) {
        fprintf(stderr, "\nError: the head of %s is %s (%p)\n", name, pointer_description, head);
        exit(1);
    }
    int position = 0;
    for (struct node *n = head; n != NULL; n = n->next, position++) {
        // If you're getting an error here,
        // you have returned an invalid list
        int error = 0;
        if ((unsigned)n->data == 0xbebebebe) {
            fprintf(stderr, "Error: %s is invalid.\n", name);
            fprintf(stderr, "       The data field of node %d is uninitialized.\n", position);
            error = 1;
        }
        if ((pointer_description = check_address_is_heap_pointer(n->next, sizeof *(n->next)))) {
            if (!error)
                fprintf(stderr, "Error: %s is invalid.\n", name);
            fprintf(stderr, "       The next field of node %d is %s (%p).\n", position, pointer_description, n->next);
            error = 1;
        }
        if (error) {
            if (position) {
                fprintf(stderr, "       The data fields of nodes 0..%d in the list contain: [", position);
                for (struct node *m = head; m != n; m = m->next) {
                    fprintf(stderr, "%d, ", m->data);
                }
                fprintf(stderr, "%d]\n", n->data);
            }
            exit(1);
        }


        int position1 = 0;
        for (struct node *o = head;; o = o->next, position1++) {
            if (o == n->next) {
                if (position == position1) {
                    fprintf(stderr, "Error: %s is invalid.\n", name);
                    fprintf(stderr, "       The next field of node %d points to itself\n", position);
                } else  {
                    fprintf(stderr, "Error: %s is invalid.\n", name);
                    fprintf(stderr, "       The next field of node %d points to node %d.\n", position, position1);
                    fprintf(stderr, "       In other words, %s is circular.\n", name);
                }
                exit(1);
            }
            if (o == n)
                break;
        }

        if (original_list_length && original_nodes) {
            int i;
            for (i = 0; i < original_list_length; i++) {
                if (original_nodes[i] == n)
                    break;
            }

            if (i == original_list_length) {
                fprintf(stderr, "Error: %s is invalid.\n", name);
                fprintf(stderr, "       The node in position %d is not in the list it was given.\n", position);
                fprintf(stderr, "       Do not create new nodes with malloc\n");
                exit(1);
            }

            if (original_data_fields && original_data_fields[i] != n->data) {
                fprintf(stderr, "Error: %s is invalid.\n", name);
                fprintf(stderr, "       The node in position %d data field has been changed from %d to %d.\n", position, original_data_fields[i], n->data);
                fprintf(stderr, "       Do not change the data fields of nodes\n");
                exit(1);
            }
        }
    }
}
#else
static void check_list(struct node *head, char *name, int original_list_length, struct node *original_nodes[], int original_data_fields[]) {
}
#endif

A complete recursive solution for lab13.c

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

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

// Return number of nodes in the list containing value.

int count(int value, struct node *head) {
    if (head == NULL) {
        return 0;
    }

    if (head->data == value) {
        return 1 + count(value, head->next);
    } else {
        return count(value, head->next);
    }
}

// less readable but more concise version of count
// check your understanding of C by figuring out how it works

int count1(int value, struct node *head) {
    if (head == NULL) {
        return 0;
    } else {
        return ((head->data == value) + count(value, head->next));
    }
}

// a very concise version that uses C's ternary operator
// much less readable

int count2(int value, struct node *head) {
   return (head == NULL) ? 0 : ((head->data == value) + count(value, head->next));
}

// Return a pointer to the node in position n in the list.
// Position 0 is the first node in the list.
// Return NULL if the list has no n-th node.

struct node *get_nth(int n, struct node *head) {
    if (head == NULL) {
        return NULL;
    }
    if (n == 0) {
        return head;
    }
    return get_nth(n - 1, head->next);
}

// Delete the node in position  n in the list.
// the deleted node is freed.
// The first node in the list is in position 0.
// Do nothing if there is no position n in the list.
// The head of the list is returned.

struct node *delete_nth(int n, struct node *head) {
    if (head == NULL) {
        return NULL;
    }
    if (n == 0) {
        struct node *new_head = head->next;
        free(head);
        return new_head;
    }
    head->next = delete_nth(n - 1, head->next);
    return head;
}

// Delete all nodes in the list containing odd numbers.
// Any deleted nodes are freed.
// The head of the list is returned.

struct node *delete_odd(struct node *head) {
    if (head == NULL) {
        // list is empty no node to delete
        return NULL;
    }
    if (head->data % 2 == 1) {
        struct node *new_head = delete_odd(head->next);
        free(head);
        return new_head;
    }
    head->next = delete_odd(head->next);
    return head;
}

// Insert new_node before position n in the list.
// The first node in the list is in position 0.
// If n == length of the list, new_node is appended to list.
// Otherwise do nothing if there is no position n in the list.
// The head of the list is returned.

struct node *insert_nth(int n, struct node *new_node, struct node *head) {
    if (n == 0) {
        new_node->next = head;
        return new_node;
    }
    if (head == NULL) {
        return NULL;
    }
    head->next = insert_nth(n - 1, new_node, head->next);
    return head;
}

// THE CODE BELOW HERE IS TO TEST YOUR FUNCTIONS
// DO NOT CHANGE IT

void print_list(struct node *head);
struct node *reverse(struct node *list);
struct node *create_node(int data, struct node *next);
int length(struct node *head);
struct node *last(struct node *head);
struct node *append(struct node *head, int value);
void free_list(struct node *head);
static void check_list(struct node *head, char *name, int original_list_length, struct node *original_nodes[], int original_data_fields[]);

#define MAX_LINE 4096

// simple main function to test delete_first, delete_last, delete_contains, reverse

int
main(int argc, char *argv[]) {
    char line[MAX_LINE];
    struct node *list_head = NULL;

    while (1) {
        // save state of of list so we can check student functions
        // only perform permitted operations
        int list_length = length(list_head);
        struct node *nodes[list_length+1]; // ensure non-zero length for VLA
        int data[list_length+1];
        int j = 0;
        struct node *n = list_head;
        while (n != NULL) {
            nodes[j] = n;
            data[j] = n->data;
            n = n->next;
            j++;
        }

        printf("list = ");
        print_list(list_head);
        printf("\n");

        printf("> ");
        if (fgets(line, MAX_LINE, stdin) == NULL) {
            // free memory even though program is exiting
            // so we can check for memory not freed by other functions
            // by running dcc --leak-check
            free_list(list_head);
            return 0;
        }

        int i = 0;
        while (isalpha(line[i]) || line[i] == '_') {
            i++;
        }
        int argument = atoi(&line[i]);
        line[i] = '\0';

        if (strcmp(line, "append") == 0) {
            list_head = append(list_head, argument);
            continue; // need to skip check_list
        } else if (strcmp(line, "count") == 0) {
            printf("count(%d) returns %d\n", argument, count(argument, list_head));
        } else if (strcmp(line, "get_nth") == 0) {
            struct node *n = get_nth(argument, list_head);
            if (n == NULL) {
                printf("get_nth(%d) returned NULL\n", argument);
            } else {
                printf("get_nth(%d) returned a pointer to a node containing %d\n", argument, n->data);
            }
        } else if (strcmp(line, "delete_nth") == 0) {
            list_head = delete_nth(argument, list_head);
        } else if (strcmp(line, "insert_nth") == 0) {
            // insert a node containing 42
            struct node *new_node = create_node(42, NULL);
            list_head = insert_nth(argument, new_node, list_head);
            // include new node in nodes given to check_list
            nodes[list_length] = new_node;
            data[list_length] = new_node->data;
            list_length++;
        } else if (strcmp(line, "delete_odd") == 0) {
            list_head = delete_odd(list_head);
        } else if (strcmp(line, "") != 0) {
            printf("Unknown command: '%s'\n", line);
        }

        check_list(list_head, "returned list", list_length, nodes, data);
    }
}

// print contents of list in Python syntax

void print_list(struct node *head) {
    printf("[");
    for (struct node *n = head; n != NULL; n = n->next) {
        printf("%d", n->data);
        if (n->next != NULL) {
            printf(", ");
        }
    }
    printf("]");
}

// return pointer to last node in list
// NULL is returned if list is empty

struct node *last(struct node *head) {
    if (head == NULL || head->next == NULL) {
        return head;
    }
    return last(head->next);
}

// return length of list

int length(struct node *head) {
    if (head == NULL) {
        return 0;
    }
    return 1 + length(head->next);
}

// create a new list node containing value
// and append it to end of list

struct node *append(struct node *head, int value) {
    // new node will be last in list, so next field is NULL
    struct node *n =  create_node(value, NULL);
    if (head == NULL) {
        // new node is now  head of the list
        return n;
    } else {
        // change next field of last list node
        // from NULL to new node
        last(head)->next = n;  /* append node to list */
        return head;
    }
}

// Create a new struct node containing the specified data,
// and next fields, return a pointer to the new struct node.

struct node *create_node(int data, struct node *next) {
    struct node *n;

    n = malloc(sizeof (struct node));
    if (n == NULL) {
        fprintf(stderr, "out of memory\n");
        exit(1);
    }
    n->data = data;
    n->next = next;
    return n;
}

void free_list(struct node *head) {
    if (head != NULL) {
        free_list(head->next);
        free(head);
    }
}

// You are not expected to understand the following code.
// It uses complex internal compiler features to
// print informative messages for student errors.

// detect clang address-sanitizer
#ifdef __has_feature
#if __has_feature(address_sanitizer)
// clang address-sanitizer
#define HAVE_ASAN
#endif
#endif

// detect gcc address-sanitizer
#ifdef __SANITIZE_ADDRESS__
#define HAVE_ASAN
#endif

#ifdef HAVE_ASAN
#include <sanitizer/asan_interface.h>
#include <stdint.h>
#include <string.h>

// return NULL if p appears to be a valid pointer to a malloc'ed region of size size
// otherwise return string describing pointer

static char *check_address_is_heap_pointer(void *p, size_t size) {
    if (!p)
        return NULL;
    if ((sizeof(p) == 8 && (uintptr_t)p == 0xbebebebebebebebe) || (sizeof(p) == 4 && (uintptr_t)p == 0xbebebebe))
        return "uninitialized";
    if (__asan_region_is_poisoned(p, size))
        return "invalid";
    char name[8]; // unused but required by __asan_locate_address
    void *region_address;
    size_t region_size;
    if (strcmp(__asan_locate_address(p, name, sizeof name, &region_address, &region_size), "heap") != 0)
        return "invalid (not from malloc)";
    return NULL;
}

// Use address-sanitizer and other methods to detect invalid pointers in a malloc'ed linked list
// name should be a string describing the list
// If original_nodes != NULL then every node is checked to ensure it is the array original_nodes
// If original_data_fields != NULL then every data field is checked to see if matches the element
// of original_data_fields at the same index as it node appears in original_nodes
// original_nodes and original_data_fields should be of length original_list_length

static void check_list(struct node *head, char *name, int original_list_length, struct node *original_nodes[], int original_data_fields[]) {
    char *pointer_description;
    if ((pointer_description = check_address_is_heap_pointer(head, sizeof *head))) {
        fprintf(stderr, "\nError: the head of %s is %s (%p)\n", name, pointer_description, head);
        exit(1);
    }
    int position = 0;
    for (struct node *n = head; n != NULL; n = n->next, position++) {
        // If you're getting an error here,
        // you have returned an invalid list
        int error = 0;
        if ((unsigned)n->data == 0xbebebebe) {
            fprintf(stderr, "Error: %s is invalid.\n", name);
            fprintf(stderr, "       The data field of node %d is uninitialized.\n", position);
            error = 1;
        }
        if ((pointer_description = check_address_is_heap_pointer(n->next, sizeof *(n->next)))) {
            if (!error)
                fprintf(stderr, "Error: %s is invalid.\n", name);
            fprintf(stderr, "       The next field of node %d is %s (%p).\n", position, pointer_description, n->next);
            error = 1;
        }
        if (error) {
            if (position) {
                fprintf(stderr, "       The data fields of nodes 0..%d in the list contain: [", position);
                for (struct node *m = head; m != n; m = m->next) {
                    fprintf(stderr, "%d, ", m->data);
                }
                fprintf(stderr, "%d]\n", n->data);
            }
            exit(1);
        }


        int position1 = 0;
        for (struct node *o = head;; o = o->next, position1++) {
            if (o == n->next) {
                if (position == position1) {
                    fprintf(stderr, "Error: %s is invalid.\n", name);
                    fprintf(stderr, "       The next field of node %d points to itself\n", position);
                } else  {
                    fprintf(stderr, "Error: %s is invalid.\n", name);
                    fprintf(stderr, "       The next field of node %d points to node %d.\n", position, position1);
                    fprintf(stderr, "       In other words, %s is circular.\n", name);
                }
                exit(1);
            }
            if (o == n)
                break;
        }

        if (original_list_length && original_nodes) {
            int i;
            for (i = 0; i < original_list_length; i++) {
                if (original_nodes[i] == n)
                    break;
            }

            if (i == original_list_length) {
                fprintf(stderr, "Error: %s is invalid.\n", name);
                fprintf(stderr, "       The node in position %d is not in the list it was given.\n", position);
                fprintf(stderr, "       Do not create new nodes with malloc\n");
                exit(1);
            }

            if (original_data_fields && original_data_fields[i] != n->data) {
                fprintf(stderr, "Error: %s is invalid.\n", name);
                fprintf(stderr, "       The node in position %d data field has been changed from %d to %d.\n", position, original_data_fields[i], n->data);
                fprintf(stderr, "       Do not change the data fields of nodes\n");
                exit(1);
            }
        }
    }
}
#else
static void check_list(struct node *head, char *name, int original_list_length, struct node *original_nodes[], int original_data_fields[]) {
}
#endif

Submission/Assessment

These revision exercises are not assessable.

They do not get marked.

There is no need to submit them with give.