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

struct item {
	struct item* next;
	struct item* prev;
	int data;
};	

typedef struct list {
	struct item* head;
	struct item* tail;
} list_t;

void list_init(list_t* lst);
int  list_add(list_t* lst, int data);
void list_clear(list_t* lst);
void list_swap(list_t* lst, struct item* p1, struct item* p2);

//сортировка выбором
void list_sort(list_t* lst){
	struct item* p, *k, *i;
	for(p = lst->head; p != NULL; p = p->next){
		k = p;
		for(i = p->next; i != NULL; i = i->next){
			if(i->data < k->data)
				k = i;
		}
		if(k != p){
			list_swap(lst, k, p);
			p = k;
		}
	}
}

int main(void){
	int    i;
	const struct item* p;
	list_t lst;
	list_init(&lst);
	
	for(i = 0; i < 20; ++i)
		list_add(&lst, rand() % 10);

	for(p = lst.head; p != NULL; p = p->next)
		printf("%d ", p->data);
	putchar('\n');
	for(p = lst.tail; p != NULL; p = p->prev)
		printf("%d ", p->data);
	puts("\n\n");
	
	list_sort(&lst);

	//вывод после сортировки
	for(p = lst.head; p != NULL; p = p->next)
		printf("%d ", p->data);
	putchar('\n');
	for(p = lst.tail; p != NULL; p = p->prev)
		printf("%d ", p->data);
	putchar('\n');
	list_clear(&lst);
	return 0;
}

//инициализация
void list_init(list_t* lst){
	lst->head = lst->tail = NULL;
}

//добавление в конец списка
int list_add(list_t* lst, int data){
	struct item* p = (struct item*)malloc(sizeof(struct item));
	if(p != NULL){
		p->data = data;
		p->next = p->prev = NULL;
		if(lst->head == NULL)
			lst->head = lst->tail = p;
		else {
			p->prev   = lst->tail;
			lst->tail->next = p;
			lst->tail = p;
		}
	}
	return (p != NULL);
}

//удаление всех
void list_clear(list_t* lst){
	struct item* t;
	while(lst->head != NULL){
		t = lst->head;
		lst->head = lst->head->next;
		free(t);
	}
	lst->tail = NULL;
}

// обмен
void list_swap(list_t* lst, struct item* p1, struct item* p2){
	struct item* r1, *r2, *t1, *t2;
	r1 = p1->prev; 
	r2 = p2->prev;

	if(r1 != NULL) r1->next = p2;
	p2->prev = r1;

	if(r2 != NULL) r2->next = p1;
	p1->prev = r2;

	t1 = p1->next;
	t2 = p2->next;
                
	p1->next = p2->next;
	if(t2 != NULL) t2->prev = p1;

	p2->next = t1;
	if(t1 != NULL) t1->prev = p2;

	if(lst->head == p1)
		lst->head = p2;
	else if(lst->head == p2)
		lst->head = p1;

	if(lst->tail == p1)
		lst->tail = p2;
	else if(lst->tail == p2)
		lst->tail = p1;
}

3 6 7 5 3 5 6 2 9 1 2 7 0 9 3 6 0 6 2 6 
6 2 6 0 6 3 9 0 7 2 1 9 2 6 5 3 5 7 6 3 


0 0 1 2 2 2 3 3 3 5 5 6 6 6 6 6 7 7 9 9 
9 9 7 7 6 6 6 6 6 5 5 3 3 3 2 2 2 1 0 0