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.