List Homework

September 7, 2018

We’ve done these before, but it doesn’t hurt to do them again. First, a simple recursive version of the list-length program:

(define (len xs)
  (if (null? xs) 0
    (+ (len (cdr xs)) 1)))

> (len '(1 2 3 4 5))
5

That works, but it’s not tail recursive, because len isn’t in tail position (it is inside the call to +), so the function operates in linear time and space; here is a better version:

(define (len-aux xs len)
  (if (null? xs) len
    (len-aux (cdr xs) (+ len 1))))

(define (len xs) (len-aux xs 0))

> (len '(1 2 3 4 5))
5

Now len-aux is in tail position; the function operates in linear time and constant space. Here we reverse a list, using a tail recursive function:

(define (rev-aux xs zs)
  (if (null? xs) zs
    (rev-aux (cdr xs) (cons (car xs) zs))))

(define (rev xs) (rev-aux xs '()))

> (rev '(1 2 3 4 5))
(5 4 3 2 1)

You can run the program at https://ideone.com/x46jpU.

Pages: 1 2

Posted by programmingpraxis
Filed in Exercises
1 Comment »

One Response to “List Homework”

  1. Daniel said
    September 7, 2018 at 9:49 PM

    Here’s a solution in C.

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

typedef struct node {
    int value;
    struct node* next;
} node_t;

void reverse(node_t** list) {
    node_t* prev = NULL;
    node_t* node = NULL;
    node_t* next = *list;
    while (next != NULL) {
        prev = node;
        node = next;
        next = next->next;
        node->next = prev;
    }
    *list = node;
}

size_t length(node_t* list) {
    size_t result = 0;
    node_t* node = list;
    while (node != NULL) {
        ++result;
        node = node->next;
    }
    return result;
}

void print_list(node_t* list) {
    node_t* node = list;
    printf("{");
    while (node != NULL) {
        printf("%d", node->value);
        node = node->next;
        if (node) printf("->");
    }
    printf("}");
}

int main(int argc, char* argv[]) {
    node_t* list = NULL;
    for (int i = argc - 1; i > 0; --i) {
        node_t* node = (node_t*)malloc(sizeof(node_t));
        node->next = list;
        node->value = atoi(argv[i]);
        list = node;
    }
    printf("list:\n  ");
    print_list(list);
    printf("\n");
    size_t len = length(list);
    printf("len(list):\n  %zu\n", len);
    reverse(&list);
    printf("reverse(list):\n  ");
    print_list(list);
    printf("\n");
    node_t* node = list;
    while (node != NULL) {
        node_t* next = node->next;
        free(node);
        node = next;
    }
    return EXIT_SUCCESS;
}

    Example Usage:

    $ ./a.out {1..10}
list:
  {1->2->3->4->5->6->7->8->9->10}
len(list):
  10
reverse(list):
  {10->9->8->7->6->5->4->3->2->1}

Leave a comment