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.
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}