La estructura Lista

El TDA Lista

La Lista es una estructura de datos muy importante en los lenguajes de programación donde:

• representa una colección de elementos ordenados.
• puede contener elementos repetidos.
• cada elemento de la lista tiene un índice que lo ubica dentro de la misma.

Operaciones

En general las listas proveen las siguientes operaciones:

• construir una lista
• obtener el tamaño de la lista
• verificar si está vacía
• obtener el primer elemento de la lista, usualmente llamado head o cabeza
• agregar un nuevo elemento a la lista.
• obtener el elemento para un índice dado.
• etc

Acá vemos un ejemplo en seudo código:

tipo abstracto Lista<T>

operacion crearLista() -> Lista

operacion tamanio(Lista lista) -> int

operacion vacia(Lista lista) -> boolean

operacion cabeza(Lista<T> lista) -> T

operacion agregar(Lista<T> lista, T elemento)

operacion elementoEn(Lista<T> lista, int indice) -> T

operacion removerElementEn(Lista lista, int indice)

Lista Enlazada

Una implementación muy común de lista es la llamada lista enlazada, en donde se representa internamente como Nodos que referencian al siguiente.

Así la lista

• tiene una referencia al primer nodo (salvo que esté vacía)
• Cada Nodo tiene:
• el dato en esa posición
• una referencia al siguiente nodo

Agregar un elemento (al final)

En la lista enlazada, agregar un elemento es fácil, o poco costoso en términos de alocación de memoria. Símplemente debemos alocar espacio para un nuevo nodo, y actualizar el ultimo nodo, para que apunte al nuevo, como "siguiente".

Por el contrario en una lista basada en array (que vamos a ver más adelante), agregar un elemento que involucre redimensionar el array podría ser costoso a nivel de memoria, si no imposible.

Como para agregar un elemento es necesario primero ubicar el último nodo, es necesario recorrer todos los nodos hasta llegar al final. Esto hace que sea una operación con complejidad lineal O(n), ya que cuantos más elementos tengamos en la lista, más tiempo va a demorar.

Por esto es que en general se implementa una variante, donde la lista además de conocer al primer elemento, conoce al último. Esto cambia la complejidad a orden constante O(1).

Agregar un elemento (en el medio)

Esta operación requiere la misma cantidad de memoria, es decir un nuevo nodo. Por otro lado es también muy simple a nivel de operaciones. Lo que debemos hacer es posicionarnos en el nodo anterior y "meter" el nuevo nodo, actualizando las referencias del anterior al nuevo, y del nuevo al que previamente era el siguiente.

Remoción de un elemento

Al igual que el agregar, el remover un item es también simple en términos operativos. Se libera el nodo, pero primero se "atan" entre sí los nodos anterior y siguiente.

No se requiere re-ordenar o re-alocar memoria

Problemas o desventajas

La lista enlazada tiene las siguientes desventajas:

• Acceso aleatorio: por ejemplo, si necesitamos acceder a una posición específica, digamos el item con índide 23, la estructura no posee una forma de acceder directamente a este elemento, por lo cual debe ir recorriendo todos los nodos hasta llegar al 23.
• Localidad: la localidad espacial en memoria es "mala", ya que los nodos pueden estar dispersos y "alejados" en la memoria.
• Recorrido reverso: por consecuencia del hecho de que el acceso aleatorio es "malo", también sucederá que si en mi programa necesito recorrer la lista en sentido contrario, esto va a ser muy ineficiente. Porque por cada elemento va a recorrer los nodos.

Lista Doblemente Enlazada

Para resolver el tercer problema mencionado anteriormente, el del recorrido inverso/reverso, existe una variante a la lista enlazada simple, llamada lista doblemente enlazada. La idea es que cada nodo, además de conocer al siguiente, conozca al anterior.

Es un poco más costoso a nivel de complejidad de código, porque ahora vamos a tener que mantener un puntero más, y en cada operación como agregar, eliminar, etc.. deberemos actualizarlo. Y por otro lado, también requerirá más memoria (un puntero más). Pero hará más rápido el recorrido inverso (pasamos de complejidad sum(0..N) a O(n))

Lista Circular

Otra variante de lista enlazada es aquella en la que el último elemento conoce al primero (y viceversa si es además, doblemente enlazada). De ahí su nombre "circular", ya que se puede representar como un círculo de nodos. Obviamente esta lista no tiene fin.

Lista basada en Array

Esta implementación sí que es bastante diferente a la enlazada (a diferencia de la doblemente enlazada y la circular). Junto a la enlazada, son las dos implementaciones más comunes en los lenguajes de programación.

La idea es bien simple:

• Tendremos un tipo Lista (struct en C, clase en Python)
• Este almacenará los datos internamente como un array.
  • En C tendremos un puntero

Agregar un elemento

Adicionar un elemento a la lista de tipo array tiene varios problemas:

• Por un lado es costoso a nivel de memoria, ya que debemos hacer crecer el array una posición, pidiendo memoria = cantidadActual + 1
• Por otro lado también podría ser costoso a nivel de tiempo, porque se deben copiar los elementos a la nueva posición (en caso de realocación)

Como ya vimos, a veces el sistema operativo no nos puede dar la posición siguiente de memoria, por lo que tiene que buscar otro sector de memoria que tenga la nueva capacidad, y luego copiar todos los elementos. Por lo cual, en estos casos necesitaremos memoria = N + (N + 1) que es igual a 2N + 1

Remover un elemento

Esta operación también es costosa. Ya que no podemos simplemente "nullear" la posición donde está el elemento a eliminar, porque tendríamos los índices corridos, y porque tendríamos fragmentación. Necesitamos re-ordenar todos los elementos, corriéndolos a la izquierda.

Por ejemplo, si en para la lista anterior nos puden borrar la "E". Acá podemos ver los pasos:

Acceso aleatorio (lista[i])

Por otro lado, por el contrario a las listas enlazadas, el acceder a un elemento arbitrario, es decir en la posición "i", es mucho más simple, ya que justamente tenemos todos los elementos contiguos (localidad), con lo cual podemos "indexar", a través de aritmética de punteros (o bien la notación de arrays).

Esta operación tiene orden de complejidad constante O(1), y es la principal ventaja de la lista basada en array.

Análisis Lista Enlazada vs Lista c/Array

Comparemos algunas operaciones y sus costos tanto en la lista enlazada como en la implementación basada en array.

En conclusión podemos decir que uno tiende a utilizar:

• Lista enlazada: para representar datos que van creciendo contínuamente, o se va a eliminar elementos también frecuentemente.