Listas enlazadas en Pascal

Cuando se procesan conjuntos de datos cuyo espacio de almacenamiento no se puede predecir a priori ( en tiempo de compilación) y además la actividad de los mismos (inserciones y borrados) es frecuente, las estructuras de datos estáticas (los arrays) no son adecuadas para su implementación. Las razones son varias:

1. Los arrays deben ser declarados en tamaño en el programa fuente, de modo que si se elige uno mayor que el necesario, entonces se desperdicia espacio de memoria.
2. La operación de añadir datos al final de la lista (el arrays) es un proceso rápido; sin embargo, las inserciones y eliminaciones en el interior del array son lentas y complejas, ya que puede ser necesario desplazar cada elemento del array para hacer espacio al nuevo elemento, o bien cerrar el espacio dejado por una eliminación.

Las listas enlazadas son una secuencia de nodos que se encuentran enlazados cada uno con el siguiente mediante una liga (enlace) o apuntador. Cada elemento (nodo) de una lista enlazada debe tener dos campos: un campo (datos) que contiene el valor de ese elemento y un campo liga(apuntador) que indica la posición del siguiente elemento.

Los elementos de una lista están conectados o "enlazados" mediante sus campos liga o apuntador. Los componentes de un nodo se llaman campos. El campo liga apunta (indica la dirección) al siguiente nodo de la lista. Existe una marca de fin de lista, que es la constante nil, también representada por el signo eléctrico de tierra.

El campo datos puede contener cualquier tipo estándar o definido por el usuario. El campo liga contiene el punto al siguiente elemento de la lista.

Formato de declaración de un nodo (por ejemplo, de enteros)

Type
  nodo   = ^enteros; 
  enteros = record
                       numero :integer;
                       liga        : nodo
                    end;

Por medio del siguiente programa se ejemplificarán las diversas operaciones con listas enlazadas:

inicialización, creación, recorrido, inserción, borrado, busqueda.

Program Listas_enlazadas;
 {El siguiente programa realiza las operaciones
  de altas,bajas y consultas  del control de
  empleados por medio de listas enlazadas}
Uses Crt;
Const
  esc = #27;
Type
  nodos = ^datos;
  datos = record
            clave  : string[3];
            nombre : string[30];
            puesto : string[20];
            sueldo : real;
            liga   : nodos
          end;
Var
  p,q,inicio:nodos;
  tecla     :char;
{procedimiento para insertar un
 nodo al final de la lista}
procedure inserta_nodo(var p : nodos);
begin
  if inicio=nil then
    inicio:=p
  else
    q^.liga:=p;
  q:=p
end;
procedure elimina_nodo(var p,q:nodos);
begin
  if p=inicio then
    begin
      if inicio^.liga=nil then
        inicio:=nil
      else
        inicio:=inicio^.liga
    end
  else
    q^.liga := p^.liga;
    dispose(p)
end;

function busca_clave(var p,q:nodos;clave:string):boolean;
begin
  if inicio <> nil then
    begin
      p:=inicio;
      While ((p^.clave<>clave)and (p^.liga<>nil)) do
        begin
          q:=p;
          p:=p^.liga
        end;
      if p^.clave=clave then
        busca_clave:=true
      else
        busca_clave:=false
    end
  else
    busca_clave:=false
end;
procedure libera_memoria;
begin
  p:=inicio;
  while(p<>nil) do
    begin
      q:=p;
      p:=p^.liga;
      dispose(q)
    end
end;
procedure altas;
Var
  otro:char;
begin
  Repeat
    ClrScr;
    gotoxy(30,5);Write('Altas de empleados');
    New(p);
    p^.liga:=nil;
    {inicializa la liga a nil}
    gotoxy(25,7);Write('Clave : ');
    ReadLn(p^.clave);
    gotoxy(25,8);Write('Nombre : ');
    ReadLn(p^.nombre);
    gotoxy(25,9);Write('Puesto : ');
    ReadLn(p^.puesto);
    Repeat
    {$I-}  {validación de entrada de datos}
     gotoxy(25,10);write('Sueldo : ');
     ReadLn(p^.sueldo);
    {$I+}
    until IOResult=0;
    inserta_nodo(p);
    gotoxy(20,22);write('Desea dar otra alta s/n? ');
    otro:=ReadKey
  until otro in ['n','N',Esc]
end;
procedure bajas;
Var
  otro :char;
  clave:string[3];
begin
  Repeat
    ClrScr;
    gotoxy(30,5);Write('Bajas de empleados');
    gotoxy(25,7);Write('Clave : ');
    ReadLn(clave);
    if  busca_clave(p,q,clave) then
      begin
        gotoxy(25,8);Write('Nombre : ');
        Write(p^.nombre);
        gotoxy(25,9);Write('Puesto : ');
        Write(p^.puesto);
        gotoxy(25,10);write('Sueldo : ');
        Write(p^.sueldo:6:2);
        gotoxy(20,15);Write('Desea eliminarlo s/n? ');
        otro:=ReadKey;Write(otro);
        if otro in['s','S'] then
          elimina_nodo(p,q)
      end
    else
      begin
        gotoxy(20,10); Write('La clave no existe...')
      end;
    gotoxy(20,22);write('Desea dar otra baja s/n? ');
    otro:=ReadKey
  until otro in ['n','N',Esc]
end;

procedure consultas;
begin
  p:=inicio;
  while p<>nil do
    begin
      ClrScr;
      gotoxy(30,5);Write('Consulta de empleados');
      gotoxy(25,7);Write('Clave : ');
      Write(p^.clave);
      gotoxy(25,8);Write('Nombre : ');
      Write(p^.nombre);
      gotoxy(25,9);Write('Puesto : ');
      Write(p^.puesto);
      gotoxy(25,10);write('Sueldo : ');
      Write(p^.sueldob>:6:2);
      gotoxy(20,22);Write('Presione una tecla...');
      p:=p^.liga;
      ReadKey
    end
end;

begin
  inicio:=nil;
  Repeat
    ClrScr;
    gotoxy(30,5);Write('Control de empleados');
    gotoxy(35,8);Write('1. Altas');
    gotoxy(35,9);Write('2. Bajas');
    gotoxy(35,10);write('3. Consultas');
    gotoxy(35,11);Write('4. Salir (Esc)');
    gotoxy(35,13);Write('Opción [ ]');
    gotoxy(43,13);
    tecla:=ReadKey;
    case tecla of
                 '1' :altas;
                 '2' :bajas;
                 '3' :consultas
    end
  until tecla in ['4',esc];
  libera_memoria;
  ClrScr
end.