Listas enlazadas

Publicado en 'Programación' por Fernando Pala`s, 23 Dic 2008.





  1. Fernando Pala`s

    Fernando Pala`s Miembro nuevo

    Registro:
    23 Dic 2008
    Mensajes:
    1
    Likes:
    0




    LISTAS ENLAZADAS EN JAVA



    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.

    En una lista enlazada, cada elemento apunta al siguiente excepto el último que no tiene sucesor y el valor del enlace es null. Por ello los elementos son registros que contienen el dato a almacenar y un enlace al siguiente elemento. Los elementos de una lista, suelen recibir también el nombre de nodos de la lista.

    LAS LISTAS ENLAZADAS CONSISTEN EN:

    Aquí entran en juego varios temas, se trata de combinar las estructuras con los punteros para acabar por fin con la limitación de los arrays, ya no hará falta indicar el tamaño del array al principio. Después comentaremos los pros y los contras de las listas enlazas respecto a los arrays.

    Las listas enlazadas pueden ser simples, dobles o circulares. De momento veremos las simples.


    OPERADORES BÀSICOS DE UNA LISTA ENLAZADA


    Insertar: inserta un nodo con dato x en la lista, pudiendo realizarse esta inserción al principio o final de la lista o bien en orden.
    Eliminar: elimina un nodo de la lista, puede ser según la posición o por el dato.
    Buscar: busca un elemento en la lista.
    Localizar: obtiene la posición del nodo en la lista.
    Vaciar: borra todos los elementos de la lista


    EL RECORRIDO

    Recorrido simplemente despliega los datos almacenados en el arreglo info., con ayuda de un segundo arreglo llamado Índice el cual guarda el orden en el que encuentran enlazados cada uno de los datos.

    LA BUSQUEDA

    La Búsqueda su objetivo es encontrar un dato en el arreglo Info., si lo encuentra lo desplegara en la pantalla, si no lo encuentra no desplegara nada ya que el dato no se encuentra en el arreglo Info.

    INSERCIÒN AL PRINCIPIO

    La Inserción al Principio básicamente busca si existe algún lugar disponible en el arreglo Info. y lo agrega como primer Nodo si es que es posible .

    INSERCIÒN DESPUES DE UN NODO DETERMINADO

    La Inserción después de un Nodo Determinado básicamente hace lo mismo que la inserción al principio, la única diferencia es que este recibe la posición del nodo en la que será Insertada. Este Algoritmo se usa para Inserción Ordenada que mas adelante explicaremos.

    INSERCIÒN ORDENADA

    La Inserción Ordenada busca la posición en donde será Insertado el Elemento y la posición anterior donde será Insertado, después de encontrar la posición en la que será Insertado el Elemento nos regresa ese valor y lo mandamos al método de la Inserción después de un Nodo.

    · TIPOS DE LISTAS

    LISTAS DOBLES:

    Una lista doble, ó doblemente ligada es una colección de nodos en la cual cada nodo tiene dos punteros, uno de ellos apuntando a su predecesor (li) y otro a su sucesor (ld). Por medio de estos punteros se podrá avanzar o retroceder a través de la lista, según se tomen las direcciones de uno u otro puntero.

    LISTAS CIRCULARES:

    Las listas circulares tienen la característica de que el último elemento de la misma apunta al primero.

    La siguiente figura es una representación gráfica de una lista circular

    LISTAS ORTOGONALES:

    En este tipo de lista se utiliza para representar matrices. Los nodos contienen cuatro apuntadores. Uno para apuntar al nodo izquierdo (li), otro para apuntar al derecho (ld), otro al nodo inferior (lb) y por último un apuntador al nodo superior (la).

    EJEMPLO
    public class problema1 {
    public static void main(String[] args) {
    System.out.print("¿Cuántas edades desea ingresar?");
    int n=Leer.datoInt();
    int[] edades=new int[n];
    int i;
    for(i=0;i<n;i++){
    System.out.println("ingrese edad No "+(i+1)+":");
    edades=Leer.datoInt();
    }
    System.out.println("\nbuscar edad\n");
    System.out.print("ingrese edad a buscar:");
    int E=Leer.datoInt();
    boolean encontrado=false;
    for(i=0;i<n;i++){
    if (edades==E){
    System.out.println("edad encontrada en el indice:"+i);
    encontrado=true;
    }
    }
    if (encontrado==false)
    System.out.println("no se encuentra la edad buscada en el array");
    System.out.println("\nEdades almacenadas\n");
    for(i=0;i<n;i++){
    System.out.println("edades["+i+"]:"+edades);
    }
    }
    }

    · Con este pequeño programa podremos escoger cuatas edades deseamos ingresar y así mismo buscar la edad que queramos.
     


  2. Dr_Greg_House

    Dr_Greg_House Suspendido

    Registro:
    13 Abr 2008
    Mensajes:
    146
    Likes:
    1
    O eres dama o eres caballero, has estudiado algo de programacion en java, has compilado tu ejemplo, lo has posteado completo?

    Nota de curso:

    CERO
     
  3. DiabuluS

    DiabuluS Miembro maestro

    Registro:
    21 Ene 2007
    Mensajes:
    443
    Likes:
    43
    suerte que no quizo explicar algo sobre arboles o grafos XD....Madre Santa
     
  4. Dr_Greg_House

    Dr_Greg_House Suspendido

    Registro:
    13 Abr 2008
    Mensajes:
    146
    Likes:
    1
    seeee toda una mula la o el comadre, me hace acordar a curso de algoritmos en universidad publica (una vez me cole clandestinamente), y termine recontra perdido.