1. Listas Enlazadas

Se describe como se implementan las listas enlazadas en el lenguaje de programación Object Pascal.

1.1  Introducción.

Una lista enlazada la constituye una colección lineal de elementos, llamados nodos, donde el orden de los mismos se establece mediante punteros. Cada nodo se divide en dos partes: una primera que contiene la información asociada al elemento, y una segunda parte, llamada campo de enlace o campo al siguiente puntero, que contiene la dirección del siguiente nodo de la lista.

 1.2 Listas Enlazadas

Listas simples enlazadas

La lista enlazada básica es la lista enlazada simple la cual tiene un enlace por nodo. Este enlace apunta al siguiente nodo en la lista, o al valor NULL o a la lista vacía, si es el último nodo.

Una lista enlazada simple contiene dos valores: el valor actual del nodo y un enlace al siguiente nodo

Lista Doblemente Enlazada

Un tipo de lista enlazada más sofisticado es la lista doblemente enlazada o lista enlazadas de dos vías. Cada nodo tiene dos enlaces: uno apunta al nodo anterior, o apunta al valor NULL si es el primer nodo; y otro que apunta al nodo siguiente, o apunta al valor NULL si es el último nodo.

 

Una lista doblemente enlazada contiene tres valores: el valor, el link al nodo siguiente, y el link al anterior

En algunas aplicaciones podemos desear recorrer la lista hacia adelante y hacia atrás, o dado un elemento, podemos desear conocer rápidamente los elementos anterior y siguiente. En tales situaciones podríamos desear darle a cada celda sobre una lista un puntero a las celdas siguiente y anterior en la lista tal y como se muestra en la figura.

Listas enlazadas circulares

En una lista enlazada circular, el primer y el último nodo están unidos juntos. Esto se puede hacer tanto para listas enlazadas simples como para las doblemente enlazadas. Para recorrer una lista enlazada circular podemos empezar por cualquier nodo y seguir la lista en cualquier dirección hasta que se regrese hasta el nodo original. Desde otro punto de vista, las listas enlazadas circulares pueden ser vistas como listas sin comienzo ni fin. Este tipo de listas es el más usado para dirigir buffers para “ingerir” datos, y para visitar todos los nodos de una lista a partir de uno dado.

1.3 Representación de listas enlazadas en memoria

Sea LISTA una lista enlazada, salvo que se indique lo contrario. Almacenaremos LISTA en memoria de la forma siguiente. Como mínimo, LISTA estará compuesta por dos arrays lineales, a los que llamaremos INFO y ENLACE, tales que INFO [K] y ENLACE [K] contienen la parte de información y el campo de puntero de cada nodo de LISTA respectivamente. Necesitamos también una variable especial llamada COMIENZO que contiene la posición ocupada por el primer elemento de la lista, y una marca especial NULO que indica el final de la misma. Puesto que los índices de los arrays INFO y ENLACE serán habitualmente positivos, el valor NULO será el -999, salvo que digamos lo contrario.

 1.4 Recorrido y búsqueda en una lista enlazada

Sea la lista enlazada, almacenada en memoria mediante dos arrays INFO y ENLACE. Adicionalmente definimos la variable COMIENZO que apunta al primer elemento de la lista y suponemos que el último nodo de la lista contiene en su campo ENLACE el valor NULO. Supongamos que queremos RECORRER LISTA para procesar cada uno de sus nodos exactamente una vez.

1.5 Ejemplo

Este ejamplo esta super didactico.