Type  prec = ^rec;
        Lista = prec;
        rec = record
                info: T;     {seu tipo preferido}
                lig:  Lista
              End;

  Var p: Lista;     {ponteiro para qualquer elemento da lista}
      L: Lista;     {ponteiro para o primeiro elemento da lista }

Operações sobre Listas Dinâmicas

1. Criar lista vazia
2. Inserir primeiro elemento
3. Inserir no início de uma lista
4. Acessar primeiro elemento
5. Acessar último elemento
6. Tamanho da lista
7. Inserir valor
   (a) Inserir valor v depois do elemento apontado por k
   (b) Inserir valor v na posição pos
8. Eliminar elemento
   (a) Remover elemento apontado por j, que segue k
   (b) Remover elemento da posição pos
9. Eliminar primeiro elemento
10. Eliminar um valor v de uma lista ordenada
11. Inserir valor v antes do elemento apontado por p
12. Criar uma lista com registros numerados (de 1 a n)
13. Eliminar sucessor de p e inserir como cabeça em uma lista apontada por q
14. Imprimir recursivamente

Implementação das Operações

1) Criar lista vazia

Procedure Criar (Var L : Lista);
Begin
  L:= nil;
End;

2) Inserir primeiro elemento

Procedure Insere_Prim(Var L: Lista; valor: T);
Var p: Lista;
Begin
  new(p);
  p^.info := valor;
  p^.lig := nil;
  L := p;
End;

3) Inserir no início de uma lista

Procedure Insere_Inic(Var L: Lista; valor: T);
Var p: Lista;
Begin
  new(p);
  p^.info := valor;
  p^.lig := L;
  L  := p;
End;

4) Acessar primeiro elemento

Function Prim(L: Lista): T;
Begin
  Prim:= L^.info
End;

5) Acessar último elemento

Function Ultimo(L: Lista): T;
Begin
  If L = nil Then 
    { lista vazia}
  Else
    Begin
      p := L;
      While p^.lig <> nil do 
        p := p^.lig;
      Ultimo := p^.info;       {p^.info é último elemento}
    End;                  {p^ é o último registro}
End;

6) Tamanho da lista

Function Nelem(L: Lista): integer;
Begin
  If L = nil Then
    Nelem := 0
  Else
   Begin
     p := L;
     Nelem := 1;
     While p^.lig <> nil do
       Begin
         Nelem := Nelem + 1;
         p := p^.lig;
       End;
   End;
End;

7) Inserir valor
(a) Inserir valor v depois do elemento apontado por k

Procedure Insere_Depois(v: T; k: Lista);
Var q: Lista;
Begin
    new(q);
    q^.info := v;
    q^.lig := k^.lig;
    k^.lig := q;
End;

(b) Inserir valor v na posição pos

Function Insere_Pos (VAR L:Lista; v:T; pos:integer);
begin
    if L=nil then
        Insere_Prim (L,v)
    else
        if pos = 1 then
            Insere_Inic (L,v)
        else
            begin
                m = pos-1;
                p: = L;
                c=1;
                while (c<m) and (p^.lig <> nil) do
                begin
                    p:= p^.lig;
                    c := c+1;
                end;
                if c=m then {p é ponteiro para o anterior}
                    Insere_Depois (v,p)
                else
                    "nao existe posição pos na lista"
            end;
end;

Procedure Elimina_Depois(k, j: Lista);
Begin
    k^.lig := j^.lig;
    dispose(j);
  End;

Function Remove_pos (VAR L:Lista; pos:integer);

begin
        if pos = 1 then
           Remove_Prim (L) {ver operação número 9}
        else
        begin
            m = pos-1;
            p: = L;
            c=1;
            while (c<=m) and (p^.lig <> nil) do
            begin
                    pa := p;
                    p:= p^.lig;
                    c := c+1;
            end;
            if (c=pos) and (p<>nil)  then {pa é ponteiro para o anterior}
                Elimina_depois (pa,p)
            else
                "nao existe posição pos na lista"
    end;
end;

9) Remoção do primeiro elemento

Procedure Remove_Prim(Var L: Lista);
  Begin
    p := L;
    L:= L^.lig;
    dispose(p)
  End;

10) Eliminar um valor v de uma lista ordenada

  Procedure Elimina(v: T; Var L: 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;
    {While acaba aqui!}
    { 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
            Remove_prim(L)
          Else Elimina_depois(pa,p);
        End;
  End;

-> Fazer a eliminação de v de uma lista não ordenada

11) Inserção do valor v antes do elemento apontado por p

Uma alternativa para evitarmos percorrer a lista para encontrar o antecessor de p é inserirmos o valor dado, de fato, após o elemento apontado por p, após realizar uma cópia de conteúdo entre ponteiros....

Procedure Insere_antes(v: T; p: Lista);
Var q: Lista;
Begin
  new(q);
  q^ := p^;
  p^.info := v;
  p^.lig := q;
End;

-> Fazer a inserção de um elemento de valor v numa lista encadeada ordenada. Utilizar o que for
possível das operações pré-definidas
 

12) Criar uma lista com registros numerados (de 1 .. n)

Procedure Cria_Lista_num(Var L: Lista);
  Var  L, q: Lista;
  Begin
    L := nil;   { começa com lista vazia }  
    While n > 0 do
      Begin
        new(q);
        q^.lig := L;
        q^.info := n;
        L := q;
        n := n-1;
      End;
  End;

13) Eliminar sucessor de p e inserir como cabeça em uma lista apontada por q

Procedure Remove_Insere(Var q: Lista; p: Lista);
  Begin
    r := p^.next;         {r aponta o sucessor de p^}
    p^.lig := r^.lig;     {r^ sai da lista}
    r^.lig :=  q;         {r^ passa a apontar q^ }
    q := r;               {r^ passa a ser o primeiro elemento da lista
  End;                     apontada por q}

14) Imprimir recursivamente

  Procedure Printlist(p: Lista);
    Begin
      If (p <> nil) Then
        Begin
          write(p^.info);
          Printlist(p^.lig);
        End;
    End;

-> Elaborar os seguintes TADs:

Lista Encadeada Ordenada

Lista Encadeada Não-ordenada

Usando a estrutura acima.

Implementar usando Units do Pascal.

Algoritmos de Busca Dinâmica

Lista Dinâmica