Probabilistic Linked Skip List

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

struct node {
  int data;
  struct node *right;
  struct node *down;
};

struct list {
  struct node *head;
  int level;
};

/*
Naive example function
Don't use in production code
*/

int rand_level(int limit)
{
  int i = 1;

  while (rand() < RAND_MAX / 2 && i < limit) {
    ++i;
  }

  return i;
}

struct node *make_node(int data, struct node *right, struct node *down)
{
  struct node *node = malloc(sizeof *node);

  if (node == NULL) {
    return NULL;
  }

  node->data = data;
  node->right = right;
  node->down = down;

  return node;
}

void destroy_node(struct node *node)
{
  free(node);
}

int insert_node(struct list *list, int data)
{
  struct node *x, *save = NULL;
  int i, level = rand_level(list->level + 1);

  while (level > list->level) {
    ++list->level;
    list->head = make_node(0, NULL, list->head);
  }

  x = list->head;

  for (i = list->level; x != NULL; i--) {
    while (x->right != NULL && data > x->right->data) {
      x = x->right;
    }

    if ( i <= level ) {
      if (x->right == NULL || data != x->right->data) {
        x->right = make_node(data, x->right, NULL);
      }

      if (save != NULL) {
        save->down = x->right;
      }

      save = x->right;
    }

    x = x->down;
  }

  return 1;
}

int remove_node(struct list *list, int data)
{
  int ret = 0;
  struct node *x, *save;

  x = list->head;

  while (x != NULL) {
    while (x->right != NULL && data > x->right->data) {
      x = x->right;
    }

    if (x->right != NULL && data == x->right->data) {
      save = x->right;
      x->right = save->right;
      destroy_node(save);

      ret = 1;
    }

    x = x->down;
  }

  while (list->head != NULL && list->head->right == NULL) {
    save = list->head;
    list->head = list->head->down;
    destroy_node(save);
  }

  return ret;
}

void list_structure(struct list *list)
{
  struct node *x, *y, *z;

  for (x = list->head; x != NULL; x = x->down) {
    for (z = list->head; z->down != NULL; z = z->down) {
    }

    for (y = x; y != NULL; y = y->right) {
      for (; z != NULL && z->data != y->data; z = z->right) {
        printf("-");

        if (z->right != NULL && z->right->data != y->data) {
          printf("--");
        }
      }

      printf("%02d", y->data);
    }

    printf("\n");
  }
}

int main(void)
{
  struct list list = {0};
  int i;

  srand((unsigned int)time(NULL));

  for (i = 0; i < 25; i++) {
    insert_node(&list, rand() % 99 + 1);

    list_structure(&list);
    printf("\n=========================\n");

    getchar();
  }

  return 0;
}