#include<stido.h>
#include<stdlib.h>
#ifndef _Lish_h
struct Node;
typedef struct Node *PtrToNode;
typedef PtrToNode List;
typedef PtrToNode Position; 
void MakeEmpty(List l);
int IsEmpty(List l);
int IsLast(Position p,List l);
Position Find(ElementType x,List l);
void Delte(ElementType x,List l);
Position FindPrevious(ElementType x,List l);
void Insert(ElementType x,List l,Position p);
void DelList(List l);
Position Header(List l);
Position First(List l);
Position Advance(Position p);
ElementType Retrieve(Position p);
#endif 

struct Node
{
  ElementType Element;
  Position Next;
       };
    
  void MakeEmpty(List l)
  {
    Position p=l->Next;
    while(!IsLast(p,l))
         {
           tmp=p;
           p=p->Next;
           free(tmp);
         }
         l->Next=NULL;
         free(p);
  }
 
  int IsEmpty(List l)
  {
     return l->Next==NULL;
  }
 
  int IsLast(Position p,List l) 
  {
     Position pt=l->Next;
     while(pt!=p&&pt->Next!=NULL)
          pt=pt->Next;
     if(pt==p&&pt->Next==NULL)
       return 1;
     return 0;
  }
 
  Position Find(Element x,List l)
  {
     Position p=l->Next;
     while(p!=NULL&&p->Element!=x)  
          p=p->Next;
     return p;    
  }
 
  void Delete(Element x,List l)
  {
     Position p=FindPrevious(x,l);
     if(p!=NULL)
     {
        Position tmp=p->Next;
        p->Next=tmp->Next;
        free(tmp);
     }  
  }
 
  Position FindPrevious(Element x,List l)
  {
    Position p=l->Next;
    while(p!=NULL&&p->Next->Element!=x)
        p=p->Next;
    return p;
  }
 
  void Insert(Element x,List l,Position p)
  {
    Position tmp=(Position)malloc(sizeof(List));
    if(tmp==NULL)
       {printf("Out of space !"); exit(1);}
    tmp->Element=x;
    tmp->Next=p->Next;
    p->Next=tmp;
  }
 
  void DeleteList(List l)
  {
    MakeEmpty(l);
    free(l);
  }