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.

Predicados aritméticos con listas

En este apartado nos dedicaremos a estudiar predicados que realizan cálculos num´ericos sobre listas. El más básico es el que calcula la longitud de una lista, la forma más simple de definir un predicado longitud/2 tal que longitud(L,N) calcule la longitud N de una lista L es contando los elementos de forma recursiva: primero los de la cola y después los de la lista completa. Aquí tenemos dos definiciones distintas, 

longitud1([],0).

longitud1([_|Xs],N):-longitud(Xs,M),N is M+1.

es una definici´on basada en la aritm´etica predefinida de Prolog y longitud2([],0).

longitud2([_|Xs],s(M)):-longitud(Xs,M). es una definición basada en la aritmética del sucesor definida por el usuario.

Encadenamiento y partición de listas

El encadenamiento de dos listas se puede definir en Prolog de una manera bastante simple obteniéndose un predicado encadena/3 que resulta de gran utilidad en el manejo de listas. Para la definición de este predicado basta tener en cuenta que la cabeza de la lista resultante del encadenamiento será la cabeza de la primera de las dos listas que se encadenan y que la cola resultará de encadenar la cola de la primera lista con la segunda lista completa.

Reconocimiento de patrones con listas

En este apartado vamos a ver predicados definidos sobre pares de listas que sirven para establecer relaciones como ser prefijo, sufijo o sublista de una lista. En principio, aprovechando la facilidad de acceso a las cabezas y a las colas de las lista, podemos definir un predicado para la relación prefijo basado en la coincidencia de los elementos de cabeza.

Elementos de una listas

En este apartado nos ocuparemos de la construcción de predicados que sirven para comprobar si un elemento pertenece o no a una lista o si se encuentra en determinada posición dentro de una lista y veremos que algunos presentan comportamientos adicionales a los inicialmente esperados. Para expresar estos comportamientos utilizaremos los términos siguientes: test cuando el comportamiento sea comprobar si se cumple una determinada relación, generador ´unico cuando genere un valor ´unico que verifique la relación, generador acotado cuando genere un número finito de valores, generador infinito cuando genere valores de manera continuada y anómalo
cuando no produzca resultado.

Dominios para listas

Como hemos dicho en el apartado anterior, Prolog es capaz de distinguir las listas de cualquier otra clase de términos, pero esta distinción la hace a nivel interno para detectar errores de notación durante el proceso de

unificación. Si en alg´un programa queremos saber si un t´ermino T es una lista (no vacía) podemos intentar unificarlo con una expresión de la forma [X|Xs] usando el predicado de unificaci´on expl´ıcita ‘.=.’, o podemos definir un predicado recursivo lista/1 en la forma:

lista([]).

lista([X|Xs]):-lista(Xs).

Este predicado es lo m´as parecido a una definici´on del tipo lista que se puede hacer en Prolog y sirve para comprobar si un t´ermino es una lista cuando se lo proporciona un argumento conocido, pero también sirve para generar, por re evaluación, listas cuyas componentes son variables libres.

Recursividad

Recurrencia, recursión o recursividad es la forma en la cual se especifica un proceso basado en su propia definición. Siendo un poco más precisos, y para evitar el aparente circulo sin fin en esta definición:

Un problema que pueda ser definido en función de su tamaño, sea este N, pueda ser dividido en instancias más pequeñas (< N) del mismo problema y se conozca la solución explícita a las instancias más simples, lo que se conoce como casos base, se puede aplicar inducción sobre las llamadas más pequeñas y suponer que estas quedan resueltas.

Para que se entienda mejor a continuación se exponen algunos ejemplos:

1. Factorial(x: Entero): Sea N := x el tamaño del problema, podemos definir el problema de forma recurrente como x*Factorial(x - 1); como el tamaño de Factorial(x - 1) es menor que N podemos aplicar inducción por lo que disponemos del resultado. El caso base es el Factorial(0) que es 1.
2. • Ordenación por fusión(v: vector): Sea N := tamaño(v), podemos separar el vector en dos mitades. Estas dos mitades tienen tamaño N/2 por lo que por inducción podemos aplicar la ordenación en estos dos subproblemas. Una vez tenemos ambas mitades ordenadas simplemente debemos fusionarlas. El caso base es ordenar un vector de 0 elementos, que está trivialmente ordenado y no hay que hacer nada. 
   En estos ejemplos podemos observar como un problema se divide en varias (>= 1) instancias del mismo problema, pero de tamaño menor gracias a lo cual se puede aplicar inducción, llegando a un punto donde se conoce el resultado (el caso base)..

¿Que es Prolog?

Prolog es un propósito general la lógica de programación de lenguaje asociados a la inteligencia artificial y lingüística computacional. Prolog tiene sus raíces en la lógica de primer orden, una lógica formal, ya diferencia de muchos otros lenguajes de programación Prolog es declarativa: la lógica del programa se expresa en términos de relaciones, representado como los hechos y las normas. El cálculo se inicia mediante la ejecución de una consulta sobre estas relaciones. El lenguaje fue concebida por un grupo de alrededor de Alain Colmerauer en Marsella, Francia, a principios de 1970 y el sistema Prolog primero fue desarrollado en 1972 por Colmerauer con Philippe Roussel.

Prolog fue uno de los primeros lenguajes de programación lógica y sigue siendo uno de los lenguajes más populares hoy en día, con muchas implementaciones disponibles libres y comerciales. Aunque en un principio destinado a procesamiento del lenguaje natural, la lengua se ha extendido mucho desde entonces en otras áreas como la demostración de teoremas, los sistemas expertos, juegos, sistemas automatizados de respuesta, las ontologías y sofisticados sistemas de control. Ambientes modernos Prolog apoyar la creación de interfaces gráficas de usuario, así como las aplicaciones administrativas y en red.

¿Que es Lista en Programación?

En Prolog la estructura de lista está predefinida como una estructura re cursiva lineal cuyas componentes pueden ser heterogéneas porque en Prolog e no existe una comprobación tipos. Básicamente una lista es una estructura o a con dos argumentos: la cabeza de la lista, que es un componente de la lista, y la cola que es otra lista con el resto de los componentes. Normalmente existen dos notaciones para listas, una notación prefija: .(Cabeza,Cola) y o una notación infija [Cabeza|Cola] más cómoda de utilizar, y para denotar o a o la lista base se utiliza siempre []. Así la lista (a,b,c,d) se puede escribir ıa ı, en Prolog de cualquiera de las dos formas siguientes: .(a,.(b,.(c,.(d.[])))) [a|[b|[c|[d|[]]]]]. Sin embargo, la segunda forma admite simplificaciones que permiten escribir todos los elementos de la lista entre corchetes y separados por comas: [a,b,c,d], o escribir varios elementos a la izquierda del símbolo |, también separados e por comas, así como cualquier combinación de estas dos formas; con lo que ı o nuestra lista se puede escribir de cualquiera de las formas siguientes: [a|[b,c,d]] [a,b|[c,d]] [a,b,c|[d]] [a,b,c,d|[]] .

Es importante observar que en las dos notaciones para listas, el segundo argumento debe ser siempre una lista, pues aunque como hemos dicho Prolog no comprueba tipos, si es capaz de distinguir las listas de otra clase de ı términos. Así notaciones como las siguientes e ı, .(a,b) [a|b]

¿Que es Programación?

La programación es el proceso de diseñar, escribir, probar, depurar y mantener el código de fuente de programas computacionales. El código fuente es escrito en un lenguaje de programación. El propósito de la programación es crear programas que exhiban un comportamiento deseado. El proceso de escribir código requiere frecuentemente conocimientos en varias áreas distintas, además del dominio del lenguaje a utilizar, algoritmos especializados y lógica formal. Programar no involucra necesariamente otras tareas tales como el análisis y diseño de la aplicación (pero si el diseño del código), aunque si suelen estar fusionadas en el desarrollo de pequeñas aplicaciones.