#include <stdlib.h>

/* typedef declarations */
typedef struct SinglyNode {
	struct SinglyNode *next;
	int data;
} SinglyNode;
typedef struct DoublyNode {
	struct DoublyNode *next, *prev;
	int data;
} DoublyNode;
typedef struct LinkedQueue {
	SinglyNode *front, *rear;
} LinkedQueue;
typedef struct LinkedStack {
	SinglyNode *top;
} LinkedStack;

/* operations */
/* singly linked list */
void sllInsert(SinglyNode **head, int data) {
	SinglyNode *tempNode;
	if (*head == NULL) {
		*head = (SinglyNode *)malloc(sizeof(SinglyNode));
		(*head)->data = data;
		(*head)->next = NULL;
	}
	else {
		tempNode = *head;
		while(tempNode->next != NULL) {
			tempNode = tempNode->next;
		}
		tempNode->next = (SinglyNode *)malloc(sizeof(SinglyNode));
		tempNode->next->data = data;
		tempNode->next->next = NULL;
	}
}
int sllDelete(SinglyNode **head) {
	int data;
	SinglyNode *tempNode;
	if ((*head)->next == NULL) {
		data = (*head)->data;
		free(*head);
		*head = NULL;
	}
	else {
		tempNode = *head;
		while(tempNode->next->next != NULL) {
			tempNode = tempNode->next;
		}
		data = tempNode->next->data;
		free(tempNode->next);
		tempNode->next = NULL;
	}
	return data;
}
int sllIsEmpty(SinglyNode *head) {
	return head == NULL;
}

/* doubly linked list */
void dllInsert(DoublyNode **head, int data) {
	DoublyNode *tempNode;
	if (*head == NULL) {
		*head = (DoublyNode *)malloc(sizeof(DoublyNode));
		(*head)->data = data;
		(*head)->next = NULL;
		(*head)->prev = NULL;
	}
	else {
		tempNode = *head;
		while(tempNode->next != NULL) {
			tempNode = tempNode->next;
		}
		tempNode->next = (DoublyNode *)malloc(sizeof(DoublyNode));
		tempNode->next->data = data;
		tempNode->next->next = NULL;
		tempNode->next->prev = tempNode;
	}
}
int dllDelete(DoublyNode **head) {
	int data;
	DoublyNode *tempNode;
	if ((*head)->next == NULL) {
		data = (*head)->data;
		free(*head);
		*head = NULL;
	}
	else {
		tempNode = *head;
		while(tempNode->next->next != NULL) {
			tempNode = tempNode->next;
		}
		data = tempNode->next->data;
		free(tempNode->next);
		tempNode->next = NULL;
	}
	return data;
}
int dllIsEmpty(DoublyNode *head) {
	return head == NULL;
}

/* circular linked list */
void cllInsert(SinglyNode **head, int data) {
	SinglyNode *tempNode;
	if (*head == NULL) {
		*head = (SinglyNode *)malloc(sizeof(SinglyNode));
		(*head)->data = data;
		(*head)->next = *head;
	}
	else {
		tempNode = *head;
		while(tempNode->next != *head) {
			tempNode = tempNode->next;
		}
		tempNode->next = (SinglyNode *)malloc(sizeof(SinglyNode));
		tempNode->next->data = data;
		tempNode->next->next = *head;
	}
}
int cllDelete(SinglyNode **head) {
	int data;
	SinglyNode *tempNode;
	if ((*head)->next == NULL) {
		data = (*head)->data;
		free(*head);
		*head = NULL;
	}
	else {
		tempNode = *head;
		while(tempNode->next->next != NULL) {
			tempNode = tempNode->next;
		}
		data = tempNode->next->data;
		free(tempNode->next);
		tempNode->next = *head;
	}
	return data;
}
int cllIsEmpty(SinglyNode *head) {
	return head == NULL;
}

/* Linked Queue operations */
void enqueue(LinkedQueue *queue, int data) {
	if (queue->rear == NULL) {
		queue->rear = (SinglyNode *)malloc(sizeof(SinglyNode));
		queue->rear->data = data;
		queue->rear->next = NULL;
		queue->front = queue->rear;
	}
	else {
		queue->rear->next = (SinglyNode *)malloc(sizeof(SinglyNode));
		queue->rear->next->data = data;
		queue->rear->next->next = NULL;
		queue->rear = queue->rear->next;
	}
}
int dequeue(LinkedQueue *queue) {
	int data = queue->front->data;
	SinglyNode *tempNode = queue->front;
	queue->front = queue->front->next;
	free(tempNode);
	return data;
}
int queueIsEmpty(LinkedQueue *queue) {
	return queue->front == NULL;
}

/* Linked Stack operations */
void push(LinkedStack *stack, int data) {
	SinglyNode *tempNode;
	if (stack->top == NULL) {
		stack->top = (SinglyNode *)malloc(sizeof(SinglyNode));
		stack->top->next = NULL;
		stack->top->data = data;
	}
	else {
		tempNode = (SinglyNode *)malloc(sizeof(SinglyNode));
		tempNode->data = data;
		tempNode->next = stack->top;
		stack->top = tempNode;
	}
}
int pop(LinkedStack *stack) {
	int data = stack->top->data;
	SinglyNode *tempNode = stack->top;
	stack->top = stack->top->next;
	free(tempNode);
	return data;
}
int stackIsEmpty(LinkedStack *stack) {
	return stack->top == NULL;
}