Monografias.com > Computación > Programación
Descargar Imprimir Comentar Ver trabajos relacionados

Listas enlazadas y su implementación en Object Pascal



    1. Resumen
    2. Desarrollo
    3. Conclusiones
    4. Bibliografía

    Resumen:

    En este artículo el autor describe como se
    implementan las listas enlazadas en el lenguaje de
    programación Object Pascal.

    Introducción:

    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.

    Desarrollo:

    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);

    Conclusiones:

    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.

    Bibliografía:

    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
    .

    Nota al lector: es posible que esta página no contenga todos los componentes del trabajo original (pies de página, avanzadas formulas matemáticas, esquemas o tablas complejas, etc.). Recuerde que para ver el trabajo en su versión original completa, puede descargarlo desde el menú superior.

    Todos los documentos disponibles en este sitio expresan los puntos de vista de sus respectivos autores y no de Monografias.com. El objetivo de Monografias.com es poner el conocimiento a disposición de toda su comunidad. Queda bajo la responsabilidad de cada lector el eventual uso que se le de a esta información. Asimismo, es obligatoria la cita del autor del contenido y de Monografias.com como fuentes de información.

    Categorias
    Newsletter