La Página de DriverOp

Implementación de lista dinámica simplemente enlazada.

El uso de listas dinámicas es una de las herramientas más útiles que existen en Pascal o en cualquier otro lenguajes que lo permita.

La gran ventaja de usar punteros a memoria para referenciar datos consiste en que uno puede ir usando memoria a medida que lo necesita, al contrario de los datos estáticos (tal como un array) donde el uso de la memoria es fijo y permanece ocupada aún si esas posiciones no contienen dato útil alguno.

A continuación expongo el código fuente de ejemplo de cómo manejar una lista dinámica simplemente enlazada. Una lista es una estructura de datos donde cada elemento de la lista tiene un predecesor y un sucesor excepto el primero y el último respectivamente, un array es una lista de tamaño fijo, una lista dinámica es una lista que no tiene tamaño fijo sino que se van agregando o quitando elementos según se requiera. Una lista dinámica simplemente enlazada es aquella que cada elemento tiene un sucesor conocido pero no un predecesor. Para lograr esto se hace uso de punteros a memorias. Un puntero a memoria es una variable que contiene la dirección de memoria del dato apuntado.

El código fuente es:

uses crt;
type
  TStr6=String[6];
           Pnodo=^TNodo;
           TNodo=record
   Placa:TStr6;
   Sig:PNodo;
 end; { TNodo }
var
  Primero:PNodo;
  fin:boolean;
  Aux:TStr6;

procedure EliminarLista(P: PNodo);
var
  Aux: PNodo;
begin
  while P^.Sig <> nil do
    begin
      Aux:=P^.Sig;
      Dispose(P);
      P:=Aux;
    end;
end; { EliminarLista }

procedure MostrarLista(P: PNodo);
begin
  while P <> nil do
     begin
       WriteLn(P^.Placa);
       P:=P^.Sig;
     end;
end; { MostrarLista }

procedure PonerEnLista(Dato: TStr6);
var
  Nuevo, P, Anterior:PNodo;
  fin: boolean;
begin
new(Nuevo);
Nuevo^.Placa:=Dato;
Nuevo^.Sig:=nil;
Anterior:=nil;
if Primero = nil then
  begin
    Primero:=Nuevo;
  end
else
  begin
    P:=Primero;
    fin:=false;
    while (P<>nil) and (not fin) do
      begin
        if P^.Placa < Nuevo^.Placa then
          begin
            Anterior:=P;
            P:=P^.Sig;
          end { then }
        else
          begin
            if (Anterior<>nil) then
              begin
                 Anterior^.Sig:=Nuevo;
                 Nuevo^.Sig:=P;
                 fin:=true;
              end { then }
            else
              begin
                Nuevo^.Sig:=P;
                Primero:=Nuevo;
                fin:=true;
              end; { else }
          end; { else }
      end; { while }
    if not fin then
      begin
        Anterior^.Sig:=Nuevo;
        Nuevo^.Sig:=nil;
      end;
  end; { else }
end; { PonerEnLista }

begin
  clrscr;
  Primero:=nil;
  fin:=false;
  WriteLn('Para finalizar ingrese 6 espacios.');
  while not fin do
     begin
       Write('Ingrese una Placa: ');
       Readln(Aux);
       if Aux = ' ' then fin:=not fin
       else PonerEnLista(Aux);
     end;
            MostrarLista(Primero);
  readkey;
  if Primero <> nil then EliminarLista(Primero);
end.

En este ejemplo suponemos que queremos almacenar las placas (patentes) de vehículos pero en forma ordenada alfabéticamente. La estructura registro TNodo sirve para esto, teniendo un campo placa y otro campo sig que es un puntero a TNodo, este puntero apuntará al sucesor de la lista.

Cuando nos planteamos el problema vemos que hay tres casos posibles cada vez que creamos un nodo nuevo para la lista.

  • El nuevo elemento de la lista será el primero de la lista.
  • El nuevo elemento irá insertado enmedio de dos otros elementos ya ordenados.
  • El nuevo elemento será el nuevo último elemento de la lista.

En el código fuente, primero pedimos una nueva placa y se la pasamos como parámetro al procedimiento PonerEnLista.

Este procedimiento primero verifica que la lista esté vacía. Si lo está, el nuevo nodo creado será el primero nodo y sale.

Si la lista no está vacia comienza un ciclo while, resguarda el puntero al primero de la lista y usa ese resguardo (P) para recorrer la lista. Pregunta si el dato del nodo P es menor al dato del nodo Nuevo (que es el que queremos insertar en la lista) si es menor resguarda el puntero a ese nodo antes de pasar al siguiente ya que en una lista simplemente enlazada un nodo cualquiera no puede saber cuál es su predecesor.

En caso de que el dato sea igual o mayor pregunta si el predecesor de P es distinto de nulo, si lo es significa que estamos insertando entre dos nodos de la lista, para ello asignamos el puntero sig del Anterior al Nuevo nodo y el sig del Nuevo a P.

Si Anterior es igual a nulo (else de la pregunta) significa que Nuevo tiene que ser el nuevo primero nodo de la lista ya que Anterior no quedó asignado durante la búsqueda, es decir el nodo P no tiene predecesor. Entonces el sig de Nuevo será P y el puntero al Primer nodo apuntará al Nuevo.

En ambos casos se termina el ciclo while.

Si vemos las condiciones de finalización del ciclo while veremos que son dos, la primera indica si llegamos al final de la lista sin haber hecho ninguna inserción, es decir, el Nuevo no va ni al principio ni al medio. La segunda condición es que ya se haya insertado un nodo nuevo.

A la salida del ciclo pregunta si no se ha insertado un nodo (variable fin), en caso de que así sea, el Nuevo nodo será el Nuevo último nodo. Entonces se asigna sig del Anterior al Nuevo y el sig de Nuevo se asigna nulo. El primer if del procedimiento asegura que nunca se entre el ciclo while con una lista con solo un elemento en ella.

Ir a lista doblemente enlazada.

Por Diego Romero,