Ventajas y desventajas de las listas enlazadas respecto a los arrays

Bueno, después de haber visto las listas enlazadas no debemos pensar que son siempre mejores que los arrays, depende para que los vayamos a utilizar.

Ventajas de las listas enlazadas respecto a los arrays

1. Tamaño dinámico. Lo que implica optimización de la memoria.

Desventajas de las listas enlazadas respecto a los arrays

1. El acceso es secuencial (para llegar a una posición deberemos pasar por todas las anteriores). Esto significa lentitud. Imaginad por un momento el tinglado que tendríamos que montar para ordenar una lista enlazada. Si buscamos un elemento de una lista ordenada también tardaremos más, no vale la búsqueda dicotómica que vimos en la Ampliación 1 de C (métodos de clasificación en memoria dinámica).
2. El código se complica.

Eliminación de un elemento cualquiera de una lista enlazada

Este caso es parecido al anterior, sólo se diferencia en que en vez de hacer que el elemento anterior al que eliminamos apunte a NULL deberemos hacer que apunte al elemento apuntado por el elemento que eliminamos. Ahora lo vemos con el dibujo (perdonad mi poca gracia dibujando). Supongamos que queremos borrar el segundo elemento.

1. El primer paso es buscar el elemento a borrar que será apuntado por aux y el elemento anterior será apuntado por ant.
2. ant -> siguiente cogerá el valor de aux -> siguiente.
3. Liberamos aux.

Eliminar un elemento de una lista enlazada

Este es un punto en el que pido concentración para no perdernos, si se imagina la situación es algo que resulta muy sencillo. Veremos las diferentes situaciones que nos podemos encontrar a la hora de eliminar un elemento de una lista enlazada, además si se entiende podréis utilizar las mismas explicaciones para insertar un elemento en la lista enlazada en diferentes zonas.

Nos podemos encontrar con 3 casos: que el elemento sea el primero de la lista, que sea el último o que esté entre medio. Usaremos el puntero “ primero ” que apunta al primer elemento de la lista, el puntero “ aux ” que será auxiliar y el puntero “ ant ” que será el anterior. No necesitaremos los 3 siempre. Analizamos los 3 casos paso a paso pero el código os lo dejo a vosotros.

Suprimir por cabeza

1. Necesitaremos 2 punteros. Se trata de eliminar el primer elemento pero si lo eliminamos directamente la lista quedará perdida en la memoria (no sabremos donde comienza). Así que haremos que guardaremos la posición del primer elemento en aux.
2. Después haremos que primero apunte a primero -> siguiente. O sea, que el nuevo primer elemento será el segundo (claro, si eliminamos al primero…).
3. Por último ya podemos liberar aux.

Suprimir por el final

1. Hay que encontrar el último nodo y eliminarlo pero también tendremos que buscar el penúltimo para hacer que apunte a NULL. Tendremos que recorrer toda la lista con aux y utilizar ant para que apunte al elemento anterior a aux.
2. Eliminamos el último nodo (aux) y hacemos que ant apunte a NULL.

Lista Enlazada

Una lista enlazada tiene un conjunto de nodos, los cuales almacenan 2 tipos de información: El dato que contienen y un puntero al siguiente nodo en la lista. El último nodo de la lista tiene como siguiente nodo el valor NULL. Entonces las listas enlazadas simples solo pueden ser recorridas en una dirección, apuntando al nodo siguiente, mas no a un nodo anterior.

Aquí tenemos un ejemplo de un lista enlazada simple.

55-> 60-> 31-> 5-> 4-> 51-> 9-> 27-> 68-> 62-> NULL

Internamente:

Nodo-> Dato: 55 Direcion: 0x3d2c00 Siguiente: 0x3d2c80

Nodo-> Dato: 60 Direcion: 0x3d2c80 Siguiente: 0x3d2c90

Nodo-> Dato: 31 Direcion: 0x3d2c90 Siguiente: 0x3d2ca0

Nodo-> Dato: 5  Direcion: 0x3d2ca0 Siguiente: 0x3d2cb0

Nodo-> Dato: 4  Direcion: 0x3d2cb0 Siguiente: 0x3d2cc0

Nodo-> Dato: 51 Direcion: 0x3d2cc0 Siguiente: 0x3d3ab8

Nodo-> Dato: 9  Direcion: 0x3d3ab8 Siguiente: 0x3d3ac8

Nodo-> Dato: 27 Direcion: 0x3d3ac8 Siguiente: 0x3d3ad8

Nodo-> Dato: 68 Direcion: 0x3d3ad8 Siguiente: 0x3d3ae8

Nodo-> Dato: 62 Direcion: 0x3d3ae8 Siguiente: 0

Como una lista es una estructura de datos dinámica, el tamaño de la misma puede cambiar durante la ejecución del programa. Obviamente, internamente no existen las palabras nodo, dato,dirección y siguiente, es solo una representación.

Tipos de listas lineales:

Listas contiguas: los elementos son adyacentes en la memoria del ordenador y tienen unos limites (izquierdo y derecho o inferior y superior) que no pueden ser rebasados cuando se añade un nuevo elemento. Se implementan a través de arrays y la inserción o eliminación de un elemento necesitará una traslación por parte de los elementos de la lista, excepto para la cabecera y el final de la lista.


Listas enlazadas: los elementos se almacenan en posiciones de memoria que no son adyacentes o contiguas, por lo que cada elemento necesita almacenar la posición del siguiente elemento de la lista. Son bastante más flexibles y potentes que las listas contiguas y la inserción o el borrado de un elemento no requiere el desplazamiento de los demás elementos de la lista. Se implementan, normalmente, de forma dinámica, pero si el lenguaje de programación no lo permite se utilizaran arrays, con lo cual tendremos limitaciones en cuanto al número de elementos que pueda contener la lista y además establece una ocupación de memoria constante.


Listas circulares: son una modificación de las listas enlazadas en las que el puntero del ultimo elemento apunta al primero de la listas.

Gráficamente se representa de la siguiente forma:



Debemos diseñar un nodo especial llamado nodo cabecera que está permanentemente asociado a la existencia de la lista y cuyo campo para almacenar información no se utiliza. Así, al efectuar un recorrido de la lista, el nodo cabecera nos permitirá detectar cuándo han sido visitados todos los demás nodos.


Listas doblemente enlazadas: Se pueden recorrer tanto del final al principio como de principio a fin. Cada nodo de las listas de este tipo consta de un campo con información y de otros dos campos que son de tipo puntero y que podríamos denominar anterior y siguiente, uno desde su nodo anterior y otro de su nodo sucesor.


Listas doblemente encadenadas circulares: en este tipo de listas el campo anterior del primer nodo apunta al ultimo nodo y el campo siguiente del ultimo nodo apunta al primero.

Combinatoria con listas

Teniendo en cuenta que una lista es un conjunto de elementos ordenados según el orden de aparición de izquierda a derecha, dentro de los ejercicios con listas podemos considerar la generación de variaciones y permutaciones a partir de los elementos de una lista; pero también podemos considerar la generación de combinaciones y un tratamiento de conjuntos donde ya la ordenación no debe tenerse en cuenta.

A partir del predicado seleccion/3 que permite seleccionar de forma aleatoria un elemento de una lista devolviendo además una lista con los restantes elementos, podemos definir predicados para generar variaciones de un determinado tamaño, y en el caso extremo de que el tamaño coincida con la longitud de la lista podemos mejorar la definición para producir permutaciones.

 Para producir las combinaciones de un cierto tamaño a partir de los elementos de una lista también podemos recurrir a la definición recursiva Para producir las combinaciones de un cierto tamaño a partir de los añadiendo un elemento a una combinación de tamaño menor, pero en este caso hay que tener en cuenta que el orden en el que aparezcan los elementos no determinar´a combinaciones distintas como ocurre con la variaciones. En de aparición de los elementos en la lista original, para ello la selección del este caso será mejor buscar una forma canónica para representar cada combinación, esta forma puede ser la lista correspondiente respetando el orden elemento no se debe dejar al predicado selección/3 sino que deberá hacerse en la cabeza de las cláusulas tomando el primer elemento de la lista o no. y completando la combinación con los elementos siguientes (y no con los anteriores).

Ordenación de listas

Teniendo en cuenta la posibilidad que ofrece la representación de listas en Prolog de acceder directamente a varios elementos del comienzo de una lista y compararlos, podemos definir un predicado ordenada/1 que determine si una lista (de números o de términos) está ordenada o no.

• El algoritmo de ordenación por inserción parte la lista en cabeza y cola, ordena la cola e inserta la cabeza en el lugar adecuado de la cola ordenada, por lo que únicamente necesita un procedimiento auxiliar para insertar elementos en listas ordenadas.

• El algoritmo de ordenación por mezcla parte la lista en dos trozos aproximadamente de igual longitud, ordena cada trozo y después los mezcla. Este algoritmo necesita dos procedimientos auxiliares: un procedimiento para separar una lista en dos aproximadamente de igual longitud y otro para mezclar listas ordenadas de forma que se obtenga una lista igualmente ordenada.

• El algoritmo de ordenación por pivote usa un elemento como pivote para partir la lista en una lista con los elementos menores o iguales que el pivote y otra con los elementos estrictamente mayores, ordena ambas listas y después las encadena los menores delante de los mayores. Este algoritmo necesita dos procedimientos: uno para separar una lista con ayuda de un pivote en dos listas una con los elementos menores o iguales que el pivote y otra con los elementos mayores, y otro procedimiento para encadenar dos listas que ya conocemos.