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

typedef struct item_t{
	double num;
	struct item_t *next;
	struct item_t *prev;
} Item;

Item *add_double_sorted(Item *head, int n) {
	
	Item *curr;
	Item *new_item=(Item *)malloc(sizeof(Item));
	if (new_item==NULL) {
		printf("allocation failed\n");
		exit(1);
	}

	new_item->num=n;
	new_item->next=NULL;
	new_item->prev=NULL;

	/* if the list is empty then new_item is its head, and only item */
	if (head==NULL)
		return new_item;

	/* if the first value in our sorted list larger than n then we need to add at the beginning */
	if (head->num>=n) {
		head->prev=new_item;
		new_item->next=head;
		return new_item;
	}

	/* traverse the list */
	curr=head;
	while (curr->num<n && curr->next!=NULL) 
		curr=curr->next;

	/* add in the middle if we exited the loop because the current item is the place to add */
	if (curr->num>=n) {
	
		curr->prev->next=new_item;
		new_item->prev=curr->prev;
		curr->prev=new_item;
		new_item->next=curr;
		return head;
	}

	/* if curr is the last element in the list, and is not larger than n,
		it means that we need to add new_item to the end */
	if (curr->next ==NULL) {
		curr->next=new_item;
		new_item->prev=curr;
		return head;
	}

	return head;
}

void print_double_sorted(Item *head) {

	while (head !=NULL) {

		printf("%g\t",head->num);
		head=head->next;
	}
	printf("\n");
}

int main() {

	Item *head=NULL;
	head=add_double_sorted(head,3);
	print_double_sorted(head);
	head=add_double_sorted(head,18);
	print_double_sorted(head);
	head=add_double_sorted(head,25);
	print_double_sorted(head);
	head=add_double_sorted(head,20);
	print_double_sorted(head);
	head=add_double_sorted(head,5);
	print_double_sorted(head);
	head=add_double_sorted(head,5);
	print_double_sorted(head);
	head=add_double_sorted(head,1);
	print_double_sorted(head);

	return 0;
}