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

typedef struct Node
{
    int data;
    struct Node *next;
    struct Node *prev;
} Node;

Node* SortedInsert(Node *head,int data)
{
    Node *p = malloc(sizeof(*p)), **pp = &head;
    p->data = data;
    p->prev = NULL;
    
    while (*pp && (*pp)->data < data)
    {
        p->prev = *pp;
        pp = &(*pp)->next;
    }
    
    // whatever *pp is, its our next pointer
    p->next = *pp;
    if (*pp)
        (*pp)->prev = p;
    
    // this is always set to the new node
    *pp = p;
    return head;
}

void print_list(const Node *head)
{
    while (head)
    {
        printf("%d(", head->data);
        
        if (head->prev)
            printf("%d,", head->prev->data);
        else
            printf("null,");
        
        if (head->next)
            printf("%d) ", head->next->data);
        else
            printf("null) ");
        
        head = head->next;
    }
    printf("\n");
}

void free_list(Node* head)
{
    while (head)
    {
        Node *tmp = head;
        head = head->next;
        free(tmp);
    }
}

int main()
{
    int ar[] = { 3,1,5,4,6,8,7,9,2 }, i;
    Node *head = NULL;
    
    // ordered insertion
    for (i=1; i<=9; ++i)
        head = SortedInsert(head, i);
    
    print_list(head);
    free_list(head);
    head = NULL;
    
    // reverse insertion
    for (i=9; i>=1; --i)
        head = SortedInsert(head, i);
    
    print_list(head);
    free_list(head);
    head = NULL;
    
    // unordered insertion
    for (i=0; i<sizeof(ar)/sizeof(*ar); ++i)
        head = SortedInsert(head, ar[i]);
    
    print_list(head);
    free_list(head);
    head = NULL;
    
    return 0;
}