COMP1511 Revision Linked Lists Sample Solutions

Revision Video: Linked Lists - Prerequisites

Revision Video: Linked Lists - Creating and traversing a linked list (Coding)

Revision Video: Linked List - Sorted Insert

Revision Video: Linked Lists - Adding elements to a Linked List (Coding)

Revision Video: Linked List - Delete

Revision Video: Linked Lists - Deleting elements from a Linked List (Coding)

Revision Exercise: Sum the elements in a Linked List

Download list_sum.c here, or copy it to your CSE account using the following command:

cp -n /web/cs1511/21T3/activities/list_sum/list_sum.c .

Your task is to add code to this function in list_sum.c:

// Return the sum of the elements in the linked list pointed by head
int sum(struct node *head) {

    // PUT YOUR CODE HERE (change the next line!)
    return 42;

}
sum is given one argument, head, which is the pointer to the first node in a linked list.

Add code to sum so that its returns the sum of the list.

For example if the linked list contains these 8 elements:

1, 7, 8, 9, 13, 19, 21, 42

sum should return 120 because 1 + 7 + 8 + 9 + 13 + 19 + 21 + 42 = 120.

Testing

list_sum.c also contains a main function which allows you to test your sum function.

This main function:

  • converts the command-line arguments to a linked list
  • assigns a pointer to the first node in the linked list to head
  • calls list_sum(head)
  • prints the result.

Do not change this main function. If you want to change it, you have misread the question.

Your list_sum function will be called directly in marking. The main function is only to let you test your list_sum function

Here is how you use main function allows you to test list_sum:

dcc list_sum.c -o list_sum
./list_sum 1 2 4 8 16 32 64 128 256
511
./list_sum 2 4 6 5 8 9
34
./list_sum 13 15 17 17 18
80
./list_sum 42 4
46
./list_sum
0

Assumptions/Restrictions/Clarifications.

sum should return a single integer.

sum should not change the linked list it is given. Your function should not change the next or data fields of list nodes.

sum should not use arrays.

sum should not call malloc.

sum should not call scanf (or getchar or fgets).

sum should not print anything. It should not call printf.

Do not change the supplied main function. It will not be tested or marked.

When you think your program is working you can use autotest to run some simple automated tests:

1511 autotest list_sum
Sample solution for list_sum.c
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>

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

int sum(struct node *head);
struct node *strings_to_list(int len, char *strings[]);

int main(int argc, char *argv[]) {
    // create linked list from command line arguments
    struct node *head = strings_to_list(argc - 1, &argv[1]);

    int result = sum(head);
    printf("%d\n", result);

    return 0;
}

// Return sum of a linked list.
int sum(struct node *head) {
    int total = 0;
    struct node *n = head;
    while (n != NULL) {
        total = total + n->data;
        n = n->next;
    }
    return total;
}


// create linked list from array of strings
struct node *strings_to_list(int len, char *strings[]) {
    struct node *head = NULL;
    for (int i = len - 1; i >= 0; i = i - 1) {
        struct node *n = malloc(sizeof (struct node));
        assert(n != NULL);
        n->next = head;
        n->data = atoi(strings[i]);
        head = n;
    }
    return head;
}
Alternative solution for list_sum.c
#include <stdio.h>
#include <assert.h>

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

// Return sum of a linked list.
int sum(struct node *head) {
    if (head == NULL) {
        return 0;
    }
    return head->data + sum(head->next);
}

Revision Exercise: Count Elements Divisible by 17 in Linked List

Download list_count_favourite.c here, or copy it to your CSE account using the following command:

cp -n /web/cs1511/21T3/activities/list_count_favourite/list_count_favourite.c .

Your task is to add code to this function in list_count_favourite.c:

// Return the number of elements divisible by 17 in the linked list
int count_favourite(struct node *head) {

    // PUT YOUR CODE HERE (change the next line!)
    return 42;

}
count_favourite is given one argument, head, which is the pointer to the first node in a linked list.

Add code to count_favourite so that its returns the number of elements divisible by 17 in the list.

For example if the linked list contains these 8 elements:

51, 7, 8, 9, 34, 19, 34, 42

count_favourite should return 3 because 51, 34 and 34 are divisible by 17.

Testing

list_count_favourite.c also contains a main function which allows you to test your count_favourite function.

This main function:

  • converts the command-line arguments to a linked list
  • assigns a pointer to the first node in the linked list to head
  • calls list_count_favourite(head)
  • prints the result.

Do not change this main function. If you want to change it, you have misread the question.

Your list_count_favourite function will be called directly in marking. The main function is only to let you test your list_count_favourite function

Here is how you use main function allows you to test list_count_favourite:

dcc list_count_favourite.c -o list_count_favourite
./list_count_favourite 51 7 8 9 34 19 34 42
3
./list_count_favourite 2 4 6 5 8 9
0
./list_count_favourite 17 34 51 68 85 102 119 136 153
9
./list_count_favourite
0

Assumptions/Restrictions/Clarifications.

count_favourite should return a single integer.

count_favourite should not change the linked list it is given. Your function should not change the next or data fields of list nodes.

count_favourite should not use arrays.

count_favourite should not call malloc.

count_favourite should not call scanf (or getchar or fgets).

count_favourite should not print anything. It should not call printf.

Do not change the supplied main function. It will not be tested or marked.

When you think your program is working you can use autotest to run some simple automated tests:

1511 autotest list_count_favourite
Sample solution for list_count_favourite.c
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>

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

int count_favourite(struct node *head);
struct node *strings_to_list(int len, char *strings[]);

int main(int argc, char *argv[]) {
    // create linked list from command line arguments
    struct node *head = strings_to_list(argc - 1, &argv[1]);

    int result = count_favourite(head);
    printf("%d\n", result);

    return 0;
}

// Return the number of elements divisible by 17 in the linked list
int count_favourite(struct node *head) {
    int count = 0;
    struct node *n = head;
    while (n != NULL) {
        if (n->data % 17 == 0) {
            count = count + 1;
        }
        n = n->next;
    }
    return count;
}


// create linked list from array of strings
struct node *strings_to_list(int len, char *strings[]) {
    struct node *head = NULL;
    for (int i = len - 1; i >= 0; i = i - 1) {
        struct node *n = malloc(sizeof (struct node));
        assert(n != NULL);
        n->next = head;
        n->data = atoi(strings[i]);
        head = n;
    }
    return head;
}
Alternative solution for list_count_favourite.c
#include <stdio.h>
#include <assert.h>

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

// Return the number of elements divisible by 17 in the linked list
int count_favourite(struct node *head) {
    if (head == NULL) {
        return 0;
    }
    return (head->data % 17 == 0) + count_favourite(head->next);
}

Revision Exercise: Return Nth Element of Linked List

Download list_get_nth.c here, or copy it to your CSE account using the following command:

cp -n /web/cs1511/21T3/activities/list_get_nth/list_get_nth.c .

Your task is to add code to this function in list_get_nth.c:

// Return the n-th element of linked list.
// n == 0 returns first element, n == 1, second element, ....
int get_nth(int n, struct node *head) {

    // PUT YOUR CODE HERE (change the next line!)
    return 42;

}
get_nth is given two arguments, an int n and head, which is the pointer to the first node in a linked list.

Add code to get_nth so that its returns the n-th element the linked element of the linked list.

The elements are counted in the same manner as array elements (zero-based), so the first element in the list is regarded as at position 0, the second element position 1 and so on.

get_nth can assume that the list contains at least n + 1 elements.

For example if the linked list contains these 8 elements:

1, 7, 8, 9, 13, 19, 21, 42

if n is 1 get_nth should return 7.

Testing

list_get_nth.c also get_nth a main function which allows you to test your get_nth function.

This main function:

  • converts the first command-line argument to n
  • converts the remaining command-line arguments to a linked list
  • assigns a pointer to the first node in the linked list to head
  • calls list_get_nth(n, head)
  • prints the result.

Do not change this main function. If you want to change it, you have misread the question.

Your list_get_nth function will be called directly in marking. The main function is only to let you test your list_get_nth function

Here is how you use main function allows you to test list_get_nth:

dcc list_get_nth.c -o list_get_nth
./list_get_nth 0  5 6 7 8
5
./list_get_nth 1  5 6 7 8
6
./list_get_nth 2  5 6 7 8
7
./list_get_nth 3  5 6 7 8
8
./list_get_nth 0  42
42

Assumptions/Restrictions/Clarifications.

get_nth should return a single integer.

get_nth can assume n is non-negative.

get_nth can assume the linked list contains at least n + 1 elements.

get_nth should not change the linked list it is given. Your function should not change the next or data fields of list nodes.

get_nth should not use arrays.

get_nth should not call malloc.

get_nth should not call scanf (or getchar or fgets).

get_nth should not print anything. It should not call printf.

Do not change the supplied main function. It will not be tested or marked.

When you think your program is working you can use autotest to run some simple automated tests:

1511 autotest list_get_nth
Sample solution for list_get_nth.c
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>

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

int get_nth(int n, struct node *head);
struct node *strings_to_list(int len, char *strings[]);

int main(int argc, char *argv[]) {
    if (argc < 2) {
        fprintf(stderr, "Usage: %s value list-elements\n", argv[0]);
        return 1;
    }

    int value = atoi(argv[1]);
    // create linked list from command line arguments
    struct node *head = strings_to_list(argc - 2, &argv[2]);

    int result = get_nth(value, head);
    printf("%d\n", result);

    return 0;
}

// Return the n-th element of linked list.
// n == 0 returns first element, n == 1, second element, ....
int get_nth(int n, struct node *head) {
    assert(n >= 0);
    struct node *p = head;
    int i = n;
    while (i > 0) {
        assert(p != NULL);
        p = p->next;
        i = i - 1;
    }
    assert(p != NULL);
    return p->data;
}


// create linked list from array of strings
struct node *strings_to_list(int len, char *strings[]) {
    struct node *head = NULL;
    for (int i = len - 1; i >= 0; i = i - 1) {
        struct node *n = malloc(sizeof (struct node));
        assert(n != NULL);
        n->next = head;
        n->data = atoi(strings[i]);
        head = n;
    }
    return head;
}
Alternative solution for list_get_nth.c
#include <stdio.h>
#include <assert.h>

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

// Return the n-th element of linked list.
// n == 0 returns first element, n == 1, second element, ....
int get_nth(int n, struct node *head) {
    assert(head != NULL && n >= 0);
    if (n == 0) {
        return head->data;
    }
    return get_nth(n - 1, head->next);
}