miércoles, 6 de abril de 2011

"LISTAS"

Definición   
Una lista es una estructura de datos secuencial.
Una manera de clasificarlas es por la forma de acceder al siguiente elemento:
- lista densa: la propia estructura determina cuál es el siguiente elemento de la lista. Ejemplo: un array.
- lista enlazada: la posición del siguiente elemento de la estructura la determina el elemento actual. Es necesario almacenar al menos la posición de memoria del primer elemento. Además es dinámica, es decir, su tamaño cambia durante la ejecución del programa.
Una lista enlazada se puede definir recursivamente de la siguiente manera:
- una lista enlazada es una estructura vacía o
- un elemento de información y un enlace hacia una lista (un nodo).
Gráficamente se suele representar así:

Listas ordenadas


Listas reorganizables
Las listas reorganizables son aquellas en las que cada vez que se accede a un elemento éste se coloca al comienzo de la lista. Si el elemento al que se accede no está en la lista entonces se añade al comienzo de la misma. Cuando se trata de borrar un elemento se procede de la misma manera que en la operación de borrado de la lista ordenada. Notar que el orden en una lista reorganizable depende del acceso a un elemento, y no de los valores de las claves.
No se va a desarrollar el procedimiento de inserción / acceso en una lista, se deja como ejercicio. De todas formas es sencillo. Primero se busca ese elemento, si existe se pone al comienzo de la lista, con cuidado de no perder los enlaces entre el elemento anterior y el siguiente. Y si no existe pues se añade al principio y ya está. Por último se actualiza la cabecera.

Listas doblemente enlazadas
Son listas que tienen un enlace con el elemento siguiente y con el anterior. Una ventaja que tienen es que pueden recorrerse en ambos sentidos, ya sea para efectuar una operación con cada elemento o para insertar/actualizar y borrar. La otra ventaja es que las búsquedas son algo más rápidas puesto que no hace falta hacer referencia al elemento anterior. Su inconveniente es que ocupan más memoria por nodo que una lista simple.
Se realizará una implementación de lista ordenada con doble enlace que aproveche el uso de la cabecera y el centinela. A continuación se muestra un gráfico que muestra una lista doblemente enlazada con cabecera y centinela, para lo que se utiliza un único nodo que haga las veces de cabecera y centinela.

Listas circulares
Las listas circulares son aquellas en las que el último elemento tiene un enlace con el primero. Su uso suele estar relacionado con las colas, y por tanto su desarrollo se realizará en el tema de colas. Por supuesto, se invita al lector a desarrollarlo por su cuenta.





Las listas ordenadas sirven también para presentar información, en diversos elementos o items, con la particularidad que éstos estarán predecidos de un número o una letra para enumerarlos, siempre por un orden.