Lección 10 · 10 de 20

Una lista enlazada · Pascal

Construya una lista enlazada en Pascal con records y punteros: crear nodos, insertar en medio sin mover nada y liberar toda la memoria.

Pascal · Una lista enlazada en DMarlon Studio: el código del ejemplo y su salida en la terminal

Una lista enlazada guarda cada elemento en un nodo separado que apunta al siguiente. Aquí cada nodo es una parada de autobús, TStop, con su nombre y el campo Next. El tipo PStop se declara antes que el record al que apunta: Pascal lo permite con los punteros siempre que el record llegue en el mismo bloque type, y aquí hace falta porque el record se refiere a sí mismo a través del puntero.

NewStop reserva un nodo con New(Result), lo rellena y devuelve su dirección. Como recibe el siguiente nodo como parámetro, las llamadas anidadas construyen la ruta de atrás hacia delante: primero Moncloa (que apunta a nil, el final), luego Gran Via y por último Sol, que queda en route.

Insertar es la gran ventaja: route^.Next := NewStop('Callao', route^.Next) crea un nodo que apunta a lo que venía después de Sol y engancha Sol al nuevo. No se mueve ningún elemento, a diferencia de un array, donde habría que desplazar todos los posteriores.

ToText recorre la lista de forma recursiva: el texto de una parada es su nombre más el texto del resto, hasta llegar a nil, que devuelve end. Al final, el bucle while libera los nodos uno a uno, guardando antes Next en next, porque tras Dispose(route) ese campo ya no se puede leer.

Código · main.pas

program main;type  PStop = ^TStop;  // the pointer type may come before its record  TStop = record    Name: String;    Next: PStop;  end;function NewStop(const name: String; next: PStop): PStop;begin  New(Result);  Result^.Name := name;  Result^.Next := next;end;function ToText(stop: PStop): String;begin  if stop = nil then Exit('end');  Result := stop^.Name + ' > ' + ToText(stop^.Next);  // this stop, then the restend;var route, next: PStop;begin  route := NewStop('Sol', NewStop('Gran Via', NewStop('Moncloa', nil)));  WriteLn(ToText(route));  route^.Next := NewStop('Callao', route^.Next);  // insert after Sol  WriteLn(ToText(route));  while route <> nil do  // free every node, front to back  begin    next := route^.Next;    Dispose(route);    route := next;  end;end.

Salida · fpc main.pas && ./main

Sol > Gran Via > Moncloa > end
Sol > Callao > Gran Via > Moncloa > end

Para recordar

Cada nodo guarda un dato y un puntero al siguiente; nil marca el final.
El tipo puntero puede declararse antes que su record, en el mismo type.
Insertar solo cambia punteros: no mueve nada.
Para liberar, guarde Next antes de Dispose.
Recorrer una lista se presta a la recursión.

Ejercicio

Quite la parada Gran Via de la ruta: haga que Callao apunte a Moncloa, libere el nodo sobrante con Dispose y vuelva a escribir la ruta.