LISTAS CIRCULARES

listas circulares

concepto:
Una lista circular es una lista lineal en la que el último nodo a punta al primero.
Las listas circulares evitan excepciones en la operaciones que se realicen sobre ellas. No existen casos especiales, cada nodo siempre tiene uno anterior y uno siguiente.
En algunas listas circulares se añade un nodo especial de cabecera, de ese modo se evita la única excepción posible, la de que la lista esté vacía.


concepto:
En una lista enlazada circular, el primer y el último nodo estánunidos juntos. Esto se puede hacer tanto para listas enlazadas simplescomo para las doblemente enlazadas. Para recorrer un lista enlazadacircular podemos empezar por cualquier nodo y seguir la lista encualquier dirección hasta que se regrese hasta el nodo original. Desdeotro punto de vista, las listas enlazadas circulares pueden ser vistascomo listas sin comienzo ni fin. Este tipo de listas es el más usadopara dirigir buffers para “ingerir” datos, y para visitar todos losnodos de una lista a partir de uno dado.

TIPOS DE LISTAS CIRCULARES:

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 unalista enlazada simple, los nuevos nodos pueden ser solo eficientementeinsertados después de uno que ya tengamos referenciado. Por esta razón,es usual quedarse con una referencia solamente al último elemento enuna lista enlazada circular simple, esto nos permite rápidasinserciones al principio, y también permite accesos al primer nododesde el puntero del último nodo.

Lista Enlazada Doblemente Circular 

En una lista enlazada doblemente circular, cada nodo tienedos enlaces, similares a los de la lista doblemente enlazada, exceptoque el enlace anterior del primer nodo apunta al último y el enlacesiguiente del último nodo, apunta al primero. Como en una listadoblemente enlazada, las inserciones y eliminaciones pueden ser hechasdesde cualquier punto con acceso a algún nodo cercano. Aunqueestructuralmente una lista circular doblemente enlazada no tiene niprincipio ni fin, un puntero de acceso externo puede establecer el nodoapuntado que está en la cabeza o al nodo cola, y así mantener el ordentan bien como en una lista doblemente enlazada.


BUSCAR O LOCALIZAR UN ELEMENTO DE UNA LISTA CIRCULAR: A la hora de buscar elementos en una lista circularsólo hay que tener una precaución, es necesario almacenar el puntero del nodoen que se empezó la búsqueda, para poder detectar el caso en que no exista elvalor que se busca. Por lo demás, la búsqueda es igual que en el caso de laslistas abiertas, salvo que podemos empezar en cualquier punto de la lista.
ELIMINAR UN NODO EN UNA LISTA CIRCULAR CON MÁS DE UN ELEMENTO:
Es el caso más simple. Partiremos de una lista con uno o más nodos, y usaremos un puntero auxiliar, nodo:

1. Hacemos que nodo apunte al primer elemento de la lista, es decir a Lista.
2. Asignamos a Lista la dirección del segundo nodo de la lista: Lista->siguiente.
3. Liberamos la memoria asignada al primer nodo, el que queremos eliminar.

Si no guardamos el puntero al primer nodo antes de actualizar Lista, después nos resultaría imposible liberar la memoria que ocupa. Si liberamos la memoria antes de actualizar Lista, perderemos el puntero al segundo nodo.
                             
Si la lista sólo tiene un nodo, el proceso es también válido, ya que el valor de Lista->siguiente es NULL, y después de eliminar el primer nodo la lista quedará vacía, y el valor de Lista será NULL.
De hecho, el proceso que se suele usar para borrar listas completas es eliminar el primer nodo hasta que la lista esté vacía.

Eliminar un nodo cualquiera de una lista abierta:

En todos los demás casos, eliminar un nodo se puede hacer siempre del mismo modo. Supongamos que tenemos una lista con al menos dos elementos, y un puntero al nodo anterior al que queremos eliminar. Y un puntero auxiliar nodo.


El proceso es parecido al del caso anterior:

1. Hacemos que nodo apunte al nodo que queremos borrar.
2. Ahora, asignamos como nodo siguiente del nodo anterior, el siguiente al que queremos eliminar: anterior->siguiente = nodo->siguiente.
3. Eliminamos la memoria asociada al nodo que queremos eli minar.

Si el nodo a eliminar es el último, es procedimiento es igualmente válido, ya que anterior pasará a ser el último, y anterior->siguiente valdrá NULL.

Aplicacion

La lista circular, así como en el ejemplo donde guardamos nombre, DNI, edad y sueldo, podemos guardar mas datos y generar una lista que se valla expandiendo, lo podemos usar en un programa de Matriculas de una Institucion Educativa, Control de personal de una Empresa, y asi como muchas otras aplicaciones.

una parte del codigo del programa descrito arriba

package clistacircularse;
import javax.swing.*;
public class Formulario {

public static void main (String[] args)
{
    Lista lcse = new Lista();
    String nombre,lmenu,ldni,lnom,led,lsue;
    double suel;
    int vmenu,vdni,vedad;
    vmenu=0;
    while (vmenu!=8){
        if (vmenu == 0){
            /////////////
            lmenu = JOptionPane.showInputDialog("Menu:\n"+"1: Añadir final\n"+"2: Añadir Principio\n"+"3: Mostrar lista\n"+"4: Borrar elemento primero\n"+"5: Borrar Todo\n"+"6: Mostrar uno\n"+"7: modificar\n"+"8: salir\n");
            vmenu=Integer.parseInt(lmenu);
            //////////////
        }
        if (vmenu == 1){
            //ingresar los datos del trabajador
            JOptionPane.showMessageDialog(null,"INGRESAR DATOS DEL trabajador");
            vdni=1;
           
            while (vdni!= 0){

                 lnom = JOptionPane.showInputDialog("nombre");
                
                 while ((nombre = lnom)!= null){
                    ldni=JOptionPane.showInputDialog("DNI");
                    vdni = Integer.parseInt(ldni);
                    led = JOptionPane.showInputDialog("edad");
                    vedad = Integer.parseInt(led);
                    lsue = JOptionPane.showInputDialog("sueldo");
                    suel = Double.parseDouble(lsue);

                    if (vdni != 0)
                    {
                    lcse.añadirfinal(vdni,lnom,vedad,suel);
                    lnom=JOptionPane.showInputDialog("nombre");
                    }
                    else
                    {
                        lnom = null;
                    }
                    }

            }
            /////////////
              lmenu = JOptionPane.showInputDialog("Menu:\n"+"1: Añadir final\n"+"2: Añadir Principio\n"+"3: Mostrar lista\n"+"4: Borrar elemento primero\n"+"5: Borrar Todo\n"+"6: Mostrar uno\n"+"7: modificar\n"+"8: salir\n");
              vmenu=Integer.parseInt(lmenu);
           //////////////
        }
        if (vmenu == 2){
            //ingresar los datos de un trabajador al principio
            JOptionPane.showMessageDialog(null,"INGRESAR DATOS DEL trabajador al principio");
            lnom = JOptionPane.showInputDialog("nombre");
            ldni=JOptionPane.showInputDialog("DNI");
            vdni = Integer.parseInt(ldni);
            led = JOptionPane.showInputDialog("edad");
            vedad = Integer.parseInt(led);
            lsue = JOptionPane.showInputDialog("sueldo");
            suel = Double.parseDouble(lsue);
            lcse.añadirprincipio(vdni,lnom,vedad,suel);
            /////////////
            lmenu = JOptionPane.showInputDialog("Menu:\n"+"1: Añadir final\n"+"2: Añadir Principio\n"+"3: Mostrar lista\n"+"4: Borrar elemento primero\n"+"5: Borrar Todo\n"+"6: Mostrar uno\n"+"7: modificar\n"+"8: salir\n");
            vmenu=Integer.parseInt(lmenu);
            //////////////
        }
        if (vmenu == 3){
            //muestra los datos del trabajador
            JOptionPane.showMessageDialog(null,"lista");
            lcse.mostrar(lcse);
            /////////////
            lmenu = JOptionPane.showInputDialog("Menu:\n"+"1: Añadir final\n"+"2: Añadir Principio\n"+"3: Mostrar lista\n"+"4: Borrar elemento primero\n"+"5: Borrar Todo\n"+"6: Mostrar uno\n"+"7: modificar\n"+"8: salir\n");
            vmenu=Integer.parseInt(lmenu);
            //////////////
        }
       
        if (vmenu == 4){
            //borra el trabajador del principo
            lcse.borrar();
            /////////////
            lmenu = JOptionPane.showInputDialog("Menu:\n"+"1: Añadir final\n"+"2: Añadir Principio\n"+"3: Mostrar lista\n"+"4: Borrar elemento primero\n"+"5: Borrar Todo\n"+"6: Mostrar uno\n"+"7: modificar\n"+"8: salir\n");
            vmenu=Integer.parseInt(lmenu);
            //////////////
        }

        if (vmenu == 5){
            //borra todo
            lcse.borrartodo(lcse);
            /////////////
            lmenu = JOptionPane.showInputDialog("Menu:\n"+"1: Añadir final\n"+"2: Añadir Principio\n"+"3: Mostrar lista\n"+"4: Borrar elemento primero\n"+"5: Borrar Todo\n"+"6: Mostrar uno\n"+"7: modificar\n"+"8: salir\n");
            vmenu=Integer.parseInt(lmenu);
            //////////////
        }

        if (vmenu == 6){
            //busca un trabajador buscado por su dni
            String ldn;
            int vdn;
            ldn = JOptionPane.showInputDialog("Ingresar DNI:");
            vdn=Integer.parseInt(ldn);
            lcse.mostraruno(lcse,vdn);
            /////////////
            lmenu = JOptionPane.showInputDialog("Menu:\n"+"1: Añadir final\n"+"2: Añadir Principio\n"+"3: Mostrar lista\n"+"4: Borrar elemento primero\n"+"5: Borrar Todo\n"+"6: Mostrar uno\n"+"7: modificar\n"+"8: salir\n");
            vmenu=Integer.parseInt(lmenu);
            //////////////
        }

         if (vmenu == 7){
             //modifica los datos de un trabjador buscado por su dni
            String ldn;
            int vdn;
            ldn = JOptionPane.showInputDialog("Ingresar DNI:");
            vdn=Integer.parseInt(ldn);
            lnom = JOptionPane.showInputDialog("nombre");
             led = JOptionPane.showInputDialog("edad");
            vedad = Integer.parseInt(led);
            lsue = JOptionPane.showInputDialog("sueldo");
            suel = Double.parseDouble(lsue);
            lcse.modificar(lcse,vdn,lnom,vedad,suel);
            /////////////
            lmenu = JOptionPane.showInputDialog("Menu:\n"+"1: Añadir final\n"+"2: Añadir Principio\n"+"3: Mostrar lista\n"+"4: Borrar elemento primero\n"+"5: Borrar Todo\n"+"6: Mostrar uno\n"+"7: modificar\n"+"8: salir\n");
            vmenu=Integer.parseInt(lmenu);
            //////////////
        }

    }

}
}


bibliografia: listas circulares

wiki listas enlazadas fila A

CLASE LIST

La clase List proporciona un área desplegable que contiene ítems seleccionables (uno por línea). Generalmente, un usuario selecciona una opción pulsando sobre ella, e indica que una acción debe ocurrir cuando hace doble-click sobre ella o pulsa la tecla Return. Las Listas (Lists) pueden permitir múltiples selecciones o sólo una selección a la vez. Otros componentes que pérmiten al usuario elegir entre varias opciones son checkbox, choice, y menu.

LINKED LIST

La otra implementación es LinkedList (lista enlazada). En ésta, los elementos son mantenidos en una serie de nodos atados entre sí como eslabones de una cadena. Cada uno de estos nodos apunta a su antecesor y al elemento que le sigue. Nada más. No hay nada en cada uno de esos nodos que tenga algo que ver con la posición en la lista. Para obtener el elemento número “n”, esta implementación de List necesita entonces empezar desde el comienzo, desde el primer nodo, e ir avanzando al “siguiente” n veces. Buscar el elemento 400 entonces implica 400 de esos pasitos. La ventaja es que es posible eliminar elementos del principio de la lista y del medio de manera muy eficiente. Para eliminar un elemento solamente hay que modificar a sus dos “vecinos” para que se “conecten” entre sí ignorando al elemento que se está borrando. Como en una cadena, se retira un eslabón abriendo los eslabones adyacentes al que se eliminá y cerrándolos de modo que lo excluyan. No es necesario hacerle ningún cambio al resto de los elementos de la lista.

CLASE ARRAY LIST

Las aplicaciones frecuentemente necesitan almacenar un grupo de datos en un sólo objeto. Los arrays sirven bien para este propósito, pero algunas veces necesitamos incrementar o reducir dinámicamente el número de elementos del array, o hacer que contenga distintos tipos de datos
Esto es común entre las aplicaciones como las tiendas online. Un cliente añade una mercancía a su carro de la compra, y detrás de la escena, los ítems son almacenados y eliminados automáticamente.
Para esta clase de grupos de datos crecientes y menguantes, podemos usar la clase Vector , o la reciente clase ArrayList del paquete java.util .
Un ArrayList contiene tantos objetos como necesitemos.
ArrayList tiene varios constructores, dependiendo de cómo necesitemos construir el ArrayList . Los siguientes dos constructores nos ayudarán a empezar:
ArrayList() construye un ArrayList con capacidad cero por defecto, pero crecerá según le vayamos añadiendo:
ArrayList al = new ArrayList();
ArrayList(int initialCapacity) construye un ArrayList vacío con una capacidad inicial especificada:
ArrayList al2 = new ArrayList(5);
Un objeto ArrayList sólo contiene referencias a objetos. Para almacenar tipos primitivos como double , long , o float , usamos una clase envoltura, como se desmuestra abajo. Para añadir objetos al ArrayList , llamamos a sus métodos con el operador punto:
al.add("Java Technology Book"); //adds a String al.add(new Double(40.00)); //adds a double in a class wrapper //More about class wrappers in a future issue System.out.println(al.size()); //prints the size of //the ArrayList
Si necesitamos circular a través de los elementos del ArrayList , usamos la clase Iterator y sus métodos hasNext y next :
Iterator alIt = al.iterator(); while (alIt.hasNext()) { System.out.println(alIt.next() + " "); }
ArrayList es una de las muchas clases del Collection Framework , que proporciona un conjunto de interfaces y clases bien-diseñados para almacenar y manipular grupos de datos como una sola unidad, una coleccion.

ITERATOR

• Para recorrer un ArrayList, podemos llamar a get dado un
índice (como en los métodos anteriores).
• Podemos prescindir de los índices y usar un Iterator sobre este
ArrayList: ArrayListIterator.java
• La clase Iterator pertenece al paquete java.util
• La única función de un objeto de tipo Iterator es recorrer un
ArrayList.
• Iterator tiene como métodos hasNext (que devuelve un
boolean) y next (que devuelve un Object).
• Como StringTokenizer, un objeto de tipo Iterator es de un solo
uso.

LISTAS

concepto:

La lista enlazada es un TDA que nos permite almacenar datos de una forma organizada, al igual que los vectores pero, a diferencia de estos, esta estructura es dinámica, por lo que no tenemos que saber "a priori" los elementos que puede contener.

TIPOS DE LISTAS

conceptoListas 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.

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.

Operaciones básicas de las listas

En toda estructura de datos hay dos operaciones que sobresalen por encima del resto: Insertar y borrar. Estas dos operaciones aparecerán en toda estructura de datos, puede que con otro nombre, o con una funcionalidad ligeramente diferente, pero su filosofía será la misma, proporcionar unas operaciones para la construcción de la estructura de datos.

Insertar

La operación insertar consiste en la introducción de un nuevo elemento en la lista.
En una lista no ordenada no es necesario mantener ningún orden, por lo tanto la inserción de elementos se puede realizar en cualquier lugar de la lista, al principio, al final, en una posición aleatoria, ...
Generalmente se realiza la inserción de tal forma que la complejidad temporal sea mínima, es decir, que sea una operación sencilla para que se realice en el menor tiempo posible. La operación más sencilla depende de la implementación de la estructura de datos, en unos casos puede ser la inserción al inicio, en otros la inserción al final y en este caso la inserción la realiza en el segundo nodo de la lista.
Si tenemos la lista...

 ... e insertamos el elemento 0, la lista quedaría de la siguiente forma:

Borrar

La operación borrar consiste en la eliminación de la lista de un elemento concreto. El elemento a borrar será escogido por el programador.

La eliminación en una lista no conlleva ningún trabajo adicional más que el propio de la eliminación del elemento en sí. Para borrar un elemento cualquiera habría que realizar un recorrido secuencial de la lista hasta encontrar el nodo buscado y una vez localizado reestructurar los punteros para saltarse el nodo a borrar y así poder eliminarlo.Vamos a verlo con un ejemplo. Borrado del elemento 76 en la lista anterior:

Paso 1: Localizar el elemento a borrar.

Paso 2: Reestructurar punteros y eliminar nodo.

Otras operaciones

A partir de estas dos operaciones básicas cada lista puede presentar muchas operaciones diferentes, vamos a comentar algunas de ellas, dejando claro que las dos básicas que siempre aparecerán son las anteriores.

• Tamaño: Esta operación suele informar sobre el número de elementos que tiene en ese instante la lista.
• Buscar: Comprueba si existe un determinado elemento en la lista.
• Recorrer lista: Recorre toda la lista, realizando una operación en cada nodo. Por ejemplo, mostrar el contenido por pantalla.

bibliografia: listas tipos de listas operaciones

Recursividad vs. iteración

Aspectos que hay que considerar al decidir cómo implementar la solución a un

problema (de forma iterativa o de forma recursiva):

- La carga computacional (tiempo de CPU y espacio en memoria) asociada a

las llamadas recursivas.

- La redundancia (algunas soluciones recursivas resuelven un problema en

repetidas ocasiones).

- La complejidad de la solución (en ocasiones, la solución iterativa es muy

difícil de encontrar).

- La concisión, legibilidad y elegancia del código resultante de la solución

recursiva del problema.

Algo recursivo o recurrente es algo que se llama a si mismo. Tiene que ver con el principio de inducción.

La recursividad consume muchísima memoria, ya que mantiene las variables del método mientras que se ejecuta, y también mucho tiempo. La recursividad es costosa pero es más natural, se prefiere. Por ejemplo, Java no puede implementar de forma recursiva el cálculo del factorial de un millón, pues cualquier computador se quedaría sin memoria, sin embargo, es necesario de implementar para poder escribir y entender ciertos programas.

Recursividad vs. Iteración

1- Ambas realizan una repetición:

a)Solución iterativa repite el cuerpo del bucle.

b)Solución recursiva repite las llamadas al método recursivo.

2- Ambas tienen una condición de terminación.

a)Solución iterativa: termina cuando se imcumple la condición de continuación del bucle.

b)Solución recursiva: se termina cuando una llamada alcanza el caso base (inducción) desencadenando una secuencia de vuelta atrás.

Backtracking: sucesión de pruebas tentativas.

3- Ambas se deben diseñar para converger a la solución (principio de convergencia, y que no se salten la condición de terminación).

a)Solución iterativa: se llega a cumplir la condición de terminación (esto se debe garantizar).

b)Solución recursiva: se debe garantizar que se llegue al caso base.

Principio importante: Toda solución recursiva puede encontrar una solución iterativa equivalente, mientras que lo contrario no siempre es cierto.

 

aqui un pequeño ejemplo con un simulador de las torres de hanoi

aqui tienen una pequeña parte del codigo recursivo del simulador del video

y aqui una pequeña parte del codigo iterativo

y aqui el link de descarga por si quieren probrar este simulador

http://www.megaupload.com/?d=AXRI1TTR