#include <cstdio>
#include <cstdlib>
typedef struct _node
{
int data;
struct _node* left;
struct _node* right;
} Node;
typedef struct _list
{
Node* head;
Node* tail;
int size;
} List;
List* create_list()
{
List* new_list = (List*)malloc(sizeof(List));
new_list->head = NULL;
new_list->tail = NULL;
new_list->size = 0;
return new_list;
}
Node* create_node(int data)
{
Node* new_node = (Node*)malloc(sizeof(Node));
new_node->data = data;
new_node->left = NULL;
new_node->right = NULL;
return new_node;
}
bool list_empty(List* L)
{
if(L->size) return 0;
else return 1;
}
void push_back(List *L, int data)
{
Node* new_node = create_node(data);
if(list_empty(L))
{
L->head = new_node;
L->tail = new_node;
}
else
{
L->tail->right = new_node;
new_node->left = L->tail;
L->tail = new_node;
}
L->size++;
}
void push_front(List *L, int data)
{
Node* new_node = create_node(data);
if(list_empty(L))
{
L->head = new_node;
L->tail = new_node;
}
else
{
L->head->left = new_node;
new_node->right = L->head;
L->head = new_node;
}
L->size++;
}
void list_print(List* L)
{
Node* tmp = L->head;
while(tmp)
{
printf("%d ", tmp->data);
tmp = tmp->right;
}
puts("");
}
void pop_back(List* L)
{
if(!list_empty(L))
{
if(L->size == 1)
{
free(L->head);
L->head = NULL;
L->tail = NULL;
}
else
{
Node* prev = L->tail->left;
free(L->tail);
prev->right = NULL;
L->tail = prev;
}
L->size--;
}
}
void pop_front(List* L)
{
if(!list_empty(L))
{
if(L->size == 1)
{
free(L->head);
L->head = NULL;
L->tail = NULL;
}
else
{
Node* next = L->head->right;
free(L->head);
next->left = NULL;
L->head = next;
}
L->size--;
}
}
void node_delete(List* L, int idx)
{
if(!list_empty(L))
{
if(idx >= L->size - 1) pop_back(L);
else if(idx <= 0) pop_front(L);
else
{
Node* now = L->head;
for(int i = 0; i < idx; i++) now = now->right;
now->left->right = now->right;
now->right->left = now->left;
free(now);
L->size--;
}
}
}
void node_insert(List* L, int idx, int data)
{
if(idx == 0) push_front(L, data);
else if(idx >= L->size - 1) push_back(L, data);
else
{
Node* new_node = create_node(data);
Node* now = L->head;
for(int i = 0; i < idx; i++) now = now->right;
new_node->left = now->left;
new_node->right = now;
now->left = new_node;
new_node->left->right = new_node;
L->size++;
}
}
int main()
{
List* new_list = create_list();
for(int i = 1; i < 10; i++)
{
push_back(new_list, i);
list_print(new_list);
}
for(int i = -10; i < 0; i++)
{
push_front(new_list, i);
list_print(new_list);
}
for(int i = 0; i < 20; i++)
{
pop_front(new_list);
list_print(new_list);
}
for(int i = 1; i < 10; i++)
{
push_back(new_list, i);
list_print(new_list);
}
for(int i = 0; i < 10; i++)
{
node_delete(new_list, i);
list_print(new_list);
}
for(int i = 1; i < 10; i++)
{
push_back(new_list, i);
list_print(new_list);
}
puts("");
for(int i = 2; i < 5; i++){
node_insert(new_list, i, -1 - i);
list_print(new_list);
}
return 0;
}