program ListaApontadores;

type
  TipoChave     = integer;
  TipoApontador = ^TipoCelula;
  TipoItem      = record 
                    Chave: TipoChave;
                    { outros componentes }
                  end;
  TipoCelula    = record
                    Item: TipoItem;
                    Prox: TipoApontador;
                  end;
  TipoLista     = record
                    Primeiro: TipoApontador;
                    Ultimo  : TipoApontador;
                  end;

procedure FLVazia (var Lista: TipoLista);
begin
  new (Lista.Primeiro);
  Lista.Ultimo := Lista.Primeiro; Lista.Primeiro^.Prox := nil;
end; { FLVazia }

function Vazia (Lista: TipoLista): boolean;
begin Vazia := Lista.Primeiro = Lista.Ultimo; end; { Vazia }

procedure Insere (x: TipoItem; var Lista: TipoLista);
begin
  new (Lista.Ultimo^.Prox); Lista.Ultimo := Lista.Ultimo^.Prox;
  Lista.Ultimo^.Item := x;  Lista.Ultimo^.Prox := nil
end; { Insere }

procedure Retira(p:TipoApontador;var Lista:TipoLista;var Item: TipoItem);
{---Obs.: o item a ser retirado e o seguinte ao apontado por  p --- }
var q: TipoApontador;
begin
  if Vazia (Lista) or (p = nil) or (p^.Prox = nil)
  then writeln ('Erro: Lista vazia ou posicao nao existe')
  else begin
       q := p^.Prox; Item := q^.Item; p^.Prox := q^.Prox;
       if p^.Prox = nil then Lista.Ultimo := p;
       dispose (q);
       end;
end; { Retira }
 
procedure Imprime (Lista: TipoLista);
var Aux: TipoApontador;
begin
  Aux := Lista.Primeiro^.Prox;
  while Aux <> nil do
    begin writeln (Aux^.Item.Chave); Aux := Aux^.Prox; end;
end; { Imprime }

const max = 10;

var
  lista: TipoLista;
  item : TipoItem;
  vetor: array [1..max] of integer;
  p    : TipoApontador;
  i, j, k, n, tamanho: integer;

begin
  FLVazia (lista);
  tamanho := 0;
  
  { Gera uma permutação aleatoria de chaves entre 1 e max }
  randomize;
  for i := 1 to max do vetor[i] := i;
  for i := 1 to max do
    begin
    k := 1 + random (max);
    j := 1 + random (max);
    n := vetor[k];
    vetor[k] := vetor[j];
    vetor[j] := n;
    end;
  
  { Insere cada chave na lista }
  for i := 1 to max do
    begin
    item.Chave := vetor[i];
    Insere (item, lista);
    tamanho := tamanho + 1;
    writeln ('Inseriu: ', item.Chave);
    end;
  
  Imprime (lista);
  
  { Retira cada chave da lista }
  for i := 1 to max do
    begin
    { escolhe uma chave aleatoriamente }
    k := random (tamanho);
    p := lista.Primeiro;
    { aponta para a chave escolhida }
    for j := 1 to k do p := p^.Prox;
    { retira a chave apontada }
    Retira (p, lista, item);
    tamanho := tamanho - 1;
    writeln ('Retirou: ', item.Chave);
    end;
  
  Imprime (lista);
end. { ListaApontadores }