typedef
  struct _elem {

    int info;
    struct _elem *next;

  } elem, *pt;


pt getprelastel(pt list) {

  pt nextel;
  if(list) {

    nextel = list;
    do {
      list = nextel;
      if(list -> next) nextel = list -> next;
    }
    while (nextel -> next);
    return list;

  }
  else
    return 0;

}

pt getlastel(pt list) {

  if(list) {

    for(; list -> next; list = list -> next);
    return list;

  }
  else
    return 0;

}

pt searchel(pt list, int info) {

  if(list) {

    while( (list -> next) && (list -> info != info)) list = list -> next;
    return ((list -> info != info) ? 0 : list);

  }
  else return 0;

}

pt searchpreel(pt list, int info) {

  pt nextel;
  if(list) {

    nextel = list;
    do {

      list = nextel;
      if(list -> next) nextel = list -> next;

    }
    while(!((!nextel -> next) || (nextel -> info == info)));
    return ((nextel -> info != info) || (nextel == list)) ? 0 : list;

  }
  else return 0;

}

int getelem(char *elname) {

  int ret;
  printf("Iveskite %s : ", elname);
  scanf("%d", &ret);
  return ret;

}

void addtobegin(pt *list, int info) {

  pt newelem;
  newelem = (pt)malloc(sizeof(elem));
  newelem -> info = info;
  newelem -> next = *list;
  *list = newelem;

}


void addafter(pt listel, int info) {

  pt newelem, temp;
  temp = searchel(listel, getelem("Ieskomo elemento reiksme"));

  if(listel && temp) {
    newelem = (pt)malloc(sizeof(elem));
    newelem -> info = info;
    newelem -> next = temp -> next;
    temp -> next = newelem;
  }

}


void addtoend(pt *list, int info) {

  if(!(*list)) addtobegin(list, info);
  else
    addafter(getlastel(*list), info);

}


void addbefore(pt listel, int info) {

  pt newelem, temp;
  temp = searchel(listel, getelem("Ieskomo elemento reiksme"));
  if(listel && temp) {

    newelem = (pt)malloc(sizeof(elem));
    newelem -> info = temp -> info;
    temp -> info = info;
    newelem -> next = temp -> next;
    temp -> next = newelem;

  }

}

void delfirstel(pt *list) {

  pt temp;

  if(*list) {
    temp = *list;
    *list = (*list) -> next;
    free(temp);
  }
}


void dellastel(pt *list) {

  pt temp;
  if(list) {

    if(!((*list) -> next)) delfirstel(list);
    else {
      temp = getprelastel(*list);
      free(temp -> next);
      temp -> next = 0;
    }

  }

}


void delel(pt *list, pt el) {

  pt temp, temp1;
  temp1 = searchel(*list, getelem("Pasalinamo elemento reikshme"));

  if(list && el && temp1) {

    if(!temp1 -> next)
      if(!(*list) -> next) delfirstel(list);
      else dellastel(list);

    else {
      temp = temp1 -> next;
      temp1 -> info = temp -> info;
      temp1 -> next = temp -> next;
      free(temp);
    }
  }
}


void delbefore(pt *list, int info) {

  pt temp;
  if(*list) {
    temp = searchpreel(*list, info);
    delel(list, temp);
  }

}

void delafter(pt *list, int info) {

  pt temp;

  if(*list) {
    temp = searchel(*list, info);
    temp = temp -> next;
    delel(list, temp);
  }

}


void printlist(pt list) {

  clrscr();
  if(!list) puts("Sarasas Tuscias!");
  else
    while(list) {

      printf("%d", list -> info);
      list = list -> next;

      printf("%c", (list) ? "," : ".");

    }
    getch();
}


void checkel(pt list, int info) {

  if(searchel(list, info))
    printf("Elementas %d egzistuoja.", info);
  else
    printf("Elemento %d nera.", info);
  getch();

}

void listclear(pt *list) {

  pt templist;
  while(list) {
    templist = *list;
    *list = (*list) -> next;
    free(templist);
  }

}


void showmenu() {
  clrscr();
  puts("1) Irasyti elementa i saraso pradzia\n");
  puts("2) Irasyti elementa i saraso pabaiga\n");
  puts("3) Pasalinti pirma elementa is saraso\n");
  puts("4) Pasalinti paskutini elementa is saraso\n");
  puts("5) Patinkrinti ar egzistuoja nurodytas elementas\n");
  puts("6) Pasalinti nurodyta elementa\n");
  puts("7) Iterpti elementa po nurodyto\n");
  puts("8) Iterpti elementa pries nurodyta\n");
  puts("9) Pasalinti elementa po nurodyto\n");
  puts("10) Pasalinti elementa pries nurodyta\n");
  puts("11) Isspausdinti sarasa\n");
  puts("12) Istrinti sarasa\n");
  puts("13) Iseiti is programos\n\n");

  puts(" Jusu pasirinkimas : ");
}

int main() {

  pt root;
  int selection;

  root = 0;
  do {

    showmenu();
    scanf("%d", &selection);
    puts("\n");

    switch(selection) {

      case  1: addtobegin(&root,getelem("elemento reiksme"));
               break;
      case  2: addtoend(&root,getelem("elemento reiksme"));
               break;
      case  3: delfirstel(&root);
               break;
      case  4: dellastel(&root);
               break;
      case  5: checkel(root,getelem("Ieskomo elemento reiksme"));
               break;
      case  6: delel(&root,root);
               break;
      case  7: addafter(root,getelem("Iterpiamo elemento reiksme"));
               break;
      case  8: addbefore(root,getelem("Iterpiamo elemento reiksme"));
               break;
      case  9: delafter(&root,getelem("Ieskomo elemento reiksme"));
               break;
      case 10: delbefore(&root,getelem("Ieskomo elemento reiksme"));
               break;
      case 11: printlist(root);
               break;
      case 12: listclear(&root);
               break;
      case 13: clrscr();

    }

  } while(selection != 13);
  return 0;

}