En este artículo el autor describe como se implementan las listas enlazadas en el lenguaje de programación Object Pascal.
Los datos son los objetos sobre los cuales opera la computadora. Cualquier programa escrito en un lenguaje de programación, puede ser considerado como la descripción de un conjunto de datos y un conjunto de operaciones que se le aplican a estos en un orden determinado.
La palabra dato hace referencia a valores simples o conjunto de valores y pueden organizarse en muchas formas. Al modelo matemático o lógico de una organización particular de datos se le conoce con el nombre de estructura de datos.
Las estructuras de datos pueden clasificarse en lineales y no lineales. Se dice que una estructura es lineal si sus elementos forman una secuencia y existen dos formas básicas de representarlas en la memoria de la computadora.
Una de ellas es almacenando sus elementos en posiciones continuas y otra es reflejando la relación entre los elementos por medio de punteros o enlaces. Las primeras estructuras reciben el nombre de arreglos (Array) y las segundas listas enlazadas.
Este trabajo tiene como propósito describir la implementación de estas últimas en Object Pascal.
Una lista enlazada es una colección lineal de elementos donde el orden de los mismos se establece mediante punteros. La idea básica es que cada componente de la lista incluya un puntero que indique donde puede encontrarse el siguiente componente por lo que el orden relativo de estos puede ser fácilmente alterado modificando los punteros lo que permite, a su vez, añadir o suprimir elementos de la lista.
Por tanto, una lista enlazada no está limitada a contener un número máximo de componentes; puede expandir o contraer su tamaño mientras se ejecuta el programa.
Entre las diferentes clases de estructuras enlazadas se encuentran las listas enlazadas o listas unidireccionales y las listas dobles o bidireccionales. En las listas unidireccionales cada elemento está encadenado al siguiente y se tiene un apuntador al primer elemento (Cabeza de la lista) y en las listas bidireccionales cada elemento de la lista está encadenado con el siguiente y con el precedente y en la cabeza de la lista se tiene un apuntador al primer y al último elemento de la lista.
Las listas enlazadas tienen el inconveniente de que solo pueden recorrerse en una dirección. Podemos movernos por la lista partiendo del primer elemento y siguiendo a los apuntadores que se conservan en la lista junto con los elementos recorrerla hasta el final, pero no es posible moverse hacia atrás. Las listas doblemente enlazadas aunque implican un gasto adicional de memoria, se justifica su uso en los casos donde es necesario poder recorrer la lista en los dos sentidos.
Para ilustrar como se implementan las listas enlazadas en Object Pascal, se analiza a continuación como se podría crear una lista de nombres de personas y una vez creada tener la posibilidad de visualizar, añadir o eliminar elementos de la misma.
Para implementar las listas enlazadas se debe trabajar con dos tipos diferentes de variables: variables punteros, es decir, variables cuyos valores apuntan a otras variables, y variables referenciadas, o sea, variables que son apuntadas.
La variable referenciada será un registro (Record) que tendrá por nombre Persona y estará formado por dos campos: Nombre para almacenar los nombres de las personas y Siguiente que se utilizará para apuntar al siguiente elemento de la lista.
Para declarar y asociar la variable de tipo puntero a una variable referenciada se escribe:
Nombre de la variable puntero = ˆ Nombre de la variable referenciada
Type
Apuntador = ˆ Persona;
Persona = Record
Nombre : String;
Siguiente : Apuntador;
End;
Observe que la declaración de la variable referenciada aparece después de la definición de la variable puntero.
Para crear variables referenciadas se utiliza el procedimiento estándar New.
La lista enlazada se construirá creando cada componente y enlazándolo, después que se cree el próximo elemento, a su sucesor. Para ello se declaran las variables de tipo Apuntador:
Lista para almacenar el componente que se crea.
Primero para apuntar al primer elemento de la lista.
Predecesor para referirse al componente creado con anterioridad al que se está creando.
Comenzar para indicar cual es el primer elemento de la lista cuando se vaya a visualizar.
Antecesor para indicar el antecesor del elemento que se inserte o elimine de la lista.
Var
Lista, Primero, Predecesor, Comenzar, Antecesor : Apuntador;
Lista contiene dos campos: una variable de cadena llamada Lista.Nombre y una variable puntero, Lista.Siguiente. el puntero permitirá enlazar el elemento al componente que se cree con posterioridad a este, pero en el momento de su creación tendrá el valor Nil para indicar el final de la lista.
La variable Predecesor debe apuntar hacia el elemento que se crea para poderse referir a él cuando se cree el próximo componente.
Para crear el primer componente se escribe:
New (Lista);
Lista.Nombre := Primer nombre de persona;
Lista.Siguiente := Nil;
Primero := Lista;
Predecesor:= Lista;
y para el resto de los componentes:
New (Lista);
Lista.Nombre := Siguiente nombre de persona;
Lista.Siguiente := Nil;
Predecesor.Siguiente := Lista;
Predecesor:= Lista:
Note cómo en la cuarta línea (Predecesor.Siguiente := Lista;) se actualiza el puntero del componente creado con anterioridad para que apunte a este nuevo componente.
La lista puede ser visualizada fácilmente ya que la variable puntero Primero indica la posición del primer componente de la misma y cada elemento de la lista apunta a su sucesor.
Comenzar := Primero;
While Comenzar <> Nil do
begín
Lista := Comenzar ;
Lista.Nombre;
Comenzar := Lista.Siguiente;
end;
Para insertar un componente en una posición determinada dentro de una lista enlazada que ya ha sido creada basta con crear el nuevo componente, determinar la posición que va a ocupar y ajustar algunos punteros.
New (Lista);
Lista.Nombre := Nuevo nombre de persona;
Para determinar la posición del nuevo componente se utiliza una variable de tipo cadena para almacenar en ella el nombre de la persona detrás de la cual se desea insertar el nuevo elemento y a la que llamaremos Nombre. La estrategia será recorre la lista hasta que se encuentre el elemento detrás del que se desea insertar, es decir, hasta encontrar el componente que será el antecesor del nuevo elemento
Antecesor := Primero;
While (Antecesor.Nombre <> Nombre) And (Antecesor.Siguiente <> Nil) do
Antecesor := Antecesor.Siguiente;
Para realizar el ajuste de los punteros se debe tener presente que el puntero del nuevo componente debe apuntar a donde apuntaba su antecesor y el puntero del antecesor debe apuntar al nuevo componente.
Lista.Siguiente := Antecesor.Siguiente;
Antecesor.Siguiente := Lista;
Para suprimir un elemento, primeramente se localiza, se reajusta después algunos punteros y se destruye utilizando el procedimiento estándar Dispose.
Para eliminar el primer elemento:
Lista := Primero;
Primero := Lista.Siguiente;
Dispose (Lista)
y para eliminar cualquier otro elemento:
Lista := Primero.Siguiente;
While (Lista.Nombre <> Nombre) And (Lista.Siguiente <> Nil) do
begin
Antecesor := Lista;
Lista := Lista.Siguiente ;
end;
Antecesor.Siguiente := Lista.Siguiente ;
Dispose (Lista);
Si fuese necesario poder recorrer la lista en los dos sentidos, entonces se tendría que implementar una lista doblemente enlazada para lo cual se deberían realizar los siguientes cambios:
La variable referenciada Persona debe contener otro campo que permita apuntar al elemento anterior de la lista.
Persona = Record
Nombre : String;
Siguiente : Apuntador;
Anterior : Apuntador;
End;
Se necesita declarar dos variable más de tipo Apuntador:
Ultimo para apuntar al último elemento de la lista.
Sucesor para indicar el sucesor del elemento que se inserte o elimine de la lista.
Var
Lista, Primero, Predecesor, Comenzar, Antecesor, Sucesor : Apuntador;
Al crear el primer componente la variable puntero Lista.Anterior debe tener el valor Nil para indicar el final de la lista.
La variable Ultimo debe apuntar al elemento que se crea para indicar que es el último en ese momento.
New (Lista);
Lista.Nombre := Primer nombre de persona;
Lista.Siguiente := Nil;
Lista.Anterior := Nil;
Primero := Lista;
Predecesor := Lista;
Ultimo := Lista;
Para crear los demás componentes:
New (Lista);
Lista.Nombre := Siguiente nombre de persona;
Lista.Siguiente := Nil;
Lista.Anterior := Predecesor;
Predecesor.Siguiente := Lista;
Predecesor := Lista;
Ultimo := Lista;
Para visualizar la lista en orden inverso, la variable Comenzar se inicializa con el valor de la variable Ultimo que apunta al último elemento:
Comenzar := Ultimo;
While Comenzar <> Nil do
begin
Lista := Comenzar;
Lista.Nombre;
Comenzar := Lista.Anterior;
end;
Para insertar o eliminar un elemento sólo hay que determinar el antecesor y el sucesor del elemento y reajustar los puntero Siguiente y Anterior:
Para insertar un elemento:
New (Lista);
Lista.Nombre := Nuevo nombre de persona;
Antecesor := Primero;
While (Antecesor.Nombre <> Nombre) And (Antecesor.Siguiente <> Nil) do
Antecesor := Antecesor.Siguiente;
Sucesor := Antecesor.Siguiente;
Lista.Siguiente := Sucesor;
Lista.Anterior := Antecesor;
Antecesor.Siguiente := Lista;
Sucesor.Anterior := Lista;
Para eliminar el primer elemento:
Lista := Primero;
Primero := Lista.Siguiente;
Primero.Anterior := Nil;
Dispose (Lista)
y para eliminar cualquier otro elemento:
Lista := Primero.Siguiente;
While (Lista.Nombre <> Nombre) And (Lista.Siguiente <> Nil) do
begin
Antecesor := Lista;
Lista := Lista.Siguiente ;
end;
Sucesor := Lista.Siguiente;
Antecesor.Siguiente := Sucesor;
Sucesor.Anterior := Antecesor;
Dispose (Lista);
El conocimiento de la implementación de las listas enlazadas facilita la representación eficiente de los datos en la memoria de la computadora cuando la cantidad de elementos no es previsible por cuanto el uso de variables de tipo puntero permite crear y destruir variables referenciadas dinámicamente.
Katrib Mora, Miguel. Lenguajes de programación y Técnicas de compilación.– Ciudad de la Habana : Editorial Pueblo y Educación, 1988
Gottfried, Byron S. Programación en Pascal.– Ciudad de la Habana : Editorial Pueblo y Educación, 1989
Lipschutz, Seymour. Estructura de datos.– Ciudad de la Habana : Edición Revolucionaria, 1989
Autor:
Asistente Juan Antonio Fonseca Hernández.