Start New Discussion within our **Software Development Community** # 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;
}
```