COMS 3157 Advanced Programming

Index of 2025-9/code/10

Parent directory
free-nodes.c
two-nodes.c

free-nodes.c

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

struct Node {
    struct Node *next;
    int val;
};

/*
 * free_all_nodes() is rewritten to enable tail recursion.
 * Compile with gcc -O2 to enable tail recursion optimization.
 *
 * Run it with a large numner of nodes (like one million) to see
 * non-optimized binary stack-overflowing whereas the tail-optimized
 * version runs with no problem.
 *
 * You can also see the disassembly with objdump -d to see 
 * the tail-optimized version do not have a recursive call.
 */
void free_all_nodes(struct Node *head) {
    if (head == NULL) {
        return;
    }
    struct Node *head_next = head->next;
    free(head);
    free_all_nodes(head_next);
}

int main(int argc, char **argv) {
    assert(argc == 2);
    int n = atoi(argv[1]);
    struct Node *head = NULL;
    struct Node *node;

    while (n) {
        node = malloc(sizeof(struct Node));
        if (!node) {
            perror("malloc failed");
            exit(1);
        }
        node->val = n;
        node->next = head;
        head = node;
        n--;
    }

    /*
    for (node = head; node; node = node->next) {
        printf("-> %d ", node->val);
    }
    printf("\n");
    */

    free_all_nodes(head);
}

two-nodes.c

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

struct Node {
    struct Node *next;
    int val;
};

struct Node *create2Nodes(int x, int y)
{
    struct Node *n2 = malloc(sizeof(struct Node));
    if (!n2) {
        return NULL;
    }
    n2->val = y;
    n2->next = NULL;

    struct Node *n1 = malloc(sizeof(struct Node));
    if (!n1) {
        free(n2);    // don't forget to free the node we already allocated
        return NULL;
    }
    n1->val = x;
    n1->next = n2;  // n1 --> n2 --> NULL
    return n1;
}

int main()
{
    struct Node *head = create2Nodes(10, 20);
    if (head == NULL) {
        exit(1);
    }

    //         +----+   +----+----+   +----+----+
    //   head: |  --|-->| 10 |  --|-->| 20 |NULL|
    //         +----+   +----+----+   +----+----+

    printf("%d --> %d\n", head->val, head->next->val);

    free(head->next);  // must free the last node first
    free(head);
}