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

typedef int BOOL;
#define TRUE 1
#define FALSE 0

typedef struct node 
{
	int value;
	struct node *next;
	struct node *prev;
} Node;

typedef struct
{
	int value;
	BOOL flag;
} ListValue;

static Node* HEAD;
static Node* TAIL;

static int LENGTH = 0;

// O(1) operation, no growth by input
BOOL append(int value)
{
	Node* new_head = malloc(sizeof(Node));
	if (new_head == NULL)
		return FALSE;

	new_head->value = value;
	new_head->prev = HEAD;

	if (HEAD != NULL)
		HEAD->next = new_head;
	else
		TAIL = new_head;

	HEAD = new_head;
	++LENGTH;

	return TRUE;
}

// O(1) operation, no growth by input
BOOL prepend(int value)
{
	Node* new_tail = malloc(sizeof(Node));
	if (new_tail == NULL)
		return FALSE;

	new_tail->value = value;
	new_tail->next = TAIL;

	if (TAIL != NULL)
		TAIL->prev = new_tail;
	else
		HEAD = new_tail;

	TAIL = new_tail;
	++LENGTH;

	return TRUE;
}

// O(n) operation, the longer the list, the longer the search, by N in the worst case
Node* get_node(int index)
{
	if (TAIL == NULL)
		return NULL;

	Node* iterator = TAIL;
	while (index > 0 && iterator->next != NULL)
	{
		--index;
		iterator = iterator->next;
	}

	if (index > 0)
		return NULL;

	return iterator;
}

// O(n) operation, the longer the list, the longer the search, by N in the worst case
ListValue get(int index)
{
	ListValue result = { 0, FALSE };

	Node* iterator = get_node(index);
	if (iterator == NULL)
		return result;

	result.flag = TRUE;
	result.value = iterator->value;

	return result;
}

// O(n) operation, the longer the list, the longer the search, by N in the worst case
BOOL insert_at(int index, int value)
{
	Node* iterator = get_node(index);
	if (iterator == NULL)
		return FALSE;

	Node* new_node = malloc(sizeof(Node));
	if (new_node == NULL)
		return FALSE;

	new_node->value = value;
	new_node->next = iterator;

	if (iterator->prev)
	{
		new_node->prev = iterator->prev;
		iterator->prev->next = new_node;
	}
	else
		TAIL = new_node;
	
	++LENGTH;
	return TRUE;
}

// O(n) operation, the longer the list, the longer the search, by N in the worst case
BOOL remove_at(int index)
{
	Node* iterator = get_node(index);
	if (iterator == NULL)
		return FALSE;

	if (HEAD != TAIL)
	{
		if (iterator->next)
			iterator->next->prev = iterator->prev;
		else
			HEAD = iterator->prev;

		if (iterator->prev)
			iterator->prev->next = iterator->next;
		else
			TAIL = iterator->next;
	}
	else
	{
		HEAD = NULL;
		TAIL = NULL;
	}

	free(iterator);
	iterator = NULL;

	--LENGTH;
	return TRUE;
}

int main()
{
	append(5);
	append(22);
	append(66);
	prepend(122);
	prepend(9);
	insert_at(0, 999);
	insert_at(3, 3);

	Node* iterator = TAIL;
	while (iterator != NULL)
	{
		printf("it: %d\n", iterator->value);
		iterator = iterator->next;
	}

	printf("------\n");

	remove_at(0);
	remove_at(LENGTH-1);
	printf("h: %d\n", HEAD->value);
	printf("t: %d\n", TAIL->value);

	iterator = TAIL;
	while (iterator != NULL)
	{
		printf("it: %d\n", iterator->value);
		iterator = iterator->next;
	}

	printf("------\n");

	remove_at(1);
	iterator = TAIL;
	while (iterator != NULL)
	{
		printf("it: %d\n", iterator->value);
		iterator = iterator->next;
	}
}