program listas;
type mut = ^elem;
     elem = record
             szam:Integer;
             kov:mut;
            end;
var lista:mut;
    x,miutan,szam:Integer;

  {1}
  procedure beirvegere(var elso:mut;mit:Integer);
  var p,uj:mut;
  begin
   new(uj);
   uj^.szam:=mit;
   uj^.kov:=nil;
   if elso=nil then elso:=uj 
    else
     begin 
      p:=elso;
      while p^.kov<>nil do p:=p^.kov;
      p^.kov:=uj;
     end;
  end;
 
  {2}
  procedure beirelejere(var elso:mut;mit:Integer);  
  var uj:mut; 
  begin 
   new(uj);
   uj^.szam:=mit;
   uj^.kov:=elso;
   elso:=uj;
  end;

  {3}
  procedure kiir(elso:mut);
  var p:mut;
  begin 
   if elso=nil then WriteLn('A lista ures') 
    else 
     begin
      Write('A lista:');
      p:=elso;
      while p<>nil do 
       begin
        Write(p^.szam,' ');
        p:=p^.kov;  
       end;
      WriteLn;
     end;   
  end;
  
  {4}
  procedure torolelejerol(var elso:mut);
  var p:mut;
  begin
   if elso<>nil then
    begin
     p:=elso;
     elso:=elso^.kov;
     dispose(p);
    end;
  end;
  
  {5}
  procedure torolvegerol(var elso:mut);
  var p,q:mut;
  begin
   if elso<>nil then
    if elso^.kov<>nil then 
      begin 
       p:=elso;
       while p^.kov^.kov<>nil do p:=p^.kov;
       q:=p^.kov;
       p^.kov:=nil;
       dispose(q);
      end 
       else
         begin
          dispose(elso);
          elso:=nil;
         end
  end;

 {6}
 procedure beszurutan(var elso:mut;mit,miutan:Integer);
 var p,uj:mut;
     lehet:boolean;
 begin
  lehet:=false;
  p:=elso;
  while (p<>nil) do 
   begin
    if p^.szam=miutan then 
     begin 
      new(uj);
      uj^.szam:=mit;
      uj^.kov:=p^.kov;
      p^.kov:=uj;
      lehet:=true;
      p:=p^.kov^.kov;
     end else p:=p^.kov;
   end;
  if not lehet then WriteLn('Nem lehetseges!');
 end;

 {7}
 procedure beszurele(var elso:mut;mit,miele:Integer);
 var p,uj:mut; 
     lehet:boolean;
 begin
  lehet:=false;
  p:=elso;
  while p<>nil do 
   begin
    if p^.szam=miele then 
     begin
      new(uj);
      uj^:=p^;
      p^.szam:=mit;
      p^.kov:=uj;
      lehet:=true;
      p:=p^.kov^.kov;
     end else p:=p^.kov;
   end;
  if not lehet then WriteLn('Nem lehet!');
 end;
  
 {8}
 procedure beszurk(var elso:mut;mit,k:Integer);
 var uj,p:mut;
     lehet:boolean;
     db:Integer;
 begin 
  lehet:=false;
  db:=1;
  p:=elso; 
  while p<>nil do
   begin
    if db=k then
     begin
      new(uj);  
      uj^:=p^;
      p^.szam:=mit;
      p^.kov:=uj; 
      lehet:=true;
     end;
    p:=p^.kov;
    Inc(db);
   end;
  if(p=nil) and (k=db) then
   begin  
    beirvegere(lista,mit);
    lehet:=true;
   end;
  if not lehet then WriteLn('Nem lehet.');
 end;
 
 {9}
 procedure torolelemet(var elso:mut;mit:Integer);
 var p,q:mut;
 begin
  while elso^.szam=mit do
   begin
    p:=elso;
    elso:=elso^.kov;
    dispose(p);
   end;
  p:=elso;
  while p<>nil do
   begin
    if p^.kov<>nil then
     begin
      if p^.kov^.szam=mit then 
       begin
        q:=p^.kov;
        p^.kov:=q^.kov;
        dispose(q);
       end else p:=p^.kov;
     end else p:=p^.kov;
   end;
 end;
 
 procedure toroladott(var elso:mut;mit:Integer);
 var p,q:mut;
 begin
  p:=elso;
  if elso^.szam=mit then 
   begin 
    q:=elso;
    elso:=elso^.kov;
    dispose(q);
   end;
  if p^.kov<>nil then
   begin
    while (p<>nil) and (p^.kov^.szam<>mit) do p:=p^.kov;
    if p=nil then WriteLn('Nem lehet') else
     if p^.kov^.szam=mit then 
      begin
       q:=p^.kov;
       p^.kov:=q^.kov;
       dispose(q);
      end;
   end;
 end; 

 {11}
 procedure shellsort(var elso:mut);
 var p,q:mut;
     aux:Integer;
 begin
  p:=elso;
  while p^.kov<>nil do
   begin
    q:=p^.kov;
    while q<>nil do
     begin
      if p^.szam>q^.szam then
       begin 
        aux:=p^.szam;
        p^.szam:=q^.szam;
        q^.szam:=aux;
       end; 
      q:=q^.kov;
     end;
    p:=p^.kov;
   end;
 end;
 
 {12}
 procedure bubblesort(var elso:mut); 
 var rendezett:Boolean;
     p:mut;
     aux:Integer;
 begin
  repeat
   rendezett:=true;
   p:=elso;
   while p^.kov<>nil do
    begin 
     if p^.szam > p^.kov^.szam then 
      begin
       aux:=p^.szam;
       p^.szam:=p^.kov^.szam;
       p^.kov^.szam:=aux;
       rendezett:=false;
      end;
     p:=p^.kov;
    end;
  until rendezett;
 end;

 procedure felszabadit(var elso:mut);
 var p,q:mut;
 begin
  p:=elso;
  while p<>nil do
   begin
    q:=p;
    p:=p^.kov;
    dispose(q);
   end;
  elso:=nil;
 end;

begin
 lista:=nil;
 repeat
  WriteLn;
  WriteLn('1. Beir a vegere');
  WriteLn('2. Beir az elejere');
  WriteLn('3. Kiir');
  WriteLn('4.Torol az elejerol');
  WriteLn('5.Torol a vegerol');
  WriteLn('6.Beszuras minden adott elem utan');
  WriteLn('7.Beszuras minden adott elem ele');
  WriteLn('8.Elem beszurasa k. helyre');
  WriteLn('9.Adott elem minden elofordulasanak torlese');
  WriteLn('10.Adott elem elso elofordulasanak torlese');
  WriteLn('11.Rendez (shell-sort)');
  WriteLn('12.Rendez (bubble sort)');
  WriteLn('13.Felszabaditas');
  WriteLn('0. Kilepes');
  Write('A valasztas:');
  ReadLn(x);
  WriteLn;
  case x of 
   1: begin
       Write('Elem:'); 
       ReadLn(szam);
       beirvegere(lista,szam);
      end;
   2: begin
       Write('Elem:'); 
       ReadLn(szam);
       beirelejere(lista,szam);
      end;
   3: kiir(lista);
   4: torolelejerol(lista);
   5: torolvegerol(lista);
   6: begin
       Write('Elem:');
       ReadLn(szam);
       Write('Mi utan:'); 
       ReadLn(miutan);
       beszurutan(lista,szam,miutan);
      end;
   7: begin
       Write('Elem:');
       ReadLn(szam);
       Write('Mi ele:');
       ReadLn(miutan);
       beszurele(lista,szam,miutan);
      end;
   8: begin 
       Write('Elem:');
       ReadLn(szam);
       Write('Hova:');
       ReadLn(miutan); 
       beszurk(lista,szam,miutan);
      end;
   9: begin
       Write('Elem:');  
       ReadLn(szam);
       torolelemet(lista,szam);
      end;
   10: begin 
        Write('Elem:');  
        ReadLn(szam);
        toroladott(lista,szam);
       end;
   11:shellsort(lista);
   12:bubblesort(lista);
   13:felszabadit(lista);
  end;
 until x=0;

end.