1) Problema com nil ?

Se estivermos buscando um elemento x em uma lista encadeada, podemos ter algo similar a:

  while (p <> nil) and (p^.info <> x) do
    p := p^.lig;

Que problema temos no comando acima ?

No caso de p = nil o comando pode ser inválido pois p^.info não existe!

OBS.: Se o compilador não realiza o segundo teste no caso do primeiro falhar, não haveria problema. Em nível de algoritmo, é melhor resolver o problema evitando a possibilidade desse tipo de erro ocorrer, ao invés de usar soluções que dependem do compilador.

O que fizemos nos nossos algoritmos foi algo similar a:

  acabou := false;
  While (p <> nil) and (not acabou) do
    If p^. info = x Then
     acabou := true
    Else p := p^.lig;

2) Uso de sentinela na busca em lista encadeada

Um elemento sentinela pode ser utilizado na busca em lista linear encadeada: usamos para isso um registro no final da lista.

Supondo que inicializamos uma lista apontada por L com a lista vazia, faremos:

  Procedure Create(L: Lista);
  Var sentinela: Lista;
  Begin
    new(sentinela);
    L := sentinela;
  End;

O algoritmo seguinte implementa uma busca por um elemento x na lista apontada por L não ordenada. Retorna p = nil se o elemento não for encontrado; caso contrário p aponta o registro que contém o elemento.

  Procedure busca(x: T; var L, p: Lista);
    var p: Lista;

  Begin
    p := L;
    sentinela^.info := x;
    While p^.info <> x do
      p := p^.lig;
    If (p = sentinela) Then
      p := nil; {elemento não encontrado}
  End;

3) Busca com sentinela e inserção na cabeça da lista não ordenada

Caso o elemento não seja encontrado e quisermos inseri-lo no final da lista, teremos o procedimento abaixo:

  Procedure busca_insere(x: T; Var L, p: Lista);
    var p: Lista;

  Begin
    p := L;
    sentinela^.info := x;
    While p^.info <> x do
      p := p^.lig;
    If (p = sentinela) Then
      Begin
                           { inserção no começo da lista}
        p := L;            {aponta primeiro}
        new(L);            {novo registro é primeiro}
        L^.info := x;
        L^.lig := p;
      End;
  End;

4) Sentinela em busca com lista encadeada ordenada

No algoritmo acima, ao realizar uma busca sequencial numa lista encadeada anulamos a vantagem de utilizar listas encadeadas. Neste caso, esta implementação só pode ser considerada para listas com um número pequeno de elementos.

No caso da lista estar ordenada, a busca termina assim que encontrarmos um elemento maior que aquele que buscamos. A ordenação é obtida ao inserirmos cada novo elemento na sua posição correta, ao invés de na cabeça da lista.

Essa "ordenação" na realidade não tem custo algum, porque fazemos uso das características da lista encadeada. Isso não ocorre com estruturas estáticas como o array e os arquivos sequenciais.

O procedimento abaixo elimina um registro que contém o elemento v de uma lista apontada por L.

O bloco de busca pelo elemento realiza dois testes para cada elemento da lista. Esse esforço pode ser reduzido introduzindo o recurso de sentinela.

Depois da busca, testes devem ser efetuados para verificar se:

  Procedure elimina(v: integer; Var Prim: Lista);

  Var
    p, pa: Lista;
    acabou: boolean;

  Begin
    pa := nil;
    p := L;
    acabou := (p = nil);
    While (not acabou) do
      If p^.info < v Then
        Begin
       	  pa := p;
          p := p^.lig;
          acabou := (p = nil);
        End
      Else acabou := true;
    {  p = nil   ou  p^.info = v  ou  p^.info > v  }
    If (p = nil) Then 
      "lista não contém v"
    Else
      If p^.info > v Then  
        "lista não contém v"
      Else
        Begin
	  If pa = nil Then 
            L := p^.lig
	  Else 
            pa^.lig := p^.lig;
	  dispose(p);
        End;
  End;

  new(root);
  new(sentinel);
  root^.lig := sentinel;

  Procedure  busca_insere(x: T;  Var root: Lista);
    Var w1, w2, w3: Lista;

  Begin
    w2 := root;
    w1 := w2^.lig;
    sentinel^.info := x;
    While w1^.info < x do
      Begin
        w2 := w1;
        w1 := w1^.lig;
      End;
    If (w1^.info = x) and (w1 <> sentinel) Then
      {elemento já existe}
    Else
      Begin
        new(w3);  {insere  w3 entre w1 e w2}
        w3^.info := x;
        w3^.lig := w1;
        w2^.lig := w3;
      End;
  End;