#include 
#include 
#include 
#include 

struct __LLNode {
	int val;
	struct __LLNode *next;
};

typedef struct __LLNode LLNode;

size_t LL_length(LLNode *root);
void LL_free(LLNode **root);

LLNode *LL_create_node(int val) {
	LLNode *node = (LLNode*)malloc(sizeof(LLNode));
	node->val = val;
	node->next = NULL;
	return node;
}

void LL_push_back(LLNode **root, LLNode *val) {
	if (root == NULL) {
		*root = val;
		return;
	}

	LLNode *current = *root;

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

	current->next = val;
}

bool LL_insert_at(LLNode **root, LLNode *val, size_t index) {
	if (index == 0) {
		LLNode *tmp = *root;
		*root = val;
		val->next = tmp;
		return true;
	}

	if (LL_length(*root) < index) {
		return false;
	}

	LLNode *current = *root;
	index--;

	while (index--) {
		current = current->next;
	}


	LLNode *tmp = current->next;
	current->next = val;
	val->next = tmp;

	return false;
}

bool LL_delete_at(LLNode **root, size_t index) {
	if (index == 0 && root != NULL) {
		*root = (*root)->next;
		return true;
	}

	if (LL_length(*root) < index) {
		return false;
	}

	LLNode *current = *root;
	index--;

	while (index--) {
		current = current->next;
	}


	LLNode *tmp = current->next->next;
	LLNode *del = current->next;
	del->next = NULL;
	LL_free(&del);

	current->next = tmp;

	return true;
}

size_t LL_length(LLNode *root) {
	if (root == NULL) return 0;

	LLNode *current = root;
	size_t len = 1;

	while (current->next != NULL) {
		current = current->next;
		len++;
	}

	return len;
}

void LL_display(LLNode *root) {
	if (root == NULL) {
		printf("\n");
		return;
	}

	printf("%d", root->val);
	LLNode *current = root->next;
	while (current) {
		printf(" -> %d", current->val);
		current = current->next;
	}

	printf("\n");
}

void LL_free(LLNode **node) {
	LLNode *current = *node;
	while (current->next) {
		LLNode *tmp = current;
		current = current->next;

		free(tmp);
	}

	free(current);

	*node = NULL;
}

typedef struct {
	LLNode *root;
	size_t sz;
} Stack;

Stack *Stack_new() {
	Stack *stack = (Stack *)malloc(sizeof(Stack));
	if (!stack) return NULL;

	stack->root = LL_create_node(INT_MAX);
	stack->sz = 0;

	return stack;
}

int Stack_top(Stack *stack) {
	return stack->root->next->val;
}

void Stack_push(Stack *stack, int val) {
	LLNode *cur = stack->root;

	while (cur->next) {
		cur = cur->next;
	}

	cur->next = LL_create_node(val);
}

int Stack_pop(Stack *stack) {
	LLNode *prev = stack->root;
	LLNode *cur = stack->root->next;

	while (cur->next) {
		prev = cur;
		cur = cur->next;
	}

	prev->next = NULL;
	return cur->val;
}

bool Stack_is_empty(Stack *stack) {
	return stack->root->next == NULL;
}

int main() {
	Stack *st = Stack_new();

	for (int i = 1; i <= 10; i++) {
		Stack_push(st, i);
	}

	printf("Stack is %s\n", Stack_is_empty(st) ? "empty" : "not empty");

	while (!Stack_is_empty(st)) {
		printf("%d ", Stack_pop(st));
	}
	printf("\n");

	return 0;
}