Listas

LISTAS es una de las estructuras de datos fundamentales, y puede ser usada para implementar otras estructuras de datos. Consiste en una secuencia de nodos, en los que se guardan campos de datos arbitrarios y una o dos referencias (punteros) al nodo anterior o posterior. El principal beneficio de las listas enlazadas respecto a los array convencionales es que el orden de los elementos enlazados puede ser diferente al orden de almacenamiento en la memoria o el disco, permitiendo que el orden de recorrido de la lista sea diferente al de almacenamiento.



Operaciones en Listas Enlazadas
________________________________________
Las operaciones que podemos realizar sobre una lista enlazada son las siguientes:
• Recorrido. Esta operación consiste en visitar cada uno de los nodos que forman la lista . Para recorrer todos los nodos de la lista, se comienza con el primero, se toma el valor del campo liga para avanzar al segundo nodo, el campo liga de este nodo nos dará la dirección del tercer nodo, y así sucesivamente.
• Inserción. Esta operación consiste en agregar un nuevo nodo a la lista. Para esta operación se pueden considerar tres casos:
o Insertar un nodo al inicio.
o Insertar un nodo antes o después de cierto nodo.
o Insertar un nodo al final.
• Borrado. La operación de borrado consiste en quitar un nodo de la lista, redefiniendo las ligas que correspondan. Se pueden presentar cuatro casos:
o Eliminar el primer nodo.
o Eliminar el último nodo.
o Eliminar un nodo con cierta información.
o Eliminar el nodo anterior o posterior al nodo cierta con información.
• Búsqueda. Esta operación consiste en visitar cada uno de los nodos, tomando al campo liga como puntero al siguiente nodo a visitar.




Tipos de Listas Enlazadas
Listas enlazadas lineales
Listas simples enlazadas
La lista enlazada básica es la lista enlazada simple la cual tiene un enlace por nodo. Este enlace apunta al siguiente nodo en la lista, o al valor NULL o a la lista vacía, si es el último nodo.

Una lista enlazada simple contiene dos valores: el valor actual del nodo y un enlace al siguiente nodo
Lista Doblemente Enlazada
Un tipo de lista enlazada más sofisticado es la lista doblemente enlazada o lista enlazadas de dos vías. Cada nodo tiene dos enlaces: uno apunta al nodo anterior, o apunta al valor NULL si es el primer nodo; y otro que apunta al nodo siguiente, o apunta al valor NULL si es el último nodo.

Una lista doblemente enlazada contiene tres valores: el valor, el link al nodo siguiente, y el link al anterior
En algún lenguaje de muy bajo nivel, XOR-Linking ofrece una vía para implementar listas doblemente enlazadas, usando una sola palabra para ambos enlaces, aunque el uso de esta técnica no se suele utilizar.
Listas enlazadas circulares
En una lista enlazada circular, el primer y el último nodo están unidos juntos. Esto se puede hacer tanto para listas enlazadas simples como para las doblemente enlazadas. Para recorrer una lista enlazada circular podemos empezar por cualquier nodo y seguir la lista en cualquier dirección hasta que se regrese hasta el nodo original. Desde otro punto de vista, las listas enlazadas circulares pueden ser vistas como listas sin comienzo ni fin. Este tipo de listas es el más usado para dirigir buffers para “ingerir” datos, y para visitar todos los nodos de una lista a partir de uno dado.

Una lista enlazada circular que contiene tres valores enteros
Listas enlazadas circulares simples
Cada nodo tiene un enlace, similar al de las listas enlazadas simples, excepto que el siguiente nodo del último apunta al primero. Como en una lista enlazada simple, los nuevos nodos pueden ser solo eficientemente insertados después de uno que ya tengamos referenciado. Por esta razón, es usual quedarse con una referencia solamente al último elemento en una lista enlazada circular simple, esto nos permite rápidas inserciones al principio, y también permite accesos al primer nodo desde el puntero del último nodo. 1
Lista Enlazada Doblemente Circular
En una lista enlazada doblemente circular, cada nodo tiene dos enlaces, similares a los de la lista doblemente enlazada, excepto que el enlace anterior del primer nodo apunta al último y el enlace siguiente del último nodo, apunta al primero. Como en una lista doblemente enlazada, las inserciones y eliminaciones pueden ser hechas desde cualquier punto con acceso a algún nodo cercano. Aunque estructuralmente una lista circular doblemente enlazada no tiene ni principio ni fin, un puntero de acceso externo puede establecer el nodo apuntado que está en la cabeza o al nodo cola, y así mantener el orden tan bien como en una lista doblemente enlazada.

Torreas de hanoi : un claro ejemplo de recusividad en c#

Aplicaciones de la recursividad

El proceso de llamadas recursivas siempre tiene que acabar en una llamada a la función que se resuelve de manera directa, sin necesidad de invocar de nuevo la función. Esto será siempre necesario, para que llegue un momento que se corten las llamadas reiterativas a la función y no se entre en un bucle infinito de invocaciones.

Quizás en la teoría cueste más ver lo que es una función recursiva que por la práctica. Un ejemplo típico de recursividad sería la función factorial. El factorial es una función matemática que se resuelve multiplicando ese número por todos los números naturales que hay entre él y 1.

Por ejemplo, factorial de 4 es igual a 4 * 3 * 2 * 1. Si nos fijamos, para el ejemplo de factorial de 4 (factorial se expresa matemáticamente con un signo de admiración hacia abajo, como 4!), se puede resolver como 4 * 3! (4 * factorial de 3). Es decir, podemos calcular el factorial de un número multiplicando ese número por factorial de ese número menos 1.

n! = n * (n-1)!


Existen muchas funciones matemáticas cuyos argumentos son números naturales, que pueden definirse de manera recursiva. Esto quiere decir que el valor de la función para el argumento n puede definirse en términos del argumento n-1 (o alguno anterior). En este tipo de definiciones siempre existirá un caso base a partir del cual parte la definición, el cual normalmente es el valor de la función en cero o en uno, aunque no necesariamente debe ser así.

Usualmente los lenguajes de programación permiten definir funciones de manera recursiva. El lenguaje C es uno de ellos. La definición recursiva para el factorial sería:

int factorial(int n) {
if ((n == 0) || (n == 1))
return(1);
else
return(n*factorial(n-1));
}

Normalmente las definiciones recursivas pueden expresarse en forma no recursiva. Sin embargo, dependiendo del caso, el resultado puede ser más confuso. Por ejemplo, una función en C que calcula el factorial en forma iterativa sería:

int factorial(int n) {
int i, fact = 1;

for (i=2; i<=n; i++)
fact = fact * i;
return(fact);
}

Video