List Homework

September 7, 2018

For many students, school started a few weeks ago, so today’s exercise is typical of homework:

  1. Write a program to determine the length of a linked list.
  2. Write a program to reverse a linked list.

Your task is to write the two list exercises described above; write them as if you are three weeks into your first data structures class. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

Advertisements

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}
    

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: