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:
- 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.
- 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.