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.

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