linked list and bubble sort
===
###### tags: `暑期集訓`
## result
## code

#include <stdio.h>
#include <stdlib.h>
typedef struct node{
	int data;
	struct node *next;
	struct node *prev;
}Node;
typedef struct list{
	Node *head;
}List;
Node *createnode(Node *previous,int data){
	Node *newNode = malloc(sizeof(Node));
	if(!newNode){
		return NULL;
	}
	newNode -> data = data;
	newNode -> next = NULL;
	newNode -> prev = previous;
	return newNode;
}

List *makelist(){
	List *list = malloc(sizeof(List));
	list -> head = NULL;
	return list;
}

void display(List *list){
	Node *current = list -> head;
	if(list->head==NULL)
		return;
	for(;current != NULL; current =current->next){
		printf("%d ",current->data);
	}
	printf("\n");
	return;
}

void add(int data,List *list){
	Node *current = NULL;
	Node *previous = NULL;
	if(list->head == NULL){
		list -> head = createnode(previous,data);
	}
	else{
		current = list->head;
		while(current -> next != NULL){
			previous = current;
			current = current -> next;
		}
		current -> prev = previous;
		current -> next = createnode(current,data);
	}
}

void delete(Node *del_node,List *list){
	Node *previous = NULL;
	Node *nextone = NULL; 
	if (del_node -> prev ==NULL && del_node-> next ==NULL){		//only one node in this list and it is head
		list->head = NULL;
		free(del_node);				
	}
	else if (del_node -> prev == NULL){
		nextone = del_node -> next;
		nextone -> prev = NULL;
		list -> head = nextone;
		free(del_node);
	}
	else if (del_node -> next ==NULL){				//it is the last one
		previous = del_node -> prev;
		previous -> next = NULL;
		free(del_node); 
	}
	else{
		previous = del_node -> prev;
		nextone = del_node ->next;
		previous -> next = del_node -> next;
		nextone -> prev = del_node -> prev;
		free(del_node);
	}
}
void inverse_display(List *list){
	Node *current = list->head;
	for(;current->next != NULL; current = current->next ){};
		//current = current -> prev;
	for(;current -> prev != NULL; current = current->prev){
		printf("%d ",current->data);
	}
	printf("%d",current->data);
	printf("\n");
}

void swap( Node *node1 ,Node *node2 ,List *list){
	Node *p1 = node1->prev;
	Node *n1 = node1->next;
	Node *p2 = node2->prev;
	Node *n2 = node2->next;
	Node temp;		
	if( p1 == NULL){	//if node1 or node 2 is fisrt node of the list ,change head
		list->head = node2;
		p2->next = node1;
	}
	else if( p2  ==NULL){
		list->head = node1;
		p1->next = node2;
	}
	else{
		p1->next = node2;
		p2->next = node1;
	}
	//display(list);
	if( n1 == NULL){
		n2->prev = node1;
	}
	else if( n2 ==NULL){
		n1->prev = node2;
	}
	else{
		n1->prev = node2; 
		n2->prev = node1;
	}
	//display(list);
	temp.prev = node1->prev;
	temp.next = node1->next;
	node1->prev = node2->prev;
	node1->next = node2->next;
	node2->prev = temp.prev;
	node2->next = temp.next;
	//display(list);
}
/*
void swap(Node *node1,Node *node2,List *list){
	int temp = node1->data;
	node1->data = node2->data;
	node2->data = temp;
}*/
int length_of_list(List *list){
	int count = 0;
	Node *current = NULL;
	current = list->head;
	for(;current != NULL;current=current->next){
		count ++;
	}
	return count;
}
void sort( List *list ){
	int count = length_of_list(list);
	Node *current = list->head;
	Node *nextone = NULL;
	//printf("count is %d\n",count);
	for (;count >1;count--){
		current = list->head;
		for(;current->next != NULL; current = current->next ){
			nextone = current->next;
			//printf("current data is %d\n",current->data);
			//printf("next one data is %d\n",nextone->data);
			if(current->data > nextone->data){
				swap(current,nextone,list);
				current =current->prev;
			//	display(list);
			}
		}
		
	}
}

void destroy(List * list){
  Node * current = list->head;
  Node * next = current;
  while(current != NULL){
    next = current->next;
    free(current);
    current = next;
  }
  free(list);
}

int main(void){
	List * list = makelist();
	int num = 0;
	do{
		scanf("%d",&num);
		add(num,list);
	}while(getchar()!='\n');
	printf("display\n");
	display(list);
	//printf("inverse display\n");
	//inverse_display(list);
	printf("start sort\n");
	sort(list);
	printf("start display\n");
	display(list);
}