## 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

### One Response to “List Homework”

1. Daniel said

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