Friday, March 3, 2017

Simple example of linked list operations in C

Here's a quick and simple implementation of basic routines on linked lists in the C programming language. The length or the list is limited to MAX items and each node can have a max value of MAX_VAL.
#include <stdlib.h>
#include <stdio.h>
#include <time.h>
#include <assert.h>

#define MIN      1
#define MAX      10
#define MAX_VAL  30

typedef struct node {
    int val;
    struct node *next;
} node_t;

static int list_len = 0;

void
print_list(node_t *head)
{
    node_t *node = head;
    int cnt = 0;

    while (node != NULL) {
        printf("[%d] %d\n", cnt, node->val);
        node = node->next;
        assert(++cnt <= list_len);
    }
}

int
grow_list(node_t **head)
{
    node_t *node;
    int i, len;

    do {
        len = rand() % MAX;
    } while (len < MIN);

    printf("adding %d entries to the list\n", len);

    if (*head != NULL) {
        node = *head;

        do {
            ;
        } while ((node = node->next) != NULL);
    }

    for (i = 0; i < len; i++) {
        node = calloc(1, sizeof (*node));
        node->val = rand() % MAX_VAL;

        node->next = *head;
        *head = node;
    }

    return (len);
}

void
reverse_list(node_t **head)
{
    node_t *node = *head, *new_head = NULL;

    if (*head == NULL) {
        return;
    }

    printf("reversing list\n");

    while (node != NULL) {
        *head = node->next;
        node->next = new_head;
        new_head = node;
        node = *head;
    }

    assert(*head == NULL);

    *head = new_head;
}

void
remove_node(node_t **head)
{
    node_t *node, *prev;
    int idx = 0, i = 0;

    if (*head == NULL) {
        return;
    }

    do {
        idx = rand() % list_len;
    } while (idx == 0);

    printf("removing item %d\n", idx);

    node = *head;

    do {
        prev = node;
    } while ((node = node->next) != NULL && ++i < idx);

    prev->next = node->next;
    free(node);
}

int
main(int argc, char **argv)
{
    node_t *head = NULL;

    srand(time(NULL));

    list_len += grow_list(&head);
    print_list(head);

    reverse_list(&head);
    print_list(head);

    list_len += grow_list(&head);
    print_list(head);

    reverse_list(&head);
    print_list(head);

    remove_node(&head);
    print_list(head);

    return (0);
}

No comments:

Post a Comment