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

struct node {
 int data;
 unsigned long link;
};
struct node *head, *tail, *currN, *prevN, *nextN, *tmp;

void insert(struct node **headN, struct node **tailN, int n);
void delete(struct node **headN, struct node **tailN, int n);
void list(struct node *head, int i);
void nextNode();
void previNode();

//============================================================

void insert(struct node **headN, struct node **tailN, int numN) {
 struct node *newnode = malloc(sizeof(struct node));
 newnode->link =(unsigned long)(*headN);
 newnode->data = numN;

 //if empty list
 if (*headN == NULL){
   *headN = newnode;
   currN = *headN;
   (*headN)->link = 0;
 } else if ((*headN)->link == (unsigned long)NULL){
   if (numN <= (*headN)->data){
     newnode->link = (unsigned long) *headN;
     (*headN)->link = (unsigned long) newnode;
     tail = *headN;
     *headN = newnode;
     nextN = tail;
     prevN = NULL;
   } else {
     newnode->link = (unsigned long) *headN;
     (*headN)->link = (unsigned long) newnode;
     tail = newnode;
     nextN = NULL;
     currN = tail;
     prevN = *headN;
   }
 } else {
   currN = *headN;
   prevN = NULL;
   nextN = (struct node *)(currN->link ^ (unsigned long) prevN);
   if (numN > tail->data){
     while (currN!=tail){
       nextNode();
     }
     newnode->link = (unsigned long) currN;
     currN->link = (unsigned long) newnode ^ (unsigned long) prevN;
     tail = newnode;
   } else if (numN < head->data){
     currN->link = (unsigned long) newnode ^ (unsigned long) nextN;
     newnode->link = (unsigned long) currN;
     *headN = newnode;
     nextN = currN;
     currN = *headN;
   } else {
     while (numN > currN->data){
       nextNode();
     }
     newnode->link = (unsigned long) prevN ^ (unsigned long) currN;
     prevN->link ^= (unsigned long) currN ^ (unsigned long) newnode;
     currN->link ^= (unsigned long) prevN ^ (unsigned long) newnode;
   }
 }
}

void delete(struct node **headN, struct node **tailN, int numD){

 struct node *prevN = NULL;
 struct node *currN = *headN;

 while ( currN != NULL )
   {
     struct node *nextN = (struct node *) (currN->link ^ (unsigned long)prevN);
     //if the number is found, then delete it
     if (currN->data == numD)
       {
         if(prevN)
           {
             prevN->link ^= (unsigned long)currN ^ (unsigned long)nextN;
           }
         else
           *headN = nextN;
         if(nextN)
           {
             nextN->link ^= (unsigned long)currN ^ (unsigned long)prevN;
           }
         else
           *tailN = prevN;
         free(currN);
         break;
       }
     prevN = currN;
     currN = nextN;
   }
}

void list(struct node *head, int i){

 if(i == 0){
   currN = head;
   prevN = NULL;
   int count = 1;
   nextN = (struct node *) (currN->link ^ (unsigned long) prevN);
   printf("Linked List in ascending order\n");
   while(currN!=NULL){
     if(count <= 10){
       printf("%-5d", currN->data);
       nextNode();
       count++;
     }
     else{
       printf("\n");
       count = 1;
     }
   }
 }
 printf("\n\n");

 if(i == 1){
   printf("Linked List in descending order\n");
   currN = tail;
   int count2 = 1;
   prevN = (struct node *) currN->link;
   nextN = NULL;
   while (currN!=NULL){
     if(count2 <= 10){
       printf("%-5d", currN->data);
       previNode();
       count2++;

     }else{
       printf("\n");
       count2 = 1;
     }
   }
 }
 printf("\n");
}

void nextNode(){
 nextN = (struct node *) (currN->link ^ (unsigned long) prevN);
 prevN = currN;
 currN = nextN;
}

void previNode(){
 prevN = (struct node *) (currN->link ^ (unsigned long) nextN);
 nextN = currN;
 currN = prevN;
}

int main(){

 int i;
 float seed;
 head = NULL; tail = NULL; currN = NULL; prevN = NULL; nextN = NULL;

 for (i=0; i < 100; ++i) {
   insert( &head, &tail, i );
 }

 list(head, 0);

 for (i = 99; i > 0; --i) {
   delete( &head, &tail, i );
 }

 list(head, 1);

 return 0;
}

Linked List in ascending order
0    1    2    3    4    5    6    7    8    9    
10   11   12   13   14   15   16   17   18   19   
20   21   22   23   24   25   26   27   28   29   
30   31   32   33   34   35   36   37   38   39   
40   41   42   43   44   45   46   47   48   49   
50   51   52   53   54   55   56   57   58   59   
60   61   62   63   64   65   66   67   68   69   
70   71   72   73   74   75   76   77   78   79   
80   81   82   83   84   85   86   87   88   89   
90   91   92   93   94   95   96   97   98   99   




Linked List in descending order
0