write a linked list implementation of quick Sort. Write your sorting program as client (quick.c) of the linked list ADT. linked list ADT is provided below

#include  

#include  

#include "list.h" 

typedef struct node { 

 ElemType val; 

 struct node *next; 

} NODE; 

struct list_struct { 

 NODE *front; 

 NODE *back; 

}; 

/* 

* returns pointer to newly created empty list 

*/ 

LIST *lst_create() { 

LIST *l = malloc(sizeof(LIST)); 

 l->front = NULL; 

 l->back = NULL; 

 return l; 

} 

void lst_free(LIST *l) { 

NODE *p = l->front; 

NODE *pnext; 

 while(p != NULL) { 

 pnext = p->next; // keeps us from de-referencing a freed ptr 

 free(p); 

 p = pnext; 

 } 

 // now free the LIST 

 free(l); 

} 

void lst_print(LIST *l) { 

NODE *p = l->front; 

 printf("["); 

 while(p != NULL) { 

 printf(FORMAT, p->val); 

 p = p->next; 

 } 

 printf("] "); 

} 

void lst_push_front(LIST *l, ElemType val) { 

NODE *p = malloc(sizeof(NODE)); 

 p->val = val; 

 p->next = l->front; 

 l->front = p; 

 if(l->back == NULL) // was empty, now one elem 

 l->back = p; 

} 

void lst_push_back(LIST *l, ElemType val) { 

NODE *p; 

 if(l->back == NULL) // list empty - same as push_front 

 lst_push_front(l, val); 

 else { // at least one element before push 

 p = malloc(sizeof(NODE)); 

 p->val = val; 

 p->next = NULL; 

 l->back->next = p; 

 l->back = p; 

 } 

} 

int lst_length(LIST *l) { 

NODE *p = l->front; 

int n=0; 

 while(p != NULL) { 

 n++; 

 p = p->next; 

 } 

 return n; 

} 

int lst_is_empty(LIST *l) { 

 return l->front == NULL; 

} 

/* These are "sanity checker" functions that check to see 

* list invariants hold or not. 

*/ 

int lst_sanity1(LIST *l) { 

 if(l->front == NULL && l->back != NULL){ 

 fprintf(stderr, "lst_sanity1 error: front NULL but back non-NULL "); 

 return 0; 

 } 

 if(l->back == NULL && l->front != NULL){ 

 fprintf(stderr, "lst_sanity1 error: back NULL but front non-NULL "); 

 return 0; 

 } 

 return 1; 

} 

int lst_sanity2(LIST *l) { 

 if(l->back != NULL && l->back->next != NULL) { 

 fprintf(stderr, "lst_sanity2 error: back elem has a non-NULL next? "); 

 return 0; 

 } 

 return 1; 

} 

ElemType lst_pop_front(LIST *l) { 

ElemType ret; 

NODE *p; 

 if(lst_is_empty(l)) 

 return DEFAULT; // no-op 

 ret = l->front->val; 

 if(l->front == l->back) { // one element 

 free(l->front); 

 l->front = NULL; 

 l->back = NULL; 

 } 

 else { 

 p = l->front; // don't lose node being deleted 

 l->front = l->front->next; // hop over 

 free(p); 

 } 

 return ret; 

} 

/* 

* removes first occurrence of x (if any). Returns 

* 0 or 1 depending on whether x was found 

*/ 

int lst_remove_first(LIST *l, ElemType x) { 

NODE *p; 

NODE *tmp; 

 if(l->front == NULL) return 0; 

 if(l->front->val == x) { 

 lst_pop_front(l); 

 return 1; 

 } 

 // lst non-empty; no match on 1st elem 

 p = l->front; 

 while(p->next != NULL) { 

 if(x == p->next->val) { 

 tmp = p->next; 

 p->next = tmp->next; 

 if(tmp == l->back) 

 l->back = p; 

 free(tmp); 

 return 1; 

 } 

 p = p->next; 

 } 

 return 0; 

} 

int lst_remove_all_slow(LIST *l, ElemType x) { 

int n=0; 

 while(lst_remove_first(l, x)) 

 n++; 

 return n; 

}