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

struct element {
    int data;
    struct element *next;
};

typedef struct element *list;

list list_create() {
    return NULL;
}

bool list_is_empty(list l) {
    return l == NULL;
}

list list_push(list l, int val) {
    struct element *e = malloc(sizeof(*e));
    e->next = NULL;
    e->data = val;
    if (list_is_empty(l)) {
        return e;
    } else if (val < l->data) {
        e->next = l;
        return e;
    } else {
        struct element *crt = l;
        while (NULL != crt && val > crt->next->data) {
            crt = crt->next;
        }
        e->next = crt->next;
        crt->next = e;
        return l;
    }
}

list list_extract(list l, int val) {
    struct element *crt = l;
    struct element *prec = l;
    if (list_is_empty(l)) {
        return l;
    } else if (val == crt->data) {
        l = crt->next;
        free(crt);
        return l;
    } else {
        while (crt->next != NULL && crt->data < val) {
            prec = crt;
            crt = crt->next;
        }
        if (val == crt->data) {
            prec->next = crt->next;
            free(crt);
        }
        return l;
    }
}

struct element *list_search(list l, int val) {
    struct element *crt = l;
    while (crt->next != NULL && crt->data < val) {
        crt = crt->next;
    }
    if (val == crt->data) {
        return crt;
    }
    return NULL;
}

void list_destroy(list *l) {
    struct element *crt = *l;
    while (crt != NULL) {
        struct element *e = crt;
        crt = crt->next;
        free(e);
    }
    *l = NULL;
}

void print_safe(struct element *e) {
    if (e != NULL) {
        printf("%d\n", e->data);
    }
}

int main() {
    list l = list_create();
    l = list_extract(l, 2);
    l = list_push(l, 10);
    l = list_push(l, 0);
    l = list_push(l, 2);
    printf("first %d\n", l->data);
    printf("second %d\n", l->next->data);
    printf("third %d\n", l->next->next->data);
    struct element *e = list_search(l, 2);
    print_safe(e);
    /*printf("two %d\n", e->data);*/
    e = list_search(l, 10);
    print_safe(e);
    /*printf("ten %d\n", e->data);*/
    e = list_search(l, 0);
    print_safe(e);
    /*printf("zero %d\n", e->data);*/
    e = list_search(l, 3);
    print_safe(e);
    /*printf("absent %p\n", e);*/
    e = list_search(l, 190);
    print_safe(e);
    /*printf("bigger %p\n", e);*/
    e = list_search(l, -1);
    print_safe(e);
    /*printf("smaller %p\n", e);*/
    l = list_extract(l, 2);
    l = list_extract(l, 100);
    printf("first %d\n", l->data);
    printf("second %d\n", l->next->data);
    l = list_extract(l, 0);
    printf("first %d\n", l->data);
    list_destroy(&l);
}
