int_dll.c

// int_dll.c

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

// doubly linked list node struct
struct node {
	int id;
	struct node * prev;
	struct node * next;
}; // typedef struct node

// doubly linked list struct
struct int_dll {
	int size;
	struct node * head;
	struct node * tail;
}; // typedef struct int_dll

// initializes a passed in doubly linked list
void int_dll_init(struct int_dll * list) {
	list->head = (struct node *) malloc(sizeof(struct node));
	list->tail = (struct node *) malloc(sizeof(struct node));
	list->size = 0;
	list->head->id = 0;
	list->tail->id = 0;
	
	list->head->next = list->tail;
	list->head->prev = NULL;
	
	list->tail->prev = list->head;
	list->tail->next = NULL;
}

// returns the size of a passed in int doubly linked list
int int_dll_size(struct int_dll * list) {
	return list->size;
}

// removes a passed in node from the list it's in
int int_dll_remove_node(struct node * node) {
	int ret = node->id;
	node->next->prev = node->prev;
	node->prev->next = node->next;
	
	node->next = NULL;
	node->prev = NULL;
	
	free(node);
	
	return ret;
}

// removes an int at a specified index in a passed in doubly linked list
int int_dll_remove_at(struct int_dll * list, const int idx) {
	int len = int_dll_size(list);
	if(idx < 0 || idx >= len) {
		return -1;
	}
	
	struct node * iter;
	int mid = (len % 2 == 0) ? len / 2 + 1 : len / 2;
	if(idx <= mid) {
		int i = 0;
		iter = list->head;
		while(i <= idx) {
			iter = iter->next;
			i += 1;
		}
	} else {
		int i = len;
		iter = list->tail;
		while(i > idx) {
			iter = iter->prev;
			i -= 1;
		}
	}
	
	list->size -= 1;
	
	return int_dll_remove_node(iter);
}

// removes and returns the first int in an int doubly linked list
int int_dll_pop(struct int_dll * list) {
	if(int_dll_size(list) <= 0) {
		return -1;
	}
	
	return int_dll_remove_node(list->head->next);
}

// adds a passed in node after a specified node
void int_dll_add_after_node(struct node * after, struct node * node) {
	node->next = after->next;
	node->prev = after;
	after->next->prev = node;
	after->next = node;
}

// adds an int to the end of a passed in doubly linked list
void int_dll_add(struct int_dll * list, const int val) {
	struct node * tmp = (struct node *) malloc(sizeof(struct node));
	tmp->id = val;
	
	int_dll_add_after_node(list->tail->prev, tmp);
	
	list->size += 1;
}

// inserts an int at the beginning of a passed in doubly linked list
void int_dll_insert(struct int_dll * list, const int val) {
	struct node * tmp = (struct node *) malloc(sizeof(struct node));
	tmp->id = val;
	
	int_dll_add_after_node(list->head, tmp);
	
	list->size += 1;
}

// inserts an int into the first position of a passed in int doubly linked list
void int_dll_push(struct int_dll * list, int val) {
	int_dll_insert(list, val);
}

// inserts an int at a specified index in a passed in doubly linked list
int int_dll_insert_at(struct int_dll * list, const int idx, const int val) {
	int len = int_dll_size(list);
	if(idx < 0 || idx >= len) {
		return -1;
	}
	
	struct node * tmp = (struct node *) malloc(sizeof(struct node));
	tmp->id = val;
	
	struct node * iter;
	int mid = (len % 2 == 0) ? len / 2 + 1 : len / 2;
	if(idx <= mid) {
		int i = 0;
		iter = list->head;
		while(i < idx) {
			iter = iter->next;
			i += 1;
		}
	} else {
		int i = len;
		iter = list->tail;
		while(i > idx) {
			iter = iter->prev;
			i -= 1;
		}
	}
	
	int_dll_add_after_node(iter, tmp);
	
	list->size += 1;
	
	return 1;
}

// prints a passed in int doubly linked list list forward
void int_dll_print(struct int_dll * list) {
	struct node * tmp = list->head->next;
	
	while(tmp != list->tail) {
	  printf("%d ", tmp->id);
	  tmp = tmp->next;
	}
}

// prints a passed in int doubly linked list backward
void int_dll_print_rev(struct int_dll * list) {
	struct node * tmp = list->tail->prev;
	
	while(tmp != list->head) {
		printf("%d ", tmp->id);
		tmp = tmp->prev;
	}
}

// frees a passed in int doubly linked list
void int_dll_free(struct int_dll * list) {
	int_dll_recursive_free(list->head);
}

// int_dll_free helper function
void int_dll_recursive_free(struct node * node) {
	if(node == NULL)
		return;
	
	int_dll_recursive_free(node->next);
	free(node);
}

// entry point of the program
int main() {
	struct int_dll * list;
	list = (struct int_dll * ) malloc(sizeof(struct int_dll));
	
	int_dll_init(list); // initialize list
	
	printf("Inserting\n");
	for(int i = 1; i < 11; ++i) {
		int_dll_insert(list, i);
	}
	
	printf("List Size: %d\n", int_dll_size(list));

	printf("Adding\n");
	for(int i = 1; i < 11; ++i) {
		int_dll_add(list, i);
	}
	
	printf("List Size: %d\n", int_dll_size(list));
	
	int_dll_insert_at(list, 10, -1);
	
	printf("List Size: %d\n", int_dll_size(list));
	
	printf("Popping\n");
	for(int i = 0; i < 5; ++i) {
		int popped = int_dll_pop(list);
		printf("%d ", popped);
	} 
	
	printf("\nList Size: %d\n", int_dll_size(list));
	
	printf("Pushing\n");
	for(int i = 10; i < 16; ++i) {
		int_dll_push(list, i);
	} 
	
	printf("List Size: %d\n", int_dll_size(list));
	
	int_dll_print(list); // print the list
	
	int_dll_remove_at(list, 0);
	printf("\n");
	int_dll_print(list); // print the list
	
	int_dll_remove_at(list, 10);
	printf("\n");
	int_dll_print(list); // print the list
	
	int_dll_insert_at(list, 0, 100);
	printf("\n");
	int_dll_print(list); // print the list
	
	int_dll_free(list); // free the list
	
	return 0;
}