PDF de programación - 9 Estructuras de datos: Listas Uni y Bidireccionales

A. Dasso, A. Funes -

Introducción a la Programación -

Notas de Clase

Listas

9 ESTRUCTURAS DE DATOS: LISTAS UNI Y BIDIRECCIONALES

9.1 LISTAS UNIDIRECCIONALES

COMPOSICIÓN DE LOS ELEMENTOS

Los elementos de una lista unidireccional o secuencia, llamados nodos, constan de dos partes:

La Variable de Información Propiamente Dicha (VIPD), que es donde se almacena la información que
corresponde a cada elemento de la lista. Las VIPDs de una lista son todas del mismo tipo, aun cuando, obviamente,
puedan no tener necesariamente el mismo valor.

El puntero al elemento (nodo) siguiente en la lista, el cual puede encontrase no necesariamente contiguo. En el

caso del último elemento, el puntero no apunta a un elemento y se dice que su valor es nil.

ORDEN CRONOLÓGICO

Las listas tienen un orden para la inspección de sus elementos, que va del primer elemento al último. Es decir,
para acceder al elemento i-ésimo de la lista es necesario haber pasado por los i-1 elementos anteriores. Este orden
está dado por los punteros de cada elemento, donde cada uno apunta al elemento que le sigue en la secuencia. Para
ello se cuenta con un acceso inicial que apunta al primer elemento de la lista. En caso de que la lista se encuentre
vacía, no habrá primer elemento y el acceso apuntará a nil.

No hay un orden cronológico ni para la entrada (inserción) de elementos ni para la salida (supresión) de los

mismos. Es decir, los elementos pueden insertarse y suprimirse en cualquier orden.

CAPACIDAD

La capacidad teórica de las listas unidireccionales es dinámica, es decir que crece con las inserciones y

disminuye con las supresiones.

OPERACIONES

Se pueden realizar las operaciones de:

Inserción de un elemento, en cualquier lugar de la estructura.

Supresión de cualquier elemento que se encuentre en la estructura.

Inspección de cualquier elemento que se encuentre en la estructura.

Dado que las listas son estructuras dinámicas, es necesario además contar con dos predicados lógicos para

controlar el desborde y el desfonde de la estructura.

En todos los casos, el acceso es secuencial, es decir del primero al último elemento. Quiere decir que, por
ejemplo, para acceder (inspeccionar) el quinto elemento, a partir del primero, debe pasarse por los cuatro elementos
anteriores. Esto suponiendo que la lista tenga al menos cinco elementos.

Las listas unidireccionales tienen asociado un cursor que permite marcar, señalar, un elemento. Este elemento,
señalado o apuntado por el cursor, será llamado el elemento corriente; es el elemento sobre el cual se puede operar,
es decir que puede inspeccionarse, suprimirse, o donde, entre él y el anterior, podrá insertarse un nuevo elemento.

Para mover el cursor dentro de la lista, será necesaria, además, una operación para avanzar el cursor de a una

U.N.S.L. Argentina

89

Departamento de Informática

A. Dasso, A. Funes -

Introducción a la Programación -

Notas de Clase

Listas

posición, y otra para colocarlo en la primera posición de la lista.

Un cursor es básicamente un puntero externo a la lista que toma un valor de puntero, es decir, apunta a un

elemento de la lista o inclusive a nil. Podemos decir que el cursor de una lista es el selector implícito de la misma.

REPRESENTACIÓN GRÁFICA

La lista de la Figura 9.1 está representada gráficamente de izquierda a derecha. Los nodos marcados como
primer elemento y último elemento se corresponden con el orden de acceso o inspección de los elementos de la lista,
considerado desde el acceso a la misma.

Por supuesto, la representación gráfica puede hacerse como se desee, verticalmente en el papel, con el primero

arriba o abajo; horizontalmente en el papel, con el primero a la derecha o a la izquierda; o inclusive oblicuamente.

primer
elemento

VIPD



cursor



último
elemento

Z

Y

T

R

E



acceso

puntero al siguiente elemento


Figura 9.1 Una lista de caracteres.


nil



9.2 LISTAS BIDIRECCIONALES

COMPOSICIÓN DE LOS ELEMENTOS

Los elementos o nodos de una lista bidireccional constan de tres partes:

La Variable de Información Propiamente Dicha (VIPD), que es donde se almacena la información que
corresponde a cada elemento de la lista. Las VIPDs de una lista son todas del mismo tipo, aun cuando, obviamente,
puedan no tener necesariamente el mismo valor.

El Puntero al elemento siguiente; este puede apuntar a nil cuando no hay un elemento al que apuntar (caso del

último elemento). Este puntero se conoce también como puntero adelante o en inglés forward pointer.

El Puntero al elemento anterior, este puede apuntar a nil cuando no hay un elemento al que apuntar (caso del

primer elemento). Este puntero se conoce también como puntero atrás o en Inglés backward pointer.

Recordemos que, como ya dijimos para las listas unidireccionales, cuando un puntero no apunta a un elemento se

dice que su valor es nil.

ORDEN CRONOLÓGICO

En las listas bidireccionales, al igual que en las unidireccionales, existe un orden de inspección secuencial de los
elementos; sin embargo, en las bidireccionales, como su nombre lo indica, no solo va del primer elemento al último
sino también del último al primero. Este orden está dado por los punteros de cada nodo de la lista, los que apuntan
uno al elemento anterior y el otro al siguiente.

U.N.S.L. Argentina

90

Departamento de Informática

A. Dasso, A. Funes -

Introducción a la Programación -

Notas de Clase

Listas

Igual que en el caso de las listas unidireccionales, se cuenta con un acceso a la lista que apunta a un elemento de
la lista. Es por ello que se puede reconocer un elemento como el primero: es aquel que es apuntado por el acceso a la
lista. Cuando la lista se encuentra vacía el acceso apunta a nil.

No hay un orden cronológico ni para la entrada (inserción) de elementos ni para la salida (supresión) de los

mismos.

CAPACIDAD

La capacidad teórica de las listas bidireccionales es dinámica, crece y disminuye con las inserciones y

supresiones, respectivamente.

OPERACIONES

Se pueden realizar las operaciones de:

Inserción de un elemento, en cualquier lugar de la estructura.

Supresión de cualquier elemento que se encuentre en la estructura.

Inspección de cualquier elemento que se encuentre en la estructura.

Dado que las listas son estructuras dinámicas, es necesario además contar dos con predicados lógicos para

controlar el desborde y el desfonde de la estructura.

En todos los casos, el acceso es secuencial, es decir del primero al último y/o del último al primero. Quiere decir
que, por ejemplo, para acceder (inspeccionar) al octavo elemento, a partir del primero, deberá pasarse por los siete
elementos anteriores. Para ir al cuarto elemento, a partir del último, deberá pasarse por todos los elementos de la
lista que estén entre el último y el cuarto elemento; por ejemplo, suponiendo que la lista tiene ocho elementos,
significa que habrá que pasar por los elementos octavo, séptimo, sexto y quinto.

Las listas bidireccionales tienen asociado un cursor que permite marcar, señalar, apuntar un elemento. Este
elemento, así apuntado o señalado, será el elemento corriente, aquel que puede inspeccionarse, suprimirse, o donde,
entre el anterior y el corriente, podrá insertarse uno nuevo. En consecuencia, para poder operar sobre un elemento es
necesario que el cursor se encuentre apuntándolo, es decir, que sea el elemento corriente. Si el cursor se encuentra
apuntando a otro elemento, habrá que moverlo hacia delante o hacia atrás de acuerdo a dónde se lo quiera llevar.
Consecuentemente, serán necesarias dos operaciones: una para avanzar el cursor hacia adelante de a una posición
y otra para volverlo una posición hacia atrás. Asimismo, será necesaria otra operación para colocarlo en la primera
posición de la lista, cuando sea necesario.

Un cursor es básicamente un puntero a la lista, que toma un valor puntero lo que le permite apuntar a un
elemento de la lista, o inclusive a nil en situaciones tales como: cuando la lista se encuentra vacía, cuando el cursor
se encuentra apuntando fuera de la lista ya sea después del último en las listas uni y bidireccionales o cuando se lo
ha hecho retroceder ‘después’ del primero en las listas bidireccionales. Para estas situaciones existe un predicado
isOOS (is Out of Structure) que devolverá verdadero de encontrarse el cursor con el valor nil y falso en todos los
otros casos.

Podemos decir que el cursor de una lista es el selector implícito de la misma.

REPRESENTACIÓN GRÁFICA

La lista bidireccional de la Figura 9.2 está representada gráficamente de izquierda a derecha. Los elementos
marcados como primer elemento y último elemento corresponden al orden de los elementos en la lista considerando

U.N.S.L. Argentina

91

Departamento de Informática

A. Dasso, A. Funes -

Introducción a la Programación -

Notas de Clase

Listas

el orden de inspección de los mismos desde el acceso a la misma.

Por supuesto, la representación gráfica puede hacerse como se desee, verticalmente en el papel, con el primero

arriba o abajo; horizontalmente en el papel, con el primero a la derecha o a la izquierda; o inclusive oblicuamente.



nil

primer
elemento

cursor



puntero al

elemento anterior

último
elemento

Z

Y

T

R

E



acceso

puntero al

siguiente elemento

VIPD



Figura 9.2. Una lista bidireccional de caracteres

nil



9.3 GENERALIDAD DE LAS LISTAS

Las listas, uni y bidireccionales, son estructuras de datos, que por las escasas restricciones impuestas a las
mismas, frente a las otras estructuras, permiten emplearlas fácilmente